Gao / Lu / Seki Developments in Language Theory

14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010, Proceedings
Erscheinungsjahr 2010
ISBN: 978-3-642-14455-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 6224, 446 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Zielgruppe

Research

Autoren/Hrsg.

Gao, Yuan

Lu, Hanlin

Seki, Shinnosuke

Yu, Sheng

Inhaltsverzeichnis

Invited Talks.- Reaction Systems: A Model of Computation Inspired by Biochemistry.- A Brief Excursion Inside the Class of Tiling Recognizable Two-Dimensional Languages.- The Complexity of Regular(-Like) Expressions.- On Decision Problems for Simple and Parameterized Machines.- DNA Computing and Its Implications for Theoretical Computer Science.- Numeration Systems: A Link between Number Theory and Formal Language Theory.- Regular Papers.- Algorithmic Properties of Millstream Systems.- On a Conjecture by Carpi and D’Alessandro.- Linking Algebraic Observational Equivalence and Bisimulation.- Undecidability and Hierarchy Results for Parallel Communicating Finite Automata.- Inclusion Problems for Patterns with a Bounded Number of Variables.- On the Average Number of States of Partial Derivative Automata.- On the Hybrid ?erný-Road Coloring Problem and Hamiltonian Paths.- Computing Blocker Sets for the Regular Post Embedding Problem.- Rankers over Infinite Words.- Kleene and Büchi Theorems for Weighted Automata and Multi-valued Logics over Arbitrary Bounded Lattices.- On Müller Context-Free Grammars.- Minimization of Deterministic Bottom-Up Tree Transducers.- Two-Way Unary Automata versus Logarithmic Space.- On the Periodicity of Morphic Words.- Compressed Conjugacy and the Word Problem for Outer Automorphism Groups of Graph Groups.- Using Light to Implement Parallel Boolean Algebra.- Periodicity in Tilings.- Complexity in Union-Free Regular Languages.- Schema for Parallel Insertion and Deletion.- On Schützenberger Products of Semirings.- On Language Equations XXK?=?XXL and XM?=?N over a Unary Alphabet.- Around Dot Depth Two.- Input Products for Weighted Extended Top-Down Tree Transducers.- Regular Hedge Language Factorization Revisited.- Fast Parsing forBoolean Grammars: A Generalization of Valiant’s Algorithm.- On Lexicalized Well-Behaved Restarting Automata That Are Monotone.- On a Powerful Class of Non-universal P Systems with Active Membranes.- State Complexity of Prefix, Suffix, Bifix and Infix Operators on Regular Languages.- Restricted Ambiguity of Erasing Morphisms.- Automata with Extremal Minimality Conditions.- On the Existence of Minimal ?-Powers.- The Averaging Trick and the ?erný Conjecture.- Short Papers.- Pseudo-power Avoidance.- On Restricted Context-Free Grammars.- Graphs Capturing Alternations in Words.- On the Iterated Hairpin Completion.- On Lookahead Hierarchies for Monotone and Deterministic Restarting Automata with Auxiliary Symbols (Extended Abstract).- Joint Topologies for Finite and Infinite Words.