DLT 2005 was the 9th Conference on Developments in Language Theory. It was intended to cover all important areas of language theory, such us gr- mars, acceptors and transducers for strings, trees, graphs, and arrays; e?cient text algorithms; algebraic theories for automata and languages; combinatorial andalgebraicpropertiesofwordsand languages;variable-lengthcodes; symbolic dynamics; decision problems; relations to complexity theory and logic; picture descriptionandanalysis;polyominoesandbidimensionalpatterns;cryptography; concurrency; and DNA and quantum computing. DLT 2005 was held at Mondello (Palermo, Italy) during July 4 8, 2005 and was sponsored by the Department of Matematica e Applicazioni, University of Palermo, the Department of Informatica e Applicazioni R.M. Capocelli, UniversityofSalerno,andtheMIURProject Formal Languages and Automata: Methods, Models and Applications. The conference was also under the auspices of EATCS. We are grateful to these organizations. Previous DLTs were held in Turku (1993), Magdeburg (1995), Thessaloniki (1997), Aachen (1999), Vienna (2001), Kyoto (2002), Szeged (2003) and Auckland (2004). Since 2001, a DLT conference takes place in every odd year in Europe, and in every even year in another continent. The Program Committee selected 29 papers from 73 submitted papers. The papers came from the following countries: Austria, Belgium, Canada, Czech - public,Finland,France,Germany,India,Italy,Portugal,Moldova,Russia,Spain, and the UK. Each submitted paper was evaluated by at least three members of theProgramCommittee,whowereoftenassistedbytheirreferees.All29selected papers are contained in this volume together with 6 invited presentations.

Includes supplementary material: sn.pub/extras

Inhalt
Restricted Towers of Hanoi and Morphisms.- Collapsing Words: A Progress Report.- Locally Consistent Parsing and Applications to Approximate String Comparisons.- Central Sturmian Words: Recent Developments.- Reversible Cellular Automata.- Inexpressibility Results for Regular Languages in Nonregular Settings.- Complexity of Quantum Uniform and Nonuniform Automata.- Membership and Finiteness Problems for Rational Sets of Regular Languages.- Tissue P Systems with Antiport Rules and Small Numbers of Symbols and Cells.- The Mortality Threshold for Partially Monotonic Automata.- Sturmian Words: Dynamical Systems and Derivated Words.- Schützenberger and Eilenberg Theorems for Words on Linear Orderings.- On the Membership of Invertible Diagonal Matrices.- A Kleene Theorem for Languages of Words Indexed by Linear Orderings.- Revolving-Input Finite Automata.- Some New Results on Palindromic Factors of Billiard Words.- A Note on a Result of Daurat and Nivat.- Palindromes in Sturmian Words.- Voronoi Cells of Beta-Integers.- Languages with Mismatches and an Application to Approximate Indexing.- Bidimensional Sturmian Sequences and Substitutions.- Unambiguous Morphic Images of Strings.- Complementing Two-Way Finite Automata.- On Timed Automata with Discrete Time Structural and Language Theoretical Characterization.- Monotone Deterministic RL-Automata Don't Need Auxiliary Symbols.- On Hairpin-Free Words and Languages.- Adding Monotonic Counters to Automata and Transition Graphs.- Polynomial Generators of Recursively Enumerable Languages.- On Language Inequalities XK???LX.- The Power of Tree Series Transducers of Type I and II.- The Inclusion Problem for Unambiguous Rational Trace Languages.- LR Parsing for Boolean Grammars.- On Some Properties of the Language of2-Collapsing Words.- Semi-rational Sets of DAGs.- On the Frequency of Letters in Pure Binary Morphic Sequences.