Developments in Language Theory

1. Front Matter

   PDF

2. Invited Talks

   1. Iteration Semirings

      • Zoltán Ésik

      Pages 1-20

   2. Various Aspects of Finite Quantum Automata

      • Mika Hirvensalo

      Pages 21-33

   3. On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes

      • Juraj Hromkovič, Georg Schnitger

      Pages 34-55

   4. Selected Ideas Used for Decidability and Undecidability of Bisimilarity

      • Petr Jančar

      Pages 56-71

   5. The Frobenius Problem and Its Generalizations

      • Jeffrey Shallit

      Pages 72-83

   6. Well Quasi-orders in Formal Language Theory

      • Flavio D’Alessandro, Stefano Varricchio

      Pages 84-95

3. Contributed Papers

   1. On the Non-deterministic Communication Complexity of Regular Languages

      • Anil Ada

      Pages 96-107

   2. General Algorithms for Testing the Ambiguity of Finite Automata

      • Cyril Allauzen, Mehryar Mohri, Ashish Rastogi

      Pages 108-120

   3. Emptiness of Multi-pushdown Automata Is 2ETIME-Complete

      • Mohamed Faouzi Atig, Benedikt Bollig, Peter Habermehl

      Pages 121-133

   4. The Average State Complexity of the Star of a Finite Set of Words Is Linear

      • Frédérique Bassino, Laura Giambruno, Cyril Nicaud

      Pages 134-145

   5. On the Computational Capacity of Parallel Communicating Finite Automata

      • Henning Bordihn, Martin Kutrib, Andreas Malcher

      Pages 146-157

   6. On a Generalization of Standard Episturmian Morphisms

      • Michelangelo Bucci, Aldo de Luca, Alessandro De Luca

      Pages 158-169

   7. Universal Recursively Enumerable Sets of Strings

      • Cristian S. Calude, André Nies, Ludwig Staiger, Frank Stephan

      Pages 170-182

   8. Algorithmically Independent Sequences

      • Cristian S. Calude, Marius Zimand

      Pages 183-195

   9. Relationally Periodic Sequences and Subword Complexity

      • Julien Cassaigne, Tomi Kärki, Luca Q. Zamboni

      Pages 196-205

   10. Bounds on Powers in Strings

       • Maxime Crochemore, Szilárd Zsolt Fazekas, Costas Iliopoulos, Inuka Jayasekera

       Pages 206-215

   11. When Is Reachability Intrinsically Decidable?

       • Barbara F. Csima, Bakhadyr Khoussainov

       Pages 216-227

   12. Some New Modes of Competence-Based Derivations in CD Grammar Systems

       • Erzsébet Csuhaj-Varjú, Jürgen Dassow, György Vaszil

       Pages 228-239

   13. The Synchronization Problem for Strongly Transitive Automata

       • Arturo Carpi, Flavio D’Alessandro

       Pages 240-251

This book constitutes the refereed proceedings of the 12th International Conference on Developments in Language Theory, DLT 2008, held in Kyoto, Japan, September 2008. The 36 revised full papers presented together with 6 invited papers were carefully reviewed and selected from 102 submissions. All important issues in language theory are addressed including grammars, acceptors and transducers for words, trees and graphs; algebraic theories of automata; algorithmic, combinatorial and algebraic properties of words and languages; variable length codes; symbolic dynamics; cellular automata; polyominoes and multidimensional patterns; decidability questions; image manipulation and compression; efficient text algorithms; relationships to cryptography, concurrency, complexity theory and logic; bio-inspired computing; quantum computing.

• DNA computing
• Factor
• acceptors
• algebraic language theory
• algorithms
• calculus
• combinatorics
• complexity
• complexity theory
• context-sensitive languages
• cryptography
• derivation
• language classes
• logic
• proof
• algorithm analysis and problem complexity

Policies and ethics