This book constitutes the refereed proceedings of the 10th International Conference on Developments in Language Theory, DLT 2006, held in Santa Barbara, CA, USA in June 2006.
The 36 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 63 submissions. All important issues in language theory are addressed including grammars, acceptors and transducers for strings, trees, graphs, arrays; efficient text algorithms; algebraic theories for automata and languages; combinatorial and algebraic properties of words and languages; variable-length codes; symbolic dynamics; decision problems; relations to complexity theory and logic; picture description and analysis; polyominoes and bi-dimensional patterns; cryptography; concurrency; bio-inspired computing; and quantum computing.
Author(s): Rajeev Alur, P. Madhusudan (auth.), Oscar H. Ibarra, Zhe Dang (eds.)
Series: Lecture Notes in Computer Science 4036 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2006
Language: English
Pages: 456
Tags: Mathematical Logic and Formal Languages; Computation by Abstract Devices; Logics and Meanings of Programs; Discrete Mathematics in Computer Science; Symbolic and Algebraic Manipulation
Front Matter....Pages -
Adding Nesting Structure to Words....Pages 1-13
Can Abstract State Machines Be Useful in Language Theory?....Pages 14-19
Languages in Membrane Computing: Some Details for Spiking Neural P Systems....Pages 20-35
Computational Nature of Biochemical Reactions....Pages 36-36
Polynomials, Fragments of Temporal Logic and the Variety DA over Traces....Pages 37-48
Weighted Automata and Weighted Logics on Infinite Words....Pages 49-58
Simulation Relations for Alternating Parity Automata and Parity Games....Pages 59-70
Equivalence of Functions Represented by Simple Context-Free Grammars with Output....Pages 71-82
On the Gap-Complexity of Simple RL-Automata....Pages 83-94
Noncanonical LALR(1) Parsing....Pages 95-107
Context-Free Grammars and XML Languages....Pages 108-119
Synchronization of Pushdown Automata....Pages 120-132
Context-Dependent Nondeterminism for Pushdown Automata....Pages 133-144
Prime Decompositions of Regular Languages....Pages 145-155
On Weakly Ambiguous Finite Transducers....Pages 156-167
Ciliate Bio-operations on Finite String Multisets....Pages 168-179
Characterizing DNA Bond Shapes Using Trajectories....Pages 180-191
Involution Solid and Join Codes....Pages 192-202
Well-Founded Semantics for Boolean Grammars....Pages 203-214
Hierarchies of Tree Series Transformations Revisited....Pages 215-225
Bag Context Tree Grammars ....Pages 226-237
Closure of Language Classes Under Bounded Duplication....Pages 238-247
The Boolean Closure of Growing Context-Sensitive Languages....Pages 248-259
Well Quasi Orders and the Shuffle Closure of Finite Sets....Pages 260-269
The Growth Ratio of Synchronous Rational Relations Is Unique....Pages 270-279
On Critical Exponents in Fixed Points of Non-erasing Morphisms....Pages 280-291
P Systems with Proteins on Membranes and Membrane Division....Pages 292-303
Computing by Only Observing....Pages 304-314
A Decision Procedure for Reflexive Regular Splicing Languages....Pages 315-326
Contextual Hypergraph Grammars – A New Approach to the Generation of Hypergraph Languages....Pages 327-338
End-Marked Maximal Depth-First Contextual Grammars....Pages 339-350
Some Examples of Semi-rational DAG Languages....Pages 351-362
Finding Lower Bounds for Nondeterministic State Complexity Is Hard....Pages 363-374
Lowering Undecidability Bounds for Decision Questions in Matrices....Pages 375-385
Complexity of Degenerated Three Dimensional Billiard Words....Pages 386-396
Factorial Languages of Low Combinatorial Complexity....Pages 397-407
Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy....Pages 408-419
Language Equations with Complementation....Pages 420-432
Synchronizing Automata with a Letter of Deficiency 2....Pages 433-442
On Some Variations of Two-Way Probabilistic Finite Automata Models....Pages 443-454
Back Matter....Pages -
