Descriptional Complexity of Formal Systems

1. Front Matter

   Pages I-X

   PDF

2. Invited Papers

   1. Front Matter

      Pages 1-1

      PDF

   2. Sensing as a Complexity Measure

      • Shaull Almagor, Denis Kuperberg, Orna Kupferman

      Pages 3-15

   3. Avoiding Overlaps in Pictures

      • Marcella Anselmo, Dora Giammarresi, Maria Madonia

      Pages 16-32

   4. Descriptional Complexity and Operations – Two Non-classical Cases

      • Jürgen Dassow

      Pages 33-44

   5. Applications of Transducers in Independent Languages, Word Distances, Codes

      • Stavros Konstantinidis

      Pages 45-62

3. Contributed Papers

   1. Front Matter

      Pages 63-63

      PDF

   2. On the Degree of Nondeterminism of Tree Adjoining Languages and Head Grammar Languages

      • Suna Bensch, Maia Hoeberechts

      Pages 65-76

   3. On the Average Complexity of Strong Star Normal Form

      • Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis

      Pages 77-88

   4. Most Complex Non-returning Regular Languages

      • Janusz A. Brzozowski, Sylvie Davies

      Pages 89-101

   5. Uncountable Realtime Probabilistic Classes

      • Maksims Dimitrijevs, Abuzer Yakaryılmaz

      Pages 102-113

   6. A Parametrized Analysis of Algorithms on Hierarchical Graphs

      • Rachel Faran, Orna Kupferman

      Pages 114-127

   7. Graph-Controlled Insertion-Deletion Systems Generating Language Classes Beyond Linearity

      • Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

      Pages 128-139

   8. Computational Completeness of Networks of Evolutionary Processors with Elementary Polarizations and a Small Number of Processors

      • Rudolf Freund, Vladimir Rogojin, Sergey Verlan

      Pages 140-151

   9. Recognizing Union-Find Trees Built Up Using Union-By-Rank Strategy is NP-Complete

      • Kitti Gelle, Szabolcs Iván

      Pages 152-163

   10. Self-attraction Removal from Oritatami Systems

       • Yo-Sub Han, Hwee Kim, Trent A. Rogers, Shinnosuke Seki

       Pages 164-176

   11. One-Time Nondeterministic Computations

       • Markus Holzer, Martin Kutrib

       Pages 177-188

   12. Kuratowski Algebras Generated by Factor-, Subword-, and Suffix-Free Languages

       • Jozef Jirásek Jr., Matúš Palmovský, Juraj Šebej

       Pages 189-201

   13. Branching Measures and Nearly Acyclic NFAs

       • Chris Keeler, Kai Salomaa

       Pages 202-213

   14. Square on Deterministic, Alternating, and Boolean Finite Automata

       • Ivana Krajňáková, Galina Jirásková

       Pages 214-225

This book constitutes the proceedings of the 19th International Conference on Descriptional Complexity of Formal Systems, DCFS 2017, held in Milano, Italy, in July 2017. The 20 full papers presented together with 4 invited talks were carefully reviewed and selected from 26 submissions.Descriptional Complexity is a field in Computer Science that deals with the size of all kinds of objects that occur in computational models, such as turing machines, finite automata, grammars, splicing systems and others. The topics of this conference are related to all aspects of descriptional complexity.

• descriptional complexity
• automata theory
• formal languages
• context free languages
• regular languages
• Turing machines
• automata extensions
• computational completeness
• graph-controlled systems
• information theory
• insertion-deletion systems
• models of computation
• quantitative automata
• state complexity
• syntactic complexity
• theory of computation
• language
• upper bounds
• algorithms
• algorithm analysis and problem complexity

• Università degli Studi di Milano, Milan, Italy

  Giovanni Pighizzini

• University of Prince Edward Island, Charlottetown, Canada

  Cezar Câmpeanu

Policies and ethics