DLT 2013
17th International Conference on Developments in Language Theory
18th--21st of June 2013 Paris-Est, France

Scientific Program




Scientific Program

The talks will take place in the conference room 160 in ESIEE, Paris

Tuesday, June 18

8.00 – 8.45 Registration
8.45 – 9.00 Opening by Dominique Perrin, Head of ESIEE Paris,  Gilles Roussel, President of Université Paris-Est Marne-la-Vallée, Juhani Karhumäki, Head of the DLT Steering Committee
9.00 – 10.00 Invited Talk 1 Chair: Marie-Pierre Béal
  • Raphaël Jungers: Joint spectral characteristics: a tale of three disciplines
10.20–11.35 Session 1: Chair: Jacques Sakarovitch
  • Alberto Bertoni, Christian Choffrut and Flavio Dalessandro: Quantum finite automata and linear context-free languages: a decidable problem
  • Ugur Kucuk, A. C. Cem Say and Abuzer Yakaryilmaz: Finite automata with advice tapes
  • Martin Kutrib, Andreas Malcher and Matthias Wendlandt: One-way multi-head finite automata with pebbles but no states
11.50–12.40 Session 2: Chair: Antonio Restivo
  • Marcella Anselmo, Dora Giammarresi and Maria Madonia: Two dimensional prefix codes of pictures
  • Daniel Prusa, Frantisek Mraz and Friedrich Otto: New results on deterministic sgraffito automata
Lunch break
14.30–15.45 Session 3: Chair: Juhani Karhumäki
  • Daniel Goc, Luke Schaeffer and Jeffrey Shallit: Subword complexity and k-synchronization
  • Francine Blanchet-Sadri and Brent Woodhouse: Strict bounds for pattern avoidance
  • Seyyed Hamoon Mousavi Haji and Jeffrey Shallit: Repetition avoidance in circular factors
16.00–17.15 Session 4: Chair: Christian Choffrut
  • Zoltan Ésik and Szabolcs Ivan: Operational characterization of scattered MCFLs
  • Vincent Carnino and Sylvain Lombardy: Factorizations and universal automaton of omega languages
  • Federica Panella, Matteo Pradella, Violetta Lonati and Dino Mandrioli: Operator precedence omega-languages


Wednesday, June 19

9.00–10.00 Invited Talk 2. Chair : Michel Rigo
  • Jean-Éric Pin: Polynomials of regular languages
10.20–11.35 Session 5: Chair: Jean-Éric Pin
  • Sven De Felice and Cyril Nicaud Brzozowski algorithm is generically super-polynomial for deterministic automata
  • Ondrej Klima and Libor Polak: Alternative automata characterization of piecewise testable languages
  • Victor Marsault and Jacques Sakarovitch: Ultimate periodicity of b-recognisable sets: a quasilinear procedure
11.50–12.40 Session 6: Chair: Filippo Mignosi
  • Oscar Ibarra and Bala Ravikumar: Some decision questions concerning the time complexity of language acceptors 
  • Damien Regnault: Proof of a phase transition in probabilistic cellular automata
Lunch break
14.30 – 15.30 Invited Talk 3. Chair: Olivier Carton
  • Rūsiņš Freivalds: Ultrametric finite automata and Turing machines
15.45–17.30 Session 7: Chair: Sylvain Lombardy
  • Martin Berglund, Frank Drewes, Henrik Björklund, Brink van der Merwe and Bruce Watson: Cuts in regular expressions
  • Silvia Bonomo, Sabrina Mantaci, Antonio Restivo, Giovanna Rosone and Marinella Sciortino: Suffixes, conjugates and Lyndon words
  • Joel D. Day, Daniel Reidenbach and Johannes C. Schneider: On the dual Post correspondence problem
  • Arseny Shur: Languages with a finite antidictionary: growth-preserving transformations and available orders of growth

Thursday, June 20

9.00 – 10.00 Invited Talk 4. Chair: Volker Diekert
  • Christof Löding: Unambiguous finite automata
10.20–11.35 Session 8: Chair: Clelia De Felice
  •  Jürgen Dassow, Florin Manea, Robert Mercas and Mike Müller: Inner palindromic closure
  •  Aldo de Luca, Elena Pribavkina and Luca Q. Zamboni: A Coloring Problem for Sturmian and Episturmian Words
  •  Kalle Saari, James Currie and Narad Rampersad: Extremal words in the shift orbit closure of a morphic sequence
11.50–12.40 Session 9: Chair: Francine Blanchet-Sadri
  • Benedikt Bollig, Peter Habermehl, Martin Leucker and Benjamin Monmege: A Fresh Approach to Learning Register Automata
  • Leonid Libkin, Tony Tan and Domagoj Vrgoc: Regular Expressions with Binding over Data Words for Querying Graph Databases
Lunch break
20.00 Conference Diner


Friday, June 21

9.00–10.00 Invited Talk 5. Chair : Alexander Okhotin
  • Artur Jeż : Recompression word equations and beyond
10.20–11.35 Session 10: Chair: Massimiliano Goldwurm
  • Manfred Droste and Heiko Vogler: The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages
  • Mohamed Faouzi Atig, K. Narayan Kumar and Prakash Saivasan: Adjacent Ordered Multi-Pushdown Systems
  • Artur Jeż and Alexander Okhotin: Unambiguous conjunctive grammars over a one-letter alphabet
11.50–12.40 Session 11: Chair: Cyril Nicaud
  • Zoltán Fülöp and Andreas Maletti: Composition Closure of Epsilon-free Linear Extended Top-down Tree Transducers
  • Ping Lu, Feifei Peng and Haiming Chen: Deciding Determinism of Unary Languages Is coNP-Complete
Lunch break
14.15–16.05 Session 12: Chair: Maxime Crochemore
  • Francine Blanchet-Sadri and Nathan Fox: On the Asymptotic Abelian Complexity of Morphic Words
  • Gabriele Fici, Alessio Langiu, Thierry Lecroq, Arnaud Lefebvre, Filippo Mignosi and Elise Prieur-Gaston: Abelian Repetitions in Sturmian Words
  • Robert Mercas and Aleksi Saarela: 3-Abelian Cubes Are Avoidable on Binary Alphabets
  • Narad Rampersad, Michel Rigo and Pavel Salimov: On the Number of Abelian Bordered Words
16.30–17.00 Closing session




Online user: 1