Development in Language Theory

1. Front Matter

   PDF

2. Invited Talks

   1. Hunting Redundancies in Strings

      • Golnaz Badkobeh, Supaporn Chairungsee, Maxime Crochemore

      Pages 1-14

   2. Some Remarks on Automata Minimality

      • Antonio Restivo, Roberto Vaglica

      Pages 15-27

   3. Growth Properties of Power-Free Languages

      • Arseny M. Shur

      Pages 28-43

   4. A Functional Program for Regular Expressions Matching

      • Thomas Wilke

      Pages 44-45

   5. State Complexity Research and Approximation

      • Sheng Yu, Yuan Gao

      Pages 46-57

3. Regular Papers

   1. Counting the Orderings for Multisets in Consecutive Ones Property and PQ-Trees

      • Giovanni Battaglia, Roberto Grossi, Noemi Scutellà

      Pages 58-69

   2. Avoiding Abelian Powers in Partial Words

      • Francine Blanchet-Sadri, Sean Simmons

      Pages 70-81

   3. Regular Splicing Languages Must Have a Constant

      • Paola Bonizzoni, Natasha Jonoska

      Pages 82-92

   4. The Average Transition Complexity of Glushkov and Partial Derivative Automata

      • Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis

      Pages 93-104

   5. Theory of Átomata

      • Janusz Brzozowski, Hellis Tamm

      Pages 105-116

   6. Syntactic Complexity of Ideal and Closed Languages

      • Janusz Brzozowski, Yuli Ye

      Pages 117-128

   7. Generalized One-Unambiguity

      • Pascal Caron, Yo-Sub Han, Ludovic Mignot

      Pages 129-140

   8. Simulations over Two-Dimensional On-Line Tessellation Automata

      • Gérard Cécé, Alain Giorgetti

      Pages 141-152

   9. Δ-Clearing Restarting Automata and \(\makebox{\sf CFL} \)

      • Peter Černo, František Mráz

      Pages 153-164

   10. Enumeration and Decidable Properties of Automatic Sequences

       • Émilie Charlier, Narad Rampersad, Jeffrey Shallit

       Pages 165-179

   11. Languages vs. ω-Languages in Regular Infinite Games

       • Namit Chaturvedi, Jörg Olschewski, Wolfgang Thomas

       Pages 180-191

   12. Solving Word Problems in Group Extensions over Infinite Words

       • Volker Diekert, Alexei G. Myasnikov

       Pages 192-203

   13. Abelian Primitive Words

       • Michael Domaratzki, Narad Rampersad

       Pages 204-215

   14. Scattered Context-Free Linear Orderings

       • Zoltán Ésik

       Pages 216-227

This book constitutes the refereed proceedings of the 15th International Conference on Developments in Language Theory, DLT 2011, held in Milano, Italy, in July 2011. The 34 regular papers presented were carefully reviewed and selected from numerous submissions. The volume also contains the papers or abstracts of 5 invited speakers, as well as a 2-page abstract for each of the 7 poster papers. The topics covered include grammars, acceptors and transducers for words, trees and graphs; algebraic theories of automata; codes; symbolic dynamics; algorithmic, combinatorial and algebraic properties of words and languages; decidability questions; applications of language theory, including: natural computing, image manipulation and compression, text algorithms, cryptography, concurrency, complexity theory and logic; cellular automata and multidimensional patterns; language theory aspects of quantum computing and bio-computing.

• finite automata
• formal languages
• regular languages
• simulation
• unary languages
• algorithm analysis and problem complexity

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Milano, Italy

  Giancarlo Mauri, Alberto Leporati

Policies and ethics