index - Descriptional Complexity of Formal Systems (DCFS 2017)
   


Full Text Documents

Chargement de la page

Search

Chargement de la page

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/