Developments in Language Theory: 12th International Conference, DLT 2008, Kyoto, Japan, September 16-19, 2008, Proceedings

Front Cover
Springer Science & Business Media, Sep 4, 2008 - Computers - 544 pages

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.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Iteration Semirings
1
Various Aspects of Finite Quantum Automata
21
On the Hardness of Determining Small NFAs and of Proving Lower Bounds on Their Sizes
34
Selected Ideas Used for Decidability and Undecidability of Bisimilarity
56
The Frobenius Problem and Its Generalizations
72
Well Quasiorders in Formal Language Theory
84
On the Nondeterministic Communication Complexity of Regular Languages
96
General Algorithms for Testing the Ambiguity of Finite Automata
108
Extended Multi BottomUp Tree Transducers
289
Derivation Tree Analysis for Accelerated FixedPoint Computation
301
Tree Automata with Global Constraints
314
Bad News on Decision Problems for Patterns
327
Finding the Growth Rate of a Regular of ContextFree Language in Polynomial Time
339
More Concise Representation of Regular Languages by Automata and Regular Expressions
359
A Taxonomy of Deterministic Forgetting Automata
371
Provably Shorter Regular Expressions from Deterministic Finite Automata
383

Emptiness of Multipushdown Automata Is 2ETIMEComplete
121
The Average State Complexity of the Star of a Finite Set of Words Is Linear
134
On the Computational Capacity of Parallel Communicating Finite Automata
146
On a Generalization of Standard Episturmian Morphisms
158
Universal Recursively Enumerable Sets of Strings
170
Algorithmically Independent Sequences
183
Relationally Periodic Sequences and Subword Complexity
196
Bounds on Powers in Strings
206
When Is Reachability Intrinsically Decidable?
216
Some New Modes of CompetenceBased Derivations in CD Grammar Systems
228
The Synchronization Problem for Strongly Transitive Automata
240
On the Decidability of the Equivalence for kValued Transducers
252
Decidable Properties of 2D Cellular Automata
264
Fixed Point and Aperiodic Tilings
276
Large Simple Binary Equality Words
396
On the Relation between Periodicity and Unbordered Factors of Finite Words
408
Duplication in DNA Sequences
419
On the State Complexity of Complements Stars and Reversals of Regular Languages
431
On the State Complexity of Operations on TwoWay Finite Automata
443
On the Size Complexity of Rotating and Sweeping Automata
455
An Analysis and a Reproof of Hmelevskiis Theorem
467
Hierarchies of Piecewise Testable Languages
479
Construction of Tree Automata from Regular Expressions
491
Balance Properties and Distribution of Squares in Circular Words
504
MSO Logic for Unambiguous SharedMemory Systems
516
Complexity of Topological Propertiesof Regular omegaLanguages
529
Author Index
543
Copyright

Other editions - View all

Common terms and phrases