Developments in Language Theory: 8th International Conference, DLT 2004, Auckland, New Zealand, December 13-17, 2004. Proceedings

Bruno Courcelle (auth.), Cristian S. Calude, Elena Calude, Michael J. Dinneen (eds.)3540240144, 9783540240143, 9783540305507

This book constitutes the refereed proceedings of the 8th International Conference on Developments in Language Theory, DLT 2004, held in Auckland, New Zealand in December 2004.

The 30 revised full papers presented together with 5 invited papers were carefully reviewed and selected from 47 submissions. The main subjects are formal languages, automata, conventional and unconventional computation theory, and applications of automata theory. Among the topics addressed are grammars and acceptors for strings, graphs, and arrays; efficient text algorithms, combinatorial and algebraic properties of languages; decision problems; relations to complexity theory and logic; picture description and analysis; cryptography; concurrency; DNA computing; and quantum computing.

---

Table of contents :
Front Matter….Pages –
Recognizable Sets of Graphs, Hypergraphs and Relational Structures: A Survey….Pages 1-11
Some New Directions and Questions in Parameterized Complexity….Pages 12-26
Basic Notions of Reaction Systems….Pages 27-29
A Kleene Theorem for a Class of Communicating Automata with Effective Algorithms….Pages 30-48
Algebraic and Topological Models for DNA Recombinant Processes….Pages 49-62
Regular Expressions for Two-Dimensional Languages Over One-Letter Alphabet….Pages 63-75
On Competence in CD Grammar Systems….Pages 76-88
The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels….Pages 89-101
Input Reversals and Iterated Pushdown Automata: A New Characterization of Khabbaz Geometric Hierarchy of Languages….Pages 102-113
On the Maximum Coefficients of Rational Formal Series in Commuting Variables….Pages 114-126
On Codes Defined by Bio-operations….Pages 127-138
Avoidable Sets and Well Quasi-Orders….Pages 139-150
A Ciliate Bio-operation and Language Families….Pages 151-162
Semantic Shuffle on and Deletion Along Trajectories….Pages 163-174
Sturmian Graphs and a Conjecture of Moser….Pages 175-187
P Systems Working in the Sequential Mode on Arrays and Strings….Pages 188-199
Optimal Time and Communication Solutions of Firing Squad Synchronization Problems on Square Arrays, Toruses and Rings….Pages 200-211
The Power of Maximal Parallelism in P Systems….Pages 212-224
An Efficient Pattern Matching Algorithm on a Subclass of Context Free Grammars….Pages 225-236
On the Complexity of 2-Monotone Restarting Automata….Pages 237-248
On Left-Monotone Deterministic Restarting Automata….Pages 249-260
On the Computation Power of Finite Automata in Two-Dimensional Environments….Pages 261-271
The Role of the Complementarity Relation in Watson-Crick Automata and Sticker Systems….Pages 272-283
The Boolean Closure of Linear Context-Free Languages….Pages 284-295
Context-Sensitive Decision Problems in Groups….Pages 296-307
Decidability and Complexity in Automatic Monoids….Pages 308-320
Relating Tree Series Transducers and Weighted Tree Automata….Pages 321-333
An NP-Complete Fragment of LTL….Pages 334-344
From Post Systems to the Reachability Problems for Matrix Semigroups and Multicounter Automata….Pages 345-356
Words Avoiding $frac{7}{3}$ -Powers and the Thue–Morse Morphism….Pages 357-367
On the Equivalence Problem for E-Pattern Languages Over Small Alphabets….Pages 368-380
Complementation of Rational Sets on Countable Scattered Linear Orderings….Pages 381-392
On the Hausdorff Measure of ω -Power Languages….Pages 393-405
A Method for Deciding the Finiteness of Deterministic Tabled Picture Languages….Pages 406-417
Tissue P Systems with Minimal Symport/Antiport….Pages 418-429
Back Matter….Pages –