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

Ibarra, Oscar H.; Dang, Zhe

Brossura

ISBN 10: 354035428X ISBN 13: 9783540354284

Casa editrice: Springer, 2008

Riassunto

This book constitutes the refereed proceedings of the 10th International Conference on Developments in Language Theory, DLT 2006, held in Santa Barbara, CA, June 2006. The book presents 36 revised full papers together with 4 invited papers. 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; and more.

Su questo libro

Contenuti

Invited Lectures.- Adding Nesting Structure to Words.- Can Abstract State Machines Be Useful in Language Theory?.- Languages in Membrane Computing: Some Details for Spiking Neural P Systems.- Computational Nature of Biochemical Reactions.- Papers.- Polynomials, Fragments of Temporal Logic and the Variety DA over Traces.- Weighted Automata and Weighted Logics on Infinite Words.- Simulation Relations for Alternating Parity Automata and Parity Games.- Equivalence of Functions Represented by Simple Context-Free Grammars with Output.- On the Gap-Complexity of Simple RL-Automata.- Noncanonical LALR(1) Parsing.- Context-Free Grammars and XML Languages.- Synchronization of Pushdown Automata.- Context-Dependent Nondeterminism for Pushdown Automata.- Prime Decompositions of Regular Languages.- On Weakly Ambiguous Finite Transducers.- Ciliate Bio-operations on Finite String Multisets.- Characterizing DNA Bond Shapes Using Trajectories.- Involution Solid and Join Codes.- Well-Founded Semantics for Boolean Grammars.- Hierarchies of Tree Series Transformations Revisited.- Bag Context Tree Grammars.- Closure of Language Classes Under Bounded Duplication.- The Boolean Closure of Growing Context-Sensitive Languages.- Well Quasi Orders and the Shuffle Closure of Finite Sets.- The Growth Ratio of Synchronous Rational Relations Is Unique.- On Critical Exponents in Fixed Points of Non-erasing Morphisms.- P Systems with Proteins on Membranes and Membrane Division.- Computing by Only Observing.- A Decision Procedure for Reflexive Regular Splicing Languages.- Contextual Hypergraph Grammars – A New Approach to the Generation of Hypergraph Languages.- End-Marked Maximal Depth-First Contextual Grammars.- Some Examples of Semi-rational DAG Languages.- Finding Lower Bounds for Nondeterministic State Complexity Is Hard.- Lowering Undecidability Bounds for Decision Questions in Matrices.- Complexity of Degenerated Three Dimensional Billiard Words.- Factorial Languages of Low Combinatorial Complexity.- Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy.- Language Equations with Complementation.- Synchronizing Automata with a Letter of Deficiency 2.- On Some Variations of Two-Way Probabilistic Finite Automata Models.

Product Description

Book by None

Dettagli dell'edizione

• Editore: Springer
• Data di pubblicazione: 2008
• Lingua: Inglese
• ISBN 10: 354035428X
• ISBN 13: 9783540354284
• Rilegatura: Copertina flessibile
• Numero di pagine: 476
• Contatto del produttore: ProductSafety@springernature.com; ProductSafety@springernature.com; ; Tiergartenstr. 17; Heidelberg; 69121; Germania