This book constitutes the refereed proceedings of the 9th International Conference on Developments in Language Theory, DLT 2005, held in Palermo, Italy in July 2005.
The 29 revised full papers presented together with 5 invited papers were carefully reviewed and selected from 73 submissions. All important issues in language theory are addressed including grammars, acceptors, and transducers for strings frees, graphs, and arrays; efficient text algorithms; algebraic theories for automata and languages; variable-length codes; symbolic dynamics; decision problems; relations to complexity theory and logic; picture description and analysis; cryptography; concurrency; DNA computing; and quantum computing.
Author(s): Jean-Paul Allouche, Amir Sapir (auth.), Clelia De Felice, Antonio Restivo (eds.)
Series: Lecture Notes in Computer Science 3572 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2005
Language: English
Pages: 412
Tags: Mathematical Logic and Formal Languages; Computation by Abstract Devices; Logics and Meanings of Programs; Discrete Mathematics in Computer Science
Front Matter....Pages -
Restricted Towers of Hanoi and Morphisms....Pages 1-10
Collapsing Words: A Progress Report....Pages 11-21
Locally Consistent Parsing and Applications to Approximate String Comparisons....Pages 22-35
Central Sturmian Words: Recent Developments....Pages 36-56
Reversible Cellular Automata....Pages 57-68
Inexpressibility Results for Regular Languages in Nonregular Settings....Pages 69-77
Complexity of Quantum Uniform and Nonuniform Automata....Pages 78-87
Membership and Finiteness Problems for Rational Sets of Regular Languages....Pages 88-99
Tissue P Systems with Antiport Rules and Small Numbers of Symbols and Cells....Pages 100-111
The Mortality Threshold for Partially Monotonic Automata....Pages 112-121
Sturmian Words: Dynamical Systems and Derivated Words....Pages 122-133
Schützenberger and Eilenberg Theorems for Words on Linear Orderings....Pages 134-145
On the Membership of Invertible Diagonal Matrices....Pages 146-157
A Kleene Theorem for Languages of Words Indexed by Linear Orderings....Pages 158-167
Revolving-Input Finite Automata....Pages 168-179
Some New Results on Palindromic Factors of Billiard Words....Pages 180-188
A Note on a Result of Daurat and Nivat....Pages 189-198
Palindromes in Sturmian Words....Pages 199-208
Voronoi Cells of Beta-Integers....Pages 209-223
Languages with Mismatches and an Application to Approximate Indexing....Pages 224-235
Bidimensional Sturmian Sequences and Substitutions....Pages 236-247
Unambiguous Morphic Images of Strings....Pages 248-259
Complementing Two-Way Finite Automata....Pages 260-271
On Timed Automata with Discrete Time – Structural and Language Theoretical Characterization....Pages 272-283
Monotone Deterministic RL-Automata Don’t Need Auxiliary Symbols....Pages 284-295
On Hairpin-Free Words and Languages....Pages 296-307
Adding Monotonic Counters to Automata and Transition Graphs....Pages 308-319
Polynomial Generators of Recursively Enumerable Languages....Pages 320-326
On Language Inequalities XK ⊆ LX ....Pages 327-337
The Power of Tree Series Transducers of Type I and II....Pages 338-349
The Inclusion Problem for Unambiguous Rational Trace Languages....Pages 350-361
LR Parsing for Boolean Grammars....Pages 362-373
On Some Properties of the Language of 2-Collapsing Words....Pages 374-384
Semi-rational Sets of DAGs....Pages 385-396
On the Frequency of Letters in Pure Binary Morphic Sequences....Pages 397-408
Back Matter....Pages -
