Table of Contents
|
Descriptional Complexity of Formal Systems
Stavros Konstantinidis, Giovanni Pighizzini |
Front Matter |
Finite Automata and Randomness
Ludwig Staiger |
1-10 |
Properties of Right One-Way Jumping Finite Automata
Simon Beier, Markus Holzer |
11-23 |
Word Problem Languages for Free Inverse Monoids
Tara Brough |
24-36 |
Most Complex Deterministic Union-Free Regular Languages
Janusz Brzozowski, Sylvie Davies |
37-48 |
Site-Directed Insertion: Decision Problems, Maximality and Minimality
Da-Jung Cho, Yo-Sub Han, Kai Salomaa, Taylor Smith |
49-61 |
Two-Way Automata over Locally Finite Semirings
Louis-Marie Dando, Sylvain Lombardy |
62-74 |
A New Technique for Reachability of States in Concatenation Automata
Sylvie Davies |
75-87 |
Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs
Miguel Ferreira, Nelma Moreira, Rogério Reis |
88-100 |
On the Generation of 2-Polyominoes
Enrico Formenti, Paolo Massazza |
101-113 |
A Local Limit Property for Pattern Statistics in Bicomponent Stochastic Models
Massimiliano Goldwurm, Jianyi Lin, Marco Vignati |
114-125 |
Linear-Time Limited Automata
Bruno Guillon, Luca Prigioniero |
126-138 |
Cover Complexity of Finite Languages
Stefan Hetzl, Simon Wolfsteiner |
139-150 |
On the Grammatical Complexity of Finite Languages
Markus Holzer, Simon Wolfsteiner |
151-162 |
State Grammars with Stores
Oscar Ibarra, Ian Mcquillan |
163-174 |
Error-Free Affine, Unitary, and Probabilistic OBDDs
Rishat Ibrahimov, Kamil Khadiev, Krišjānis Prūsis, Abuzer Yakaryılmaz |
175-187 |
State Complexity of Unambiguous Operations on Deterministic Finite Automata
Galina Jirásková, Alexander Okhotin |
188-199 |
Cycle Height of Finite Automata
Chris Keeler, Kai Salomaa |
200-211 |
Finite Automata with Undirected State Graphs
Martin Kutrib, Andreas Malcher, Christian Schneider |
212-223 |
Further Closure Properties of Input-Driven Pushdown Automata
Alexander Okhotin, Kai Salomaa |
224-236 |
State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis
Tomoyuki Yamakami |
237-249 |
