Developments in Language Theory

17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013, Proceedings
Herausgegeben:Beal, Marie-Pierre; Carton, Olivier

• Broschiertes Buch

Produktbeschreibung

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.

Produktdetails

• Theoretical Computer Science and General Issues 7907
• Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
• Artikelnr. des Verlages: 978-3-642-38770-8
• 2013
• Seitenzahl: 476
• Erscheinungstermin: 24. Mai 2013
• Englisch
• Abmessung: 235mm x 155mm x 26mm
• Gewicht: 715g
• ISBN-13: 9783642387708
• ISBN-10: 3642387705
• Artikelnr.: 38106113

Inhaltsangabe

Ultrametric Finite Automata and Turing Machines.- Recompression: Word Equations and Beyond.- Joint Spectral Characteristics: A Tale of Three Disciplines.- Unambiguous Finite Automata.- An Explicit Formula for the Intersection of Two Polynomials of Regular Languages.- Two Dimensional Prefix Codes of Pictures.- Adjacent Ordered Multi-Pushdown Systems .- Cuts in Regular Expressions.- Quantum Finite Automata and Linear Context-Free Languages: A Decidable Problem.- On the Asymptotic Abelian Complexity of Morphic Words.- Strict Bounds for Pattern Avoidance.- A Fresh Approach to Learning Register Automata.- Suffixes, Conjugates and Lyndon Words.- Extremal Words in the Shift Orbit Closure of a Morphic Sequence.- Inner Palindromic Closure.- On the Dual Post Correspondence Problem.- Brzozowski Algorithm Is Generically Super-Polynomial forDeterministic Automata.- A Coloring Problem for Sturmian and Episturmian Words.- The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages.- Operational Characterization of Scattered MCFLs.- Abelian Repetitions in Sturmian Words.- Composition Closure of -Free Linear Extended Top-Down Tree Transducers.- Subword Complexity and k-Synchronization.- Some Decision Questions Concerning the Time Complexity of Language Acceptors.- Unambiguous Conjunctive Grammars over a One-Letter Alphabet.- Alternative Automata Characterization of Piecewise Testable Languages.- Finite Automata with Advice Tapes.- One-Way Multi-Head Finite Automata with Pebbles But No States.- Regular Expressions with Binding over Data Words for Querying Graph Databases.- Factorizations and Universal Automaton of Omega Languages.- Deciding Determinism of Unary Languages Is coNP-Complete.- Ultimate Periodicity of b-Recognisable Sets: A Quasilinear Procedure.- 3-Abelian Cubes Are Avoidable on Binary Alphabets.- Repetition Avoidance in Circular Factors.- Operator Precedence -Languages .- New Results on Deterministic Sgraffito Automata.- On the Number of AbelianBordered Words.- Proof of a Phase Transition in Probabilistic Cellular Automata.- Languages with a Finite Antidictionary: Growth-Preserving Transformations and Available Orders of Growth.