This book constitutes the refereed proceedings of the 6th International Conference on Developments in Language Theory, DLT 2002, held in Kyoto, Japan in September 2002.
The 28 revised full papers presented together with 8 invited papers were carefully reviewed and selected from 63 submissions. Among the topics addressed are grammars and acceptors for strings, graphs, arrays, etc; efficient algorithms for languages; combinatorial and algebraic properties of languages; decision problems; relations to complexity theory, logic picture description and analysis, DNA computing, cryptography, concurrency, quantum computing, and algebraic systems.
Author(s): Tero Harju, Grzegorz Rozenberg (auth.), Masami Ito, Masafumi Toyama (eds.)
Series: Lecture Notes in Computer Science 2450
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2003
Language: English
Pages: 438
Tags: Mathematical Logic and Formal Languages; Computation by Abstract Devices; Logics and Meanings of Programs; Discrete Mathematics in Computer Science
Computational Processes in Living Cells: Gene Assembly in Ciliates....Pages 1-20
Experimental Quantum Computation with Molecules....Pages 21-27
Efficient Transformations from Regular Expressions to Finite Automata....Pages 28-42
Extended Temporal Logic on Finite Words and Wreath Product of Monoids with Distinguished Generators....Pages 43-58
A Remark about Quadratic Trace Equations....Pages 59-66
Infinite Snake Tiling Problems....Pages 67-77
Decision Problems for Linear and Circular Splicing Systems....Pages 78-92
Finite Automata Models of Quantized Systems: Conceptual Status and Outlook....Pages 93-102
Automata on Linear Orderings....Pages 103-115
Some Properties of Ciliate Bio-operations....Pages 116-127
On the Descriptional Complexity of Some Variants of Lindenmayer Systems....Pages 128-140
Carriers and Counters....Pages 140-151
On the Separation between k -Party and ( k - 1)-Party Nondeterministic Message Complexities....Pages 152-161
Unary Language Operations and Their Nondeterministic State Complexity....Pages 162-172
Constructing Infinite Words of Intermediate Complexity....Pages 173-184
A Space Lower Bound of Two-Dimensional Probabilistic Turing Machines....Pages 185-196
Undecidability of Weak Bisimilarity for PA-Processes....Pages 197-209
Improved Bounds on the Number of Automata Accepting Finite Languages....Pages 209-219
Roots and Powers of Regular Languages....Pages 220-230
Innermost Termination of Context-Sensitive Rewriting....Pages 231-244
A Unique Structure of Two-Generated Binary Equality Sets....Pages 245-257
On Deterministic Finite Automata and Syntactic Monoid Size....Pages 258-269
An Inverse Automata Algorithm for Recognizing 2-Collapsing Words....Pages 270-282
Efficient Algorithm for Checking Multiplicity Equivalence for the Finite Z - Σ * -Automata....Pages 283-289
Some Remarks on Asynchronous Automata....Pages 290-296
Tiling Systems over Infinite Pictures and Their Acceptance Conditions....Pages 297-306
The Average Lengths of the Factors of the Standard Factorization of Lyndon Words....Pages 307-318
Circular Words Avoiding Patterns....Pages 319-325
Safety Verification for Two-Way Finite Automata with Monotonic Counters....Pages 326-338
An Infinite Prime Sequence Can Be Generated in Real-Time by a 1-Bit Inter-cell Communication Cellular Automaton....Pages 339-348
On the Structure of Graphic DLI-Sets....Pages 349-356
Finite Completion of Comma-Free Codes. Part I....Pages 357-368
On a Family of Codes with Bounded Deciphering Delay....Pages 369-380
Abstract Families of Graphs....Pages 381-392
Automaton Representation of Linear Conjunctive Languages....Pages 393-404
On-Line Odometers for Two-Sided Symbolic Dynamical Systems....Pages 405-416
Characteristic Semigroups of Directable Automata....Pages 417-427
