Developments in Language Theory

6th International Conference, DLT 2002, Kyoto, Japan, September 18-21, 2002, Revised Papers

448 Seiten, Taschenbuch

Kurzbeschreibung des Verlags

Invited Presentations.- Computational Processes in Living Cells: Gene Assembly in Ciliates.- Experimental Quantum Computation with Molecules.- Efficient Transformations from Regular Expressions to Finite Automata.- Extended Temporal Logic on Finite Words and Wreath Product of Monoids with Distinguished Generators.- A Remark about Quadratic Trace Equations.- Infinite Snake Tiling Problems.- Decision Problems for Linear and Circular Splicing Systems.- Finite Automata Models of Quantized Systems: Conceptual Status and Outlook.- Automata on Linear Orderings.- Contributions.- Some Properties of Ciliate Bio-operations.- On the Descriptional Complexity of Some Variants of Lindenmayer Systems.- Carriers and Counters.- On the Separation between k-Party and (k - 1)-Party Nondeterministic Message Complexities.- Unary Language Operations and Their Nondeterministic State Complexity.- Constructing Infinite Words of Intermediate Complexity.- A Space Lower Bound of Two-Dimensional Probabilistic Turing Machines.- Undecidability of Weak Bisimilarity for PA-Processes.- Improved Bounds on the Number of Automata Accepting Finite Languages.- Roots and Powers of Regular Languages.- Innermost Termination of Context-Sensitive Rewriting.- A Unique Structure of Two-Generated Binary Equality Sets.- On Deterministic Finite Automata and Syntactic Monoid Size.- An Inverse Automata Algorithm for Recognizing 2-Collapsing Words.- Efficient Algorithm for Checking Multiplicity Equivalence for the Finite Z - ?*-Automata.- Some Remarks on Asynchronous Automata.- Tiling Systems over Infinite Pictures and Their Acceptance Conditions.- The Average Lengths of the Factors of the Standard Factorization of Lyndon Words.- Circular Words Avoiding Patterns.- Safety Verification for Two-Way Finite Automata withMonotonic Counters.- An Infinite Prime Sequence Can Be Generated in Real-Time by a 1-Bit Inter-cell Communication Cellular Automaton.- On the Structure of Graphic DLI-Sets.- Finite Completion of Comma-Free Codes. Part I.- On a Family of Codes with Bounded Deciphering Delay.- Abstract Families of Graphs.- Automaton Representation of Linear Conjunctive Languages.- On-Line Odometers for Two-Sided Symbolic Dynamical Systems.- Characteristic Semigroups of Directable Automata.

• Reihe: Lecture Notes in Computer Science
• Themen: Informatik und Informationstechnologie Informatik Theoretische Informatik Mathematik für Informatiker
• ISBN: 9783540404316
• Sprache: Englisch
• Erscheinungsdatum: 20.06.2003
• Größe: 235 x 155 mm
• Verlag: Springer
• Herausgegeben von: Masafumi Toyama, Masami Ito