Developments in Language Theory : 7th International Conference, DLT 2003, Szeged, Hungary, July 7-11, 2003 - Proceedings

by Esik, Zoltan; Fulop, Zoltan

• ISBN13: 9783540404347
• ISBN10: 3540404341
• Format: Paperback
• Copyright: 2003-07-01
• Publisher: Springer Verlag

Summary

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.

Table of Contents

Invited Presentations
Quantum Computing: 1-Way Quantum Automata	1	(20)
Alberto Bertoni
Carlo Mereghetti
Beatrice Palano
An Automata-Theoretic Approach to Software Verification	21	(1)
Javier Esparza
Comments on Complete Sets of Tree Automata	22	(13)
Ferenc Gecseg
On a Conjecture of Schnoebelen	35	(20)
Antonio Cano Gomez
Jean-Eric Pin
Restarting Automata and Their Relations to the Chomsky Hierarchy	55	(20)
Friedrich Otto
Test Sets for Large Families of Languages	75	(20)
Wojciech Plandowski
Complexity Theory Made Easy	95	(16)
Heribert Vollmer
Contributions
Synchronizing Monotonic Automata	111	(11)
Dimitry S. Ananichev
Mikhail V. Volkov
Covering Problems from a Formal Language Point of View	122	(12)
Marcella Anselmo
Maria Madonia
Regular Languages Generated by Reflexive Finite Splicing Systems	134	(12)
Paola Bonizzoni
Clelia De Felice
Giancarlo Mauri
Rosalba Zizza
The Myhill-Nerode Theorem for Recognizable Tree Series	146	(13)
Bjorn Borchardt
Generating Series of the Trace Group	159	(12)
Anne Bouillard
Jean Mairesse
Residual Finite Tree Automata	171	(12)
Julien Carme
Remi Gilleron
Aurelien Lemay
Alain Terlutte
Marc Tommasi
From Glushkov WFAs to Rational Expressions	183	(11)
Pascal Caron
Marianne Flouret
NFA Reduction Algorithms by Means of Regular Inequalities	194	(12)
Jean-Marc Champarnaud
Fabien Coulon
Tile Rewriting Grammars	206	(12)
Stefano Crespi Reghizzi
Matteo Pradella
Distributed Pushdown Automata Systems: Computational Power	218	(12)
Erzsebet Csuhaj-Varju
Victor Mitrana
Gyorgy Vaszil
On Well Quasi-orders on Languages	230	(12)
Flavio D'Alessandro
Stefano Varricchio
Frequency of Symbol Occurrences in Simple Non-primitive Stochastic Models	242	(12)
Diego de Falco
Massimiliano Goldwurm
Violetta Lonati
On Enumeration of Muller Automata	254	(12)
Michael Domaratzki
Branching Grammars: A Generalization of ETOL Systems	266	(13)
Frank Drewes
Joost Engelfriet
Learning a Regular Tree Language from a Teacher	279	(13)
Frank Drewes
Johanna Hogberg
On Three Classes of Automata-Like P Systems	292	(12)
Rudolf Freund
Carlos Martin-Vide
Adam Obtulowicz
Gheorghe Paun
Computing Languages by (Bounded) Local Sets	304	(12)
Dora Giammarresi
About Duval's Conjecture	316	(9)
Tero Harju
Dirk Nowotka
Computation with Absolutely No Space Overhead	325	(12)
Lane A. Hemaspaandra
Proshanto Mukherji
Till Tantau
Deleting String Rewriting Systems Preserve Regularity	337	(12)
Dieter Hofbauer
Johannes Waldmann
On Deterministic Finite Automata and Syntactic Monoid Size, Continued	349	(12)
Markus Holzer
Barbara Konig
Flip-Pushdown Automata: Nondeterminism is Better than Determinism	361	(12)
Markus Holzer
Martin Kutrib
Deciding the Sequentiality of a Finitely Ambiguous Max-Plus Automaton	373	(13)
Ines Klimann
Sylvain Lombardy
Jean Mairesse
Christophe Prieur
Minimizing Finite Automata Is Computationally Hard	386	(12)
Andreas Malcher
Boolean Grammars	398	(13)
Alexander Okhotin
Syntactic Semiring and Universal Automation	411	(12)
Libor Polak
Alphabetic Pushdown Tree Transducers	423	(14)
George Rahonis
Author Index	437