VOLUME 9 2004 NUMBERS 2–3

Special Issues with Selected and Extended Papers of the Fourth International Workshop on Descriptional Complexity of Formal Systems (DCFS 2002)

Jürgen Dassow, Helmut Jürgensen, Detlef Wotschke:
Editorial173–173
Henning Bordihn, Markus Holzer, Martin Kutrib:
Economy of Description for Basic Constructions on Rational Transductions175–188
Cezar Câmpeanu, Wing Hong Ho:
The Maximum State Complexity for Finite Languages189–202
Jean-Marc Champarnaud, Georges Hansel, Thomas Paranthoën, Djelloul Ziadi:
Random Generation Models for NFAs203–216
Michael Domaratzki, Kai Salomaa:
State Complexity of Shuffle on Trajectories217–232
Keith Ellul, Bryan Krawetz, Jeffrey Shallit, Ming-wei Wang:
Regular Expressions: New Results and Open Problems233–256
Mark G. Eramian:
Efficient Simulation of Nondeterministic Weighted Finite Automata257–267
Cristian Grozea:
NP Predicates Computable in the Weakest Level of the Grzegorczyck Hierarchy269–279
Martin Kappes, Chandra M. R. Kintala:
Tradeoffs Between Reliability and Conciseness of Deterministic Finite Automata281–292
Lila Kari, Stavros Konstantinidis:
Descriptional Complexity of Error/Edit Systems293–309
Mutyam Madhu:
Descriptional Complexity of Rewriting P Systems311–316
Ian McQuillan:
Descriptional Complexity of Block-Synchronization Context-Free Grammars317–332
Charlotte Miller:
Context Derivation Sets and Context-Free Normal Forms333–345
Frank Niessner:
Büchi Automata and Their Degrees of Nondeterminism and Ambiguity347–363
Alexander Okhotin:
State Complexity of Linear Conjunctive Languages365–381