Developments in Language Theory

Inhalt

Invited Talks.- Reaction Systems: A Model of Computation Inspired by Biochemistry.- A Brief Excursion Inside the Class of Tiling Recognizable Two-Dimensional Languages.- The Complexity of Regular(-Like) Expressions.- On Decision Problems for Simple and Parameterized Machines.- DNA Computing and Its Implications for Theoretical Computer Science.- Numeration Systems: A Link between Number Theory and Formal Language Theory.- Regular Papers.- Algorithmic Properties of Millstream Systems.- On a Conjecture by Carpi and D'Alessandro.- Linking Algebraic Observational Equivalence and Bisimulation.- Undecidability and Hierarchy Results for Parallel Communicating Finite Automata.- Inclusion Problems for Patterns with a Bounded Number of Variables.- On the Average Number of States of Partial Derivative Automata.- On the Hybrid ?erný-Road Coloring Problem and Hamiltonian Paths.- Computing Blocker Sets for the Regular Post Embedding Problem.- Rankers over Infinite Words.- Kleene and Büchi Theorems for Weighted Automata and Multi-valued Logics over Arbitrary Bounded Lattices.- On Müller Context-Free Grammars.- Minimization of Deterministic Bottom-Up Tree Transducers.- Two-Way Unary Automata versus Logarithmic Space.- On the Periodicity of Morphic Words.- Compressed Conjugacy and the Word Problem for Outer Automorphism Groups of Graph Groups.- Using Light to Implement Parallel Boolean Algebra.- Periodicity in Tilings.- Complexity in Union-Free Regular Languages.- Schema for Parallel Insertion and Deletion.- On Schützenberger Products of Semirings.- On Language Equations XXK?=?XXL and XM?=?N over a Unary Alphabet.- Around Dot Depth Two.- Input Products for Weighted Extended Top-Down Tree Transducers.- Regular Hedge Language Factorization Revisited.- Fast Parsing for Boolean Grammars: A Generalization of Valiant's Algorithm.- On Lexicalized Well-Behaved Restarting Automata That Are Monotone.- On a Powerful Class of Non-universal P Systems with Active Membranes.- State Complexity of Prefix, Suffix, Bifix and Infix Operators on Regular Languages.- Restricted Ambiguity of Erasing Morphisms.- Automata with Extremal Minimality Conditions.- On the Existence of Minimal ?-Powers.- The Averaging Trick and the ?erný Conjecture.- Short Papers.- Pseudo-power Avoidance.- On Restricted Context-Free Grammars.- Graphs Capturing Alternations in Words.- On the Iterated Hairpin Completion.- On Lookahead Hierarchies for Monotone and Deterministic Restarting Automata with Auxiliary Symbols (Extended Abstract).- Joint Topologies for Finite and Infinite Words.