VOLUME 6 2001 NUMBER 4

Selected Papers of the Second Workshop on Descriptional Complexity of Automata, Grammars, and Related Structures (DCAGRS, London, Ontario, Canada, July 27–29, 2000)

Helmut Jürgensen:
Editorial393–393
Suna Aydin, Helmut Jürgensen, Lynda E. Robbins:
Dialogues as Co-Operating Grammars395–410
Henning Bordihn, Markus Holzer:
On the Number of Active Symbols in L and CD Grammar Systems411–426
Pál Dömösi, Zoltán Ésik:
Homomorphic Simulation and Letichevsky's Criterion427–436
Christian Glasser, Heinz Schmitz:
The Boolean Structure of Dot-Depth One437–452
Markus Holzer, Kai Salomaa, Sheng Yu:
On the State Complexity of k-Entry Deterministic Finite Automata453–466
Bakhadyr Khoussainov, Sasha Rubin:
Graphs with Automatic Presentations over a Unary Alphabet467–480
Massimiliano Milani, Giovanni Pighizzini:
Tight Bounds on the Simulation of Unary Probabilistic Automata by Deterministic Automata481–492
František Mráz:
Lookahead Hierarchies of Restarting Automata493–506
Taishin Y. Nishida:
Sizes of Context-Free Languages Generated by Context-Free Grammars and Stable and Recurrent 0L Systems507–518
Alexander Okhotin:
Conjunctive Grammars519–535
Jeffrey Shallit, Ming-wei Wang:
Automatic Complexity of Strings537–554
K. G. Subramanian, D. Gnanaraj Thomas, P. Helen Chandra, Maia Hoeberechts:
Basic Puzzle Grammars and Generation of Polygons555–568
Yuri Velinov:
On the Regions of Influence in Complex Decomposition Forms of Finite Functions569–579