Developments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings.

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. Front Matter....Pages I-XXI Recognisable Languages over Monads....Pages 1-13 Garside and Quadratic Normalisation: A Survey....Pages 14-45 Grammar-Based Tree Compression....Pages 46-57 On Decidability of Intermediate Levels of Concatenation Hierarchies....Pages 58-70 Ergodic Infinite Permutations of Minimal Complexity....Pages 71-84 Diverse Palindromic Factorization Is NP-complete....Pages 85-96 Factorization in Formal Languages....Pages 97-107 Consensus Game Acceptors....Pages 108-119 On the Size of Two-Way Reasonable Automata for the Liveness Problem....Pages 120-131 Squareable Words....Pages 132-142 Complexity Analysis: Transformation Monoids of Finite Automata....Pages 143-154 Palindromic Complexity of Trees....Pages 155-166 Deciding Proper Conjugacy of Classes of One-Sided Finite-Type-Dyck Shifts....Pages 167-178 Transfinite Lyndon Words....Pages 179-190 Unary Patterns with Permutations....Pages 191-202 Finite Automata Over Infinite Alphabets: Two Models with Transitions for Local Change....Pages 203-214 Enumeration Formulæ in Neutral Sets....Pages 215-227 On the Density of Context-Free and Counter Languages....Pages 228-239 Unary Probabilistic and Quantum Automata on Promise Problems....Pages 240-251 Generalizations of Code Languages with Marginal Errors....Pages 252-263 Minimal Reversible Deterministic Finite Automata....Pages 264-275 Multi-sequential Word Relations....Pages 276-287 The Boundary of Prefix-Free Languages....Pages 288-299 A Connected 3-State Reversible Mealy Automaton Cannot Generate an Infinite Burnside Group....Pages 300-312 Path Checking for MTL and TPTL over Data Words....Pages 313-325 Surminimisation of Automata....Pages 326-339 On the Complexity of k-Piecewise Testability and the Depth of Automata....Pages 340-351 Interval Exchange Words and the Question of Hof, Knill, and Simon....Pages 352-363 State Complexity of Neighbourhoods and Approximate Pattern Matching....Pages 364-376 Deterministic Ordered Restarting Automata that Compute Functions....Pages 377-388 Weight Assignment Logic....Pages 389-400 Complexity Bounds of Constant-Space Quantum Computation....Pages 401-412 Back Matter....Pages 413-425 ....Pages 426-438