This book constitutes the refereed proceedings of the 7th International Conference on Developments in Language Theory, DLT 2003, held in Szeged, Hungary, in July 2003.
The 27 revised full papers presented together with 7 invited papers were carefully reviewed and selected from 57 submissions. All current aspects in language theory are addressed, in particular grammars, acceptors, and transducers for strings, trees, graphs, arrays, etc; algebraic theories for automata and languages; combinatorial properties of words and languages; formal power series; decision problems; efficient algorithms for automata and languages; and relations to complexity theory and logic, picture description and analysis, DNA computing, quantum computing, cryptography, and concurrency.
Author(s): Alberto Bertoni, Carlo Mereghetti, Beatrice Palano (auth.), Zoltán Ésik, Zoltán Fülöp (eds.)
Series: Lecture Notes in Computer Science 2710
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2003
Language: English
Pages: 436
Tags: Mathematical Logic and Formal Languages; Computation by Abstract Devices; Logics and Meanings of Programs; Discrete Mathematics in Computer Science
Quantum Computing: 1-Way Quantum Automata....Pages 1-20
An Automata-Theoretic Approach to Software Verification....Pages 21-21
Comments on Complete Sets of Tree Automata....Pages 22-34
On a Conjecture of Schnoebelen....Pages 35-54
Restarting Automata and Their Relations to the Chomsky Hierarchy....Pages 55-74
Test Sets for Large Families of Languages....Pages 75-94
Complexity Theory Made Easy....Pages 95-110
Synchronizing Monotonic Automata....Pages 111-121
Covering Problems from a Formal Language Point of View....Pages 122-133
Regular Languages Generated by Reflexive Finite Splicing Systems....Pages 134-145
The Myhill-Nerode Theorem for Recognizable Tree Series....Pages 146-158
Generating Series of the Trace Group....Pages 159-170
Residual Finite Tree Automata....Pages 171-182
From Glushkov WFAs to Rational Expressions....Pages 183-193
NFA Reduction Algorithms by Means of Regular Inequalities....Pages 194-205
Tile Rewriting Grammars....Pages 206-217
Distributed Pushdown Automata Systems: Computational Power....Pages 218-229
On Well Quasi-orders on Languages....Pages 230-241
Frequency of Symbol Occurrences in Simple Non-primitive Stochastic Models....Pages 242-253
On Enumeration of Müller Automata....Pages 254-265
Branching Grammars: A Generalization of ET0L Systems....Pages 266-278
Learning a Regular Tree Language from a Teacher....Pages 279-291
On Three Classes of Automata-Like P Systems....Pages 292-303
Computing Languages by (Bounded) Local Sets....Pages 304-315
About Duval’s Conjecture....Pages 316-324
Computation with Absolutely No Space Overhead....Pages 325-336
Deleting String Rewriting Systems Preserve Regularity....Pages 337-348
On Deterministic Finite Automata and Syntactic Monoid Size, Continued....Pages 349-360
Flip-Pushdown Automata: Nondeterminism is Better than Determinism....Pages 361-372
Deciding the Sequentiality of a Finitely Ambiguous Max-Plus Automaton....Pages 373-385
Minimizing Finite Automata Is Computationally Hard....Pages 386-397
Boolean Grammars....Pages 398-410
Syntactic Semiring and Universal Automaton....Pages 411-422
Alphabetic Pushdown Tree Transducers....Pages 423-436
