This book constitutes the thoroughly refereed post-proceedings of the 5th International Conference on Developments in Language Theory, DLT 2001, held in Vienna, Austria, in July 2001.
The 24 revised full papers presented together with 10 revised invited papers were carefully selected during two rounds of reviewing and revision from a total of 64 papers submitted. Among the topics covered are grammars and acceptors, efficient algorithms for languages, combinatorial and algebraic properties, decision problems, relations to complexity theory, logic, picture description and analysis, DNA computing, cryptography, and concurrency.
Author(s): Cristian S. Calude, Elena Calude (auth.), Werner Kuich, Grzegorz Rozenberg, Arto Salomaa (eds.)
Series: Lecture Notes in Computer Science 2295
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2002
Language: English
Pages: 389
Tags: Mathematical Logic and Formal Languages; Computation by Abstract Devices; Logics and Meanings of Programs; Discrete Mathematics in Computer Science
Automata: From Uncertainty to Quantum....Pages 1-14
Elementary Theory of Ordinals with Addition and Left Translation by ω....Pages 15-20
The Equational Theory of Fixed Points with Applications to Generalized Language Theory....Pages 21-36
Second-Order Logic over Strings: Regular and Non-regular Fragments....Pages 37-56
Decision Questions on Integer Matrices....Pages 57-68
Some Petri Net Languages and Codes....Pages 69-80
Words, Permutations, and Representations of Numbers....Pages 81-99
Proof Complexity of Pigeonhole Principles....Pages 100-116
Words and Patterns....Pages 117-129
A Short Introduction to Infinite Automata....Pages 130-144
The Power of One-Letter Rational Languages....Pages 145-154
The Entropy of Lukasiewicz-Languages....Pages 155-165
Collapsing Words vs. Synchronizing Words....Pages 166-174
A Note on Synchronized Automata and Road Coloring Problem....Pages 175-185
Shuffle Quotient and Decompositions....Pages 186-196
The Growing Context-Sensitive Languages Are the Acyclic Context-Sensitive Languages....Pages 197-205
Recognizable Sets of N-Free Pomsets Are Monadically Axiomatizable....Pages 206-216
Automata on Series-Parallel Biposets....Pages 217-227
Hierarchies of String Languages Generated by Deterministic Tree Transducers....Pages 228-238
Partially-Ordered Two-Way Automata: A New Characterization of DA....Pages 239-250
Level 5/2 of the Straubing-Thérien Hierarchy for Two-Letter Alphabets....Pages 251-261
On the Power of Randomized Pushdown Automata....Pages 262-271
The Root of a Language and Its Complexity....Pages 272-280
Valuated and Valence Grammars: An Algebraic View....Pages 281-292
Context-Free Valence Grammars - Revisited....Pages 293-303
An Undecidability Result Concerning Periodic Morphisms....Pages 304-310
A Universal Turing Machine with 3 States and 9 Symbols....Pages 311-318
Minimal Covers of Formal Languages....Pages 319-329
Some Regular Languages That Are Church-Rosser Congruential....Pages 330-339
On the Relationship between the McNaughton Families of Languages and the Chomsky Hierarchy....Pages 340-348
Forbidden Factors and Fragment Assembly....Pages 349-358
Parallel Communicating Grammar Systems with Incomplete Information Communication....Pages 359-368
Eliminating Communication by Parallel Rewriting....Pages 369-378
String Rewriting Sequential P-Systems and Regulated Rewriting....Pages 379-388
