Developments in Language Theory: 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013, Proceedings (Lecture Notes in Computer Science (7907))

This book constitutes the proceedings of the 17th International Conference on Developments in Language Theory, DLT 2013, held in Marne-la-Vallée, France, in June 2013. The 34 full papers presented in this volume were carefully reviewed and selected from 63 submissions. The scope of the conference 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 - Ultrametric Finite Automata and Turing Machines....Pages 1-11 Recompression: Word Equations and Beyond....Pages 12-26 Joint Spectral Characteristics: A Tale of Three Disciplines....Pages 27-28 Unambiguous Finite Automata....Pages 29-30 An Explicit Formula for the Intersection of Two Polynomials of Regular Languages....Pages 31-45 Two Dimensional Prefix Codes of Pictures....Pages 46-57 Adjacent Ordered Multi-Pushdown Systems....Pages 58-69 Cuts in Regular Expressions....Pages 70-81 Quantum Finite Automata and Linear Context-Free Languages: A Decidable Problem....Pages 82-93 On the Asymptotic Abelian Complexity of Morphic Words....Pages 94-105 Strict Bounds for Pattern Avoidance....Pages 106-117 A Fresh Approach to Learning Register Automata....Pages 118-130 Suffixes, Conjugates and Lyndon Words....Pages 131-142 Extremal Words in the Shift Orbit Closure of a Morphic Sequence....Pages 143-154 Inner Palindromic Closure....Pages 155-166 On the Dual Post Correspondence Problem....Pages 167-178 Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata....Pages 179-190 A Coloring Problem for Sturmian and Episturmian Words....Pages 191-202 The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages....Pages 203-214 Operational Characterization of Scattered MCFLs....Pages 215-226 Abelian Repetitions in Sturmian Words....Pages 227-238 Composition Closure of ε -Free Linear Extended Top-Down Tree Transducers....Pages 239-251 Subword Complexity and k -Synchronization....Pages 252-263 Some Decision Questions Concerning the Time Complexity of Language Acceptors....Pages 264-276 Unambiguous Conjunctive Grammars over a One-Letter Alphabet....Pages 277-288 Alternative Automata Characterization of Piecewise Testable Languages....Pages 289-300 Finite Automata with Advice Tapes....Pages 301-312 One-Way Multi-Head Finite Automata with Pebbles But No States....Pages 313-324 Regular Expressions with Binding over Data Words for Querying Graph Databases....Pages 325-337 Factorizations and Universal Automaton of Omega Languages....Pages 338-349 Deciding Determinism of Unary Languages Is coNP-Complete....Pages 350-361 Ultimate Periodicity of b-Recognisable Sets: A Quasilinear Procedure....Pages 362-373 3-Abelian Cubes Are Avoidable on Binary Alphabets....Pages 374-383 Repetition Avoidance in Circular Factors....Pages 384-395 Operator Precedence ω -Languages....Pages 396-408 New Results on Deterministic Sgraffito Automata....Pages 409-419 On the Number of Abelian Bordered Words....Pages 420-432 Proof of a Phase Transition in Probabilistic Cellular Automata....Pages 433-444 Languages with a Finite Antidictionary: Growth-Preserving Transformations and Available Orders of Growth....Pages 445-457 Back Matter....Pages - This book constitutes the proceedings of the 17th International Conference on Developments in Language Theory, DLT 2013, held in Marne-la-Vallee, France, in June 2013. algebraic theories for automata and languages;