Developments in Language Theory

10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006, Proceedings

476 Seiten, Taschenbuch

Kurzbeschreibung des Verlags

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 NondeterministicState 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.

• Reihe: Lecture Notes in Computer Science
• Themen: Informatik und Informationstechnologie Informatik Theoretische Informatik Mathematik für Informatiker
• ISBN: 9783540354284
• Sprache: Englisch
• Erscheinungsdatum: 21.06.2006
• Größe: 235 x 155 mm
• Verlag: Springer
• Herausgegeben von: Zhe Dang, Oscar H. Ibarra