Developments in Language Theory: 11th International Conference, DLT 2007, Turku, Finland, July 3-6, 2007. Proceedings

Volker Diekert, Manfred Kufleitner (auth.), Tero Harju, Juhani Karhumäki, Arto Lepistö (eds.)3540732071, 9783540732075

This book constitutes the refereed proceedings of the 11th International Conference on Developments in Language Theory, DLT 2007, held in Turku, Finland in July 2007.

The 32 revised full papers presented together with six invited papers were carefully reviewed and selected from 74 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; bioinspired computing, and quantum computing.

---

Table of contents :
Front Matter….Pages –
On First-Order Fragments for Words and Mazurkiewicz Traces….Pages 1-19
Quantitative Generalizations of Languages….Pages 20-22
What Do We Know About Language Equations?….Pages 23-27
Information Distance and Applications….Pages 28-28
Finite Automata and the Writing of Numbers….Pages 29-30
Descriptional Complexity of Nondeterministic Finite Automata….Pages 31-35
From Determinism to Non-determinism in Recognizable Two-Dimensional Languages….Pages 36-47
Coding Partitions: Regularity, Maximality and Global Ambiguity….Pages 48-59
Multi-letter Reversible and Quantum Finite Automata….Pages 60-71
Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids….Pages 72-83
The Dynamics of Cellular Automata in Shift-Invariant Topologies….Pages 84-95
Two Element Unavoidable Sets of Partial Words….Pages 96-107
Hairpin Finite Automata….Pages 108-119
Characterizing Reduction Graphs for Gene Assembly in Ciliates….Pages 120-131
2-Visibly Pushdown Automata….Pages 132-144
An Efficient Computation of the Equation $mathbb{K}$ -Automaton of a Regular $mathbb{K}$ -Expression….Pages 145-156
An Extension of Newton’s Method to ω -Continuous Semirings….Pages 157-168
Non-constructive Methods for Finite Probabilistic Automata….Pages 169-180
The Unambiguity of Segmented Morphisms….Pages 181-192
Commutation of Binary Factorial Languages….Pages 193-204
Inapproximability of Nondeterministic State and Transition Complexity Assuming P  ≠  NP ….Pages 205-216
State Complexity of Union and Intersection of Finite Languages….Pages 217-228
Bisimulation Minimisation for Weighted Tree Automata….Pages 229-241
Conjunctive Grammars Can Generate Non-regular Unary Languages….Pages 242-253
Deterministic Blow-Ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet….Pages 254-265
Reduced Languages as ω -Generators….Pages 266-277
Avoiding Approximate Squares….Pages 278-289
Duplication Roots….Pages 290-299
Complexity Theory for Splicing Systems….Pages 300-311
Descriptional Complexity of Bounded Context-Free Languages….Pages 312-323
Definable Transductions and Weighted Logics for Texts….Pages 324-336
A Star Operation for Star-Free Trace Languages….Pages 337-345
Finite Automata on Unranked and Unordered DAGs….Pages 346-360
On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases….Pages 361-370
A Local Balance Property of Episturmian Words….Pages 371-381
Suffix Automata and Standard Sturmian Words….Pages 382-398
Fine Hierarchy of Regular Aperiodic ω -Languages….Pages 399-410
On Transition Minimality of Bideterministic Automata….Pages 411-421
Back Matter….Pages –