This book constitutes the refereed proceedings of the 12th International Conference on Developments in Language Theory, DLT 2008, held in Kyoto, Japan, September 2008.
The 36 revised full papers presented together with 6 invited papers were carefully reviewed and selected from 102 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; bio-inspired computing; quantum computing.
Author(s): Zoltán Ésik (auth.), Masami Ito, Masafumi Toyama (eds.)
Series: Lecture Notes in Computer Science 5257 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2008
Language: English
Pages: 544
Tags: Mathematical Logic and Formal Languages; Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Symbolic and Algebraic Manipulation
Front Matter....Pages -
Iteration Semirings....Pages 1-20
Various Aspects of Finite Quantum Automata....Pages 21-33
On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes....Pages 34-55
Selected Ideas Used for Decidability and Undecidability of Bisimilarity....Pages 56-71
The Frobenius Problem and Its Generalizations....Pages 72-83
Well Quasi-orders in Formal Language Theory....Pages 84-95
On the Non-deterministic Communication Complexity of Regular Languages....Pages 96-107
General Algorithms for Testing the Ambiguity of Finite Automata....Pages 108-120
Emptiness of Multi-pushdown Automata Is 2ETIME-Complete....Pages 121-133
The Average State Complexity of the Star of a Finite Set of Words Is Linear....Pages 134-145
On the Computational Capacity of Parallel Communicating Finite Automata....Pages 146-157
On a Generalization of Standard Episturmian Morphisms....Pages 158-169
Universal Recursively Enumerable Sets of Strings....Pages 170-182
Algorithmically Independent Sequences....Pages 183-195
Relationally Periodic Sequences and Subword Complexity....Pages 196-205
Bounds on Powers in Strings....Pages 206-215
When Is Reachability Intrinsically Decidable?....Pages 216-227
Some New Modes of Competence-Based Derivations in CD Grammar Systems....Pages 228-239
The Synchronization Problem for Strongly Transitive Automata....Pages 240-251
On the Decidability of the Equivalence for k -Valued Transducers....Pages 252-263
Decidable Properties of 2D Cellular Automata....Pages 264-275
Fixed Point and Aperiodic Tilings....Pages 276-288
Extended Multi Bottom-Up Tree Transducers....Pages 289-300
Derivation Tree Analysis for Accelerated Fixed-Point Computation....Pages 301-313
Tree Automata with Global Constraints....Pages 314-326
Bad News on Decision Problems for Patterns....Pages 327-338
Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time....Pages 339-358
More Concise Representation of Regular Languages by Automata and Regular Expressions....Pages 359-370
A Taxonomy of Deterministic Forgetting Automata....Pages 371-382
Provably Shorter Regular Expressions from Deterministic Finite Automata....Pages 383-395
Large Simple Binary Equality Words....Pages 396-407
On the Relation between Periodicity and Unbordered Factors of Finite Words....Pages 408-418
Duplication in DNA Sequences....Pages 419-430
On the State Complexity of Complements, Stars, and Reversals of Regular Languages....Pages 431-442
On the State Complexity of Operations on Two-Way Finite Automata....Pages 443-454
On the Size Complexity of Rotating and Sweeping Automata....Pages 455-466
An Analysis and a Reproof of Hmelevskii’s Theorem....Pages 467-478
Hierarchies of Piecewise Testable Languages....Pages 479-490
Construction of Tree Automata from Regular Expressions....Pages 491-503
Balance Properties and Distribution of Squares in Circular Words....Pages 504-515
MSO Logic for Unambiguous Shared-Memory Systems....Pages 516-528
Complexity of Topological Properties of Regular ω -Languages....Pages 529-542
Back Matter....Pages -
