Developments in Language Theory : 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006, Proceedings

by Ibarra, Oscar H.; Dang, Zhe

• ISBN13: 9783540354284
• ISBN10: 354035428X
• Format: Paperback
• Copyright: 2006-07-15
• Publisher: Springer Verlag

Summary

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 bidimensional patterns; cryptography; concurrency; bio-inspired computing; and quantum computing.

Table of Contents

Adding nesting structure to words	p. 1
Can abstract state machines be useful in language theory?	p. 14
Languages in membrane computing : some details for spiking neural P systems	p. 20
Computational nature of biochemical reactions	p. 36
Polynomials, fragments of temporal logic and the variety DA over traces	p. 37
Weighted automata and weighted logics on infinite words	p. 49
Simulation relations for alternating parity automata and parity games	p. 59
Equivalence of functions represented by simple context-free grammars with output	p. 71
On the gap-complexity of simple RL-automata	p. 83
Noncanonical LALR(1) parsing	p. 95
Context-free grammars and XML languages	p. 108
Synchronization of pushdown automata	p. 120
Context-dependent nondeterminism for pushdown automata	p. 133
Prime decompositions of regular languages	p. 145
On weakly ambiguous finite transducers	p. 156
Ciliate bio-operations on finite string multisets	p. 168
Characterizing DNA bond shapes using trajectories	p. 180
Involution solid and join codes	p. 192
Well-founded semantics for boolean grammars	p. 203
Hierarchies of tree series transformations revisited	p. 215
Bag context tree grammars	p. 226
Closure of language classes under bounded duplication	p. 238
The boolean closure of growing context-sensitive languages	p. 248
Well quasi orders and the shuffle closure of finite sets	p. 260
The growth ratio of synchronous rational relations is unique	p. 270
On critical exponents in fixed points of non-erasing morphisms	p. 280
P systems with proteins on membranes and membrane division	p. 292
Computing by only observing	p. 304
A decision procedure for reflexive regular splicing languages	p. 315
Contextual hypergraph grammars - a new approach to the generation of hypergraph languages	p. 327
End-marked maximal depth-first contextual grammars	p. 339
Some examples of semi-rational DAG languages	p. 351
Finding lower bounds for nondeterministic state complexity is hard	p. 363
Lowering undecidability bounds for decision questions in matrices	p. 375
Complexity of degenerated three dimensional billiard words	p. 386
Factorial languages of low combinatorial complexity	p. 397
Perfect correspondences between dot-depth and polynomial-time hierarchy	p. 408
Language equations with complementation	p. 420
Synchronizing automata with a letter of deficiency 2	p. 433
On some variations of two-way probabilistic finite automata models	p. 443
Table of Contents provided by Blackwell. All Rights Reserved.