index - Descriptional Complexity of Formal Systems
   


Full Text Documents

23

Search

Chargement de la page

 
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

 


Designed by Inria-IES Team : http://hal.inria.fr/    Hosted by HAL : http://hal.archives-ouvertes.fr/