Developments in Language Theory

1. Front Matter

   Pages I-XXI

   PDF

2. Recognisable Languages over Monads

   • Mikołaj Bojańczyk

   Pages 1-13

3. Garside and Quadratic Normalisation: A Survey

   • Patrick Dehornoy

   Pages 14-45

4. Grammar-Based Tree Compression

   • Markus Lohrey

   Pages 46-57

5. On Decidability of Intermediate Levels of Concatenation Hierarchies

   • Jorge Almeida, Jana Bartoňová, Ondřej Klíma, Michal Kunc

   Pages 58-70

6. Ergodic Infinite Permutations of Minimal Complexity

   • Sergey V. Avgustinovich, Anna E. Frid, Svetlana Puzynina

   Pages 71-84

7. Diverse Palindromic Factorization Is NP-complete

   • Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piątkowski et al.

   Pages 85-96

8. Factorization in Formal Languages

   • Paul C. Bell, Daniel Reidenbach, Jeffrey Shallit

   Pages 97-107

9. Consensus Game Acceptors

   • Dietmar Berwanger, Marie van den Bogaard

   Pages 108-119

10. On the Size of Two-Way Reasonable Automata for the Liveness Problem

    • Maria Paola Bianchi, Juraj Hromkovič, Ivan Kováč

    Pages 120-131

11. Squareable Words

    • Francine Blanchet-Sadri, Abraham Rashin

    Pages 132-142

12. Complexity Analysis: Transformation Monoids of Finite Automata

    • Christian Brandl, Hans Ulrich Simon

    Pages 143-154

13. Palindromic Complexity of Trees

    • Srečko Brlek, Nadia Lafrenière, Xavier Provençal

    Pages 155-166

14. Deciding Proper Conjugacy of Classes of One-Sided Finite-Type-Dyck Shifts

    • Marie-Pierre Béal, Pavel Heller

    Pages 167-178

15. Transfinite Lyndon Words

    • Luc Boasson, Olivier Carton

    Pages 179-190

16. Unary Patterns with Permutations

    • James Currie, Florin Manea, Dirk Nowotka

    Pages 191-202

17. Finite Automata Over Infinite Alphabets: Two Models with Transitions for Local Change

    • Christopher Czyba, Christopher Spinrath, Wolfgang Thomas

    Pages 203-214

18. Enumeration Formulæ in Neutral Sets

    • Francesco Dolce, Dominique Perrin

    Pages 215-227

19. On the Density of Context-Free and Counter Languages

    • Joey Eremondi, Oscar H. Ibarra, Ian McQuillan

    Pages 228-239

20. *-Continuous Kleene \(\omega \)-Algebras

    • Zoltán Ésik, Uli Fahrenberg, Axel Legay

    Pages 240-251

This book constitutes the proceedings of the 19th International Conference on Developments in Language Theory, DLT 2015, held in Liverpool, UK. The 31 papers presented together with 5 invited talks were carefully reviewed and selected from 54 submissions. Its scope is very general and includes, among others, the following topics and areas: combinatorial and algebraic properties of words and languages, grammars, acceptors and transducers for strings, trees, graphs, arrays, algebraic theories for automata and languages, codes, efficient text algorithms, symbolic dynamics, decision problems, relationships to complexity theory and logic, picture description and analysis, polyominoes and bidimensional patterns, cryptography, concurrency, cellular automata, bio-inspired computing, and quantum computing.

• algebraic language theory
• automata theory
• bio-inspired computing
• cellular automata
• complexity theory
• concurrency
• context-free languages
• cryptography
• decidability
• finite automata
• formal languages
• grammars
• multidimensional patterns
• pushdown automata
• quantum computing
• regular languages
• symbolic dynamics
• transducers
• trees and graphs
• variable length codes

• University of Liverpool, Liverpool, United Kingdom

  Igor Potapov

Policies and ethics