Markus Holzer

Barbara König

Bull. EATCS, 2004

TantrixTM rotation puzzles are intractable.

[BibT_eX]

[DOI]

Waltraud Holzer

Discret. Appl. Math., 2004

Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2004

Towards Formal Semantics for ODRL.

[BibT_eX]

[DOI]

Stefan Katzenbeisser

Christian Schallhart

Proceedings of the First International Workshop on the Open Digital Rights Language (ODRL), 2004

A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract).

[BibT_eX]

[DOI]

Martin Beaudry

José M. Fernandez

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

[BibT_eX]

[DOI]

Proceedings of the Machines, Computations, and Universality, 4th International Conference, 2004

Input Reversals and Iterated Pushdown Automata: A New Characterization of Khabbaz Geometric Hierarchy of Languages.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 2004

On Competence in CD Grammar Systems.

[BibT_eX]

[DOI]

Maurice H. ter Beek

Erzsébet Csuhaj-Varjú

György Vaszil

Proceedings of the Developments in Language Theory, 2004

2003

Alternating and empty alternating auxiliary stack automata.

[BibT_eX]

[DOI]

Pierre McKenzie

Theor. Comput. Sci., 2003

Hybrid modes in cooperating distributed grammar systems: combining the t-mode with the modes le k and =k.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

McNaughton families of languages.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Nondeterministic Descriptional Complexity Of Regular Languages.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2003

Flip-Pushdown Automata: k+1 Pushdown Reversals Are Better than k.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Flip-Pushdown Automata: Nondeterminism Is Better than Determinism.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 7th International Conference, 2003

On Deterministic Finite Automata and Syntactic Monoid Size, Continued.

[BibT_eX]

[DOI]

Barbara König

Proceedings of the Developments in Language Theory, 7th International Conference, 2003

On the Descriptional Complexity of Finite Automata With Modified Acceptance Conditions.

[BibT_eX]

Proceedings of the 5th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2003, Budapest, Hungary, July 12, 2003

On Iterated Sequential Transducers.

[BibT_eX]

Proceedings of the Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, 2003

2002

Multi-head finite automata: data-independent versus data-dependent computations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

On the Computational Complexity of Synchronized Context-Free Languages.

[BibT_eX]

[DOI]

J. Univers. Comput. Sci., 2002

Graph-Controlled Cooperating Distributed Grammar Systems with Singleton Components.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2002

The complexity of tensor calculus.

[BibT_eX]

[DOI]

Pierre McKenzie

Comput. Complex., 2002

State Complexity of Basic Operations on Nondeterministic Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2002

Unary Language Operations and Their Nondeterministic State Complexity.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 6th International Conference, 2002

Economy of Descriptions for Basic Constructions on Rational Transductions.

[BibT_eX]

Proceedings of the Fourth International Workshop on Descriptional Complexity of Formal Systems - DCFS 2002, London, Canada, August 21, 2002

2001

Hybrid modes in cooperating distributed grammar systems: internal versus external hybridization.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

On the State Complexity of k-Entry Deterministic Finite Automata.

[BibT_eX]

[DOI]

Kai Salomaa

Sheng Yu

J. Autom. Lang. Comb., 2001

On the Number of Active Symbols in L and CD Grammar Systems.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2001

Improving Raster Image Run-Length Encoding Using Data Order.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2001

On the Relationship between the McNaughton Families of Languages and the Chomsky Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

2000

Grammar Systems with Negated Conditions in their Cooperation Protocols

[BibT_eX]

[DOI]

J. Univers. Comput. Sci., 2000

External Contextual and Conditional Languages.

[BibT_eX]

Proceedings of the Recent Topics in Mathematical and Computational Linguistics, 2000

1999

On a Hierarchy of Languages Generated by Cooperating Distributed Grammar Systems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

On Accepting Pure Lindenmayer Systems.

[BibT_eX]

[DOI]

Fundam. Informaticae, 1999

Regulated Array Grammars of Finite Index. Part II: Syntactic Pattern Recognition.

[BibT_eX]

Proceedings of the Grammatical Models of Multi-Agent Systems, 1999

Regulated Array Grammars of Finite Index. Part I: Theoretical Investigations.

[BibT_eX]

Proceedings of the Grammatical Models of Multi-Agent Systems, 1999

On fixed and general membership for external and internal contextual languages.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 1999

Cooperating distributed grammar systems with non-terminating components.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 1999

1998

Data-independent versus data-dependent computations on multi-head automata.

[BibT_eX]

[DOI]

PhD thesis, 1998

Character Recognition with k-Head Finite Array Automata.

[BibT_eX]

[DOI]

Proceedings of the Advances in Pattern Recognition, 1998

The Generative Power of d-Dimensional #-Context-Free Array Grammars.

[BibT_eX]

Proceedings of the International Colloquium Universal Machines and Computations, 1998

VisA: A Tool for Visualizing and Animating Automata and Formal Languages.

[BibT_eX]

[DOI]

Muriel Quenzer

Proceedings of the Graph Drawing, 6th International Symposium, 1998

VisA: towards a students' green card to automata theory and formal languages.

[BibT_eX]

[DOI]

Muriel Quenzer

Proceedings of the ACM SIGCSE 3rd Australasian Conference on Computer Science Education, 1998

1997

Bounding resources in Cooperating Distributed Grammar Systems.

[BibT_eX]

Proceedings of the 3rd International Conference Developments in Language Theory, 1997

On the Complexity of Iterated Insertions.

[BibT_eX]

[DOI]

Klaus-Jörn Lange

Proceedings of the New Trends in Formal Languages, 1997

Conditional Context-Free Languages of Finite Index.

[BibT_eX]

[DOI]

Proceedings of the New Trends in Formal Languages, 1997

1996

Inductive Counting for Width-Restricted Branching Programs.

[BibT_eX]

[DOI]

Inf. Comput., 1996

Accepting Multi-Agent Systems.

[BibT_eX]

[DOI]

Comput. Artif. Intell., 1996

Accepting Multi-Agent Systems II.

[BibT_eX]

[DOI]

Acta Cybern., 1996

1995

Expressing Uniformity via Oracles

[BibT_eX]

Peter Rossmanith

Universität Trier, Mathematik/Informatik, Forschungsbericht, 1995

Automata That Take Advice.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

On Emptiness and Counting for Alternating Finite Automata.

[BibT_eX]

Proceedings of the Developments in Language Theory II, 1995

1994

Inductive Counting below LOGSPACE

[BibT_eX]

Universität Trier, Mathematik/Informatik, Forschungsbericht, 1994

1993

On the Complexities of Linear LL(1) and LR(1) Grammars.

[BibT_eX]

[DOI]

Klaus-Jörn Lange

Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

Deterministic OL Languages are of Very Low Complexity: DOL is in AC0.

[BibT_eX]

Proceedings of the Developments in Language Theory, 1993

1992

Parallel Complexity of Iterated Morphisms and the Arithmetic of Small Numbers.

[BibT_eX]

[DOI]