Descriptional Complexity of Formal Systems

1. Front Matter

   Pages I-XVI

   PDF

2. Completely Reachable Automata

   • Eugenija A. Bondar, Mikhail V. Volkov

   Pages 1-17

3. Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems

   • Gabriel Istrate, Cosmin Bonchiş

   Pages 18-28

4. Self-Verifying Finite Automata and Descriptional Complexity

   • Galina Jirásková

   Pages 29-44

5. On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection

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

   Pages 45-59

6. Unrestricted State Complexity of Binary Operations on Regular Languages

   • Janusz Brzozowski

   Pages 60-72

7. On the State Complexity of the Shuffle of Regular Languages

   • Janusz Brzozowski, Galina Jirásková, Bo Liu, Aayush Rajasekaran, Marek Szykuła

   Pages 73-86

8. MSO-definable Properties of Muller Context-Free Languages Are Decidable

   • Zoltán Ésik, Szabolcs Iván

   Pages 87-97

9. Contextual Array Grammars with Matrix and Regular Control

   • Henning Fernau, Rudolf Freund, Rani Siromoney, K. G. Subramanian

   Pages 98-110

10. Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems

    • Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

    Pages 111-125

11. Operations on Weakly Recognizing Morphisms

    • Lukas Fleischer, Manfred Kufleitner

    Pages 126-137

12. Descriptional Complexity of Bounded Regular Languages

    • Andrea Herrmann, Martin Kutrib, Andreas Malcher, Matthias Wendlandt

    Pages 138-152

13. The Complexity of Languages Resulting from the Concatenation Operation

    • Galina Jirásková, Alexander Szabari, Juraj Šebej

    Pages 153-167

14. Minimal and Reduced Reversible Automata

    • Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero

    Pages 168-179

15. Unary Self-verifying Symmetric Difference Automata

    • Laurette Marais, Lynette van Zijl

    Pages 180-191

16. State Complexity of Prefix Distance of Subregular Languages

    • Timothy Ng, David Rappaport, Kai Salomaa

    Pages 192-204

17. Two Results on Discontinuous Input Processing

    • Vojtěch Vorel

    Pages 205-216

18. Back Matter

    Pages 217-217

    PDF

his book constitutes the refereed proceedings of the 18th International Conference on Descriptional Complexity of Formal Systems, DCFS 2016, held in Bucharest, Romania, in July 2016. The 13 full papers presented together with 4 invited talks were carefully reviewed and selected from 21 submissions.Descriptional Complexity is a field in Computer Science that deals with the size of all kind of objects that occur in computational models, such as Turing Machines, finte automata, grammars, splicing systems and others. The topics of this conference are related to all aspects of descriptional complexity. 

• automata theory
• context free languages
• formal languages
• regular languages
• turing machines
• automata extensions
• computational completeness
• descriptional complexity measures
• deterministic finite automaton
• grammars
• graph-controlled systems
• information theory
• insertion-deletion systems
• models of computation
• quantitative automata
• quantum complexity theory
• state complexity
• syntactic complexity
• theory of computation
• unrestricted complexity

• University of Prince Edward Island, Charlottetown, Canada

  Cezar Câmpeanu

• Universität Kiel, Kiel, Germany

  Florin Manea

• School of Computer Science, University of Waterloo, Waterloo, Canada

  Jeffrey Shallit

Policies and ethics