VOLUME 7 2002 NUMBER 4

Special Issue with Selected Papers of the Third Workshop on Descriptional Complexity of Automata, Grammars, and Related Structures (DCAGRS 2001)

Jürgen Dassow, Detlef Wotschke, Bernd Reichel:
Editorial417–417
Henry N. Adorna:
3-Party Message Complexity is Better than 2-Party Ones for Proving Lower Bounds on the Size of Minimal Nondeterministic Finite Automata419–432
K. Arthi, Kamala Krithivasan, Erzsébet Csuhaj-Varjú:
On Rule-Number Complexity of Components of Probabilistic Cooperating Distributed Grammar Systems433–446
Henning Bordihn, Bernd Reichel:
On Descriptions of Context-Free Languages by CD Grammar Systems447–454
Michael Domaratzki:
State Complexity of Proportional Removals455–468
Michael Domaratzki, Derek Kisman, Jeffrey Shallit:
On the Number of Distinct Languages Accepted by Finite Automata with n States469–486
Henning Fernau, Markus Holzer:
Graph-Controlled Cooperating Distributed Grammar Systems with Singleton Components487–503
Kosaburo Hashiguchi, Takahiro Kunai, Shuji Jimbo:
Finite Codes over Free Binoids505–518
Juraj Hromkovič:
Descriptional Complexity of Finite Automata: Concepts and Open Problems519–531
Martin Kutrib:
Refining Nondeterminism Below Linear Time533–547
Andreas Malcher:
Descriptional Complexity of Cellular Automata and Decidability Questions549–560
Carlos Martín-Vide, Victor Mitrana:
Grammars with Bounded-Life Resources561–570
Alexander Meduna:
Descriptional Complexity of Scattered Rewriting and Multirewriting: An Overview571–577
Patrice Séébold:
About some Overlap-Free Morphisms on a n-Letter Alphabet579–597
Ferucio Laurenţiu Ţiplea, Erkki Mäkinen:
On the Complexity of a Problem on Monadic String Rewriting Systems599–609