Full Text Documents

Search


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

 

 


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