Table of Contents
|
Descriptional Complexity of Formal Systems
- Michal Hospodár, Galina Jirásková, Stavros Konstantinidis |
Front Matter |
A General Framework for Sequential Grammars with Control Mechanisms
- Rudolf Freund |
1-34 |
Low-Complexity Tilings of the Plane
- Jarkko Kari |
35-45 |
Union-Freeness, Deterministic Union-Freeness and Union-Complexity
- Benedek Nagy |
46-56 |
Limited Automata: Properties, Complexity and Variants
- Giovanni Pighizzini |
57-73 |
Nondeterministic Right One-Way Jumping Finite Automata (Extended Abstract)
- Simon Beier, Markus Holzer |
74-85 |
State Complexity of Single-Word Pattern Matching in Regular Languages
- Janusz Brzozowski, Sylvie Davies, Abhishek Madan |
86-97 |
Square, Power, Positive Closure, and Complementation on Star-Free Languages
- Sylvie Davies, Michal Hospodár |
98-110 |
Descriptional Complexity of Matrix Simple Semi-conditional Grammars
- Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman |
111-123 |
Regulated Tree Automata
- Henning Fernau, Martin Vu |
124-136 |
Generalized de Bruijn Words and the State Complexity of Conjugate Sets
- Daniel Gabric, Štěpán Holub, Jeffrey Shallit |
137-146 |
The Syntactic Complexity of Semi-flower Languages
- Kitti Gelle, Szabolcs Iván |
147-157 |
Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity
- Yo-Sub Han, Sang-Ki Ko, Kai Salomaa |
158-170 |
Computability on quasi-Polish spaces
- Mathieu Hoyrup, Cristóbal Rojas, Victor Selivanov, Donald Stull |
171-183 |
NFA-to-DFA Trade-Off for Regular Operations
- Galina Jirásková, Ivana Krajňáková |
184-196 |
State Complexity of Simple Splicing
- Lila Kari, Timothy Ng |
197-209 |
Nondeterminism Growth and State Complexity
- Chris Keeler, Kai Salomaa |
210-222 |
Descriptional Complexity of Iterated Uniform Finite-State Transducers
- Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano |
223-234 |
On Classes of Regular Languages Related to Monotone WQOs
- Mizuhito Ogawa, Victor Selivanov |
235-247 |
State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages
- Alexander Okhotin, Elizaveta Sazhneva |
248-259 |
Pushdown Automata and Constant Height: Decidability and Bounds
- Giovanni Pighizzini, Luca Prigioniero |
260-271 |
On the Decidability of Finding a Positive ILP-Instance in a Regular Set of ILP-Instances
- Petra Wolf |
272-284 |
How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?
- Tomoyuki Yamakami |
285-297 |
