Table of Contents
|
Descriptional Complexity of Formal Systems
Giovanni Pighizzini, Cezar Câmpeanu |
Front Matter |
Invited Papers
|
Sensing as a Complexity Measure
Shaull Almagor, Denis Kuperberg, Orna Kupferman |
3-15 |
Avoiding Overlaps in Pictures
Marcella Anselmo, Dora Giammarresi, Maria Madonia |
16-32 |
Descriptional Complexity and Operations – Two Non-classical Cases
Jürgen Dassow |
33-44 |
Applications of Transducers in Independent Languages, Word Distances, Codes
Stavros Konstantinidis |
45-62 |
Contributed Papers
|
On the Degree of Nondeterminism of Tree Adjoining Languages and Head Grammar Languages
Suna Bensch, Maia Hoeberechts |
65-76 |
On the Average Complexity of Strong Star Normal Form
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis |
77-88 |
Most Complex Non-returning Regular Languages
Janusz Brzozowski, Sylvie Davies |
89-101 |
Uncountable Realtime Probabilistic Classes
Abuzer Yakaryılmaz, Maksims Dimitrijevs |
102-113 |
A Parametrized Analysis of Algorithms on Hierarchical Graphs
Rachel Faran, Orna Kupferman |
114-127 |
Graph-Controlled Insertion-Deletion Systems Generating Language Classes Beyond Linearity
Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman |
128-139 |
Computational Completeness of Networks of Evolutionary Processors with Elementary Polarizations and a Small Number of Processors
Rudolf Freund, Vladimir Rogojin, Sergey Verlan |
140-151 |
Recognizing Union-Find Trees Built Up Using Union-By-Rank Strategy is NP-Complete
Kitti Gelle, Szabolcs Iván |
152-163 |
Self-attraction Removal from Oritatami Systems
Yo-Sub Han, Hwee Kim, Trent Rogers, Shinnosuke Seki |
164-176 |
One-Time Nondeterministic Computations
Markus Holzer, Martin Kutrib |
177-188 |
Kuratowski Algebras Generated by Factor-, Subword-, and Suffix-Free Languages
Jozef Jirásek Jr., Matúš Palmovský, Juraj Šebej |
189-201 |
Branching Measures and Nearly Acyclic NFAs
Chris Keeler, Kai Salomaa |
202-213 |
Square on Deterministic, Alternating, and Boolean Finite Automata
Ivana Krajňáková, Galina Jirásková |
214-225 |
A Pumping Lemma for Ordered Restarting Automata
Kent Kwee, Friedrich Otto |
226-237 |
Concise Representations of Reversible Automata
Giovanna Lavado, Luca Prigioniero |
238-249 |
State Complexity of Unary SV-XNFA with Different Acceptance Conditions
Laurette Marais, Lynette Zijl |
250-261 |
Reset Complexity of Ideal Languages Over a Binary Alphabet
Marina Maslennikova |
262-273 |
2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets
Turlough Neary |
274-286 |
State Complexity of Suffix Distance
Timothy Ng, David Rappaport, Kai Salomaa |
287-298 |
The Quotient Operation on Input-Driven Pushdown Automata
Alexander Okhotin, Kai Salomaa |
299-310 |
Hosted by HAL : 