Record Nr.



[Conference on Developments in Language Theory (17th : 2013 : Marne-la-Vallée, France)]


Developments in language theory : 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings / Marie-Pierre Béal, Olivier Carton (eds.).


Berlin ; New York : Springer, ©2013






Descrizione fisica

1 online resource (xiii, 460 pages) : illustrations.


Lecture notes in computer science, 0302-9743 ; 7907

LNCS sublibrary. SL 1, Theoretical computer science and general issues



Altri autori (Persone)

Béal, Marie-Pierre

Carton, Olivier




Electronic access

Lingua di pubblicazione



Materiale a stampa

Livello bibliografico


Note generali

International conference proceedings.

Includes author index.

Nota di bibliografia

Includes bibliographical references and author index.

Nota di contenuto

Invited Talks. Ultrametric Finite Automata and Turing Machines / Rūsiņš Freivalds -- Recompression: Word Equations and Beyond / Artur Jeż -- Joint Spectral Characteristics: A Tale of Three Disciplines / Raphaël M. Jungers -- Unambiguous Finite Automata / Christof Löding -- An Explicit Formula for the Intersection of Two Polynomials of Regular Languages / Jean-Éric Pin.

Regular Papers. Two Dimensional Prefix Codes of Pictures / Marcella Anselmo, Dora Giammarresi, Maria Madonia -- Adjacent Ordered Multi-Pushdown Systems / Mohamed Faouzi Atig, K. Narayan Kumar, Prakash Saivasan -- Cuts in Regular Expressions / Martin Berglund, Henrik Björklund, Frank Drewes, Brink van der Merwe, Bruce Watson -- Quantum Finite Automata and Linear Context-Free Languages: A Decidable Problem / Alberto Bertoni, Christian Choffrut, Flavio D'Alessandro -- On the Asymptotic Abelian Complexity of Morphic Words / Francine Blanchet-Sadri, Nathan Fox -- Strict Bounds for

Pattern Avoidance / Francine Blanchet-Sadri, Brent Woodhouse -- A Fresh Approach to Learning Register Automata / Benedikt Bollig, Peter Habermehl, Martin Leucker, Benjamin Monmege -- Suffixes, Conjugates and Lyndon Words / Silvia Bonomo, Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, Marinella Sciortino -- Extremal Words in the Shift Orbit Closure of a Morphic Sequence / James D. Currie, Narad Rampersad, Kalle Saari -- Inner Palindromic Closure / Jürgen Dassow, Florin Manea, Robert Mercaş, Mike Müller -- On the Dual Post Correspondence Problem / Joel D. Day, Daniel Reidenbach, Johannes C. Schneider.

One-Way Multi-Head Finite Automata with Pebbles But No States / Martin Kutrib, Andreas Malcher, Matthias Wendlandt -- Regular Expressions with Binding over Data Words for Querying Graph Databases / Leonid Libkin, Tony Tan, Domagoj Vrgoč -- Factorizations and Universal Automaton of Omega Languages / Vincent Carnino, Sylvain Lombardy -- Deciding Determinism of Unary Languages Is coNP-Complete / Ping Lu, Feifei Peng, Haiming Chen -- Ultimate Periodicity of b-Recognisable Sets: A Quasilinear Procedure / Victor Marsault, Jacques Sakarovitch -- 3-Abelian Cubes Are Avoidable on Binary Alphabets / Robert Mercaş, Aleksi Saarela -- Repetition Avoidance in Circular Factors / Hamoon Mousavi, Jeffrey Shallit -- Operator Precedence ω-Languages / Federica Panella, Matteo Pradella, Violetta Lonati, Dino Mandrioli -- New Results on Deterministic Sgraffito Automata / Daniel Průša, František Mráz, Friedrich Otto -- On the Number of Abelian Bordered Words / Narad Rampersad, Michel Rigo, Pavel Salimov -- Proof of a Phase Transition in Probabilistic Cellular Automata / Damien Regnault -- Languages with a Finite Antidictionary: Growth-Preserving Transformations and Available Orders of Growth / Arseny M. Shur.

Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata / Sven De Felice, Cyril Nicaud -- A Coloring Problem for Sturmian and Episturmian Words / Aldo de Luca, Elena V. Pribavkina, Luca Q. Zamboni -- The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages / Manfred Droste, Heiko Vogler -- Operational Characterization of Scattered MCFLs / Zoltán Ésik, Szabolcs Iván -- Abelian Repetitions in Sturmian Words / Gabriele Fici, Alessio Langiu, Thierry Lecroq, Arnaud Lefebvre, Filippo Mignosi -- Composition Closure of ε-Free Linear Extended Top-Down Tree Transducers / Zoltán Fülöp, Andreas Maletti -- Subword Complexity and k-Synchronization / Daniel Goč, Luke Schaeffer, Jeffrey Shallit -- Some Decision Questions Concerning the Time Complexity of Language Acceptors / Oscar H. Ibarra, Bala Ravikumar -- Unambiguous Conjunctive Grammars over a One-Letter Alphabet / Artur Jeż, Alexander Okhotin -- Alternative Automata Characterization of Piecewise Testable Languages / Ondřej Klíma, Libor Polák -- Finite Automata with Advice Tapes / Uğur Küçük, A.C. Cem Say, Abuzer Yakaryılmaz.


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.