Published: 30th July 2009
DOI: 10.4204/EPTCS.3
ISSN: 2075-2180

EPTCS 3

Proceedings Eleventh International Workshop on
Descriptional Complexity of Formal Systems
Magdeburg, Germany, July 6-9, 2009

Edited by: Jürgen Dassow, Giovanni Pighizzini and Bianca Truthe

Preface
Jürgen Dassow, Giovanni Pighizzini and Bianca Truthe
1
Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability
Christel Baier, Nathalie Bertrand and Marcus Größer
3
Quotient Complexity of Regular Languages
Janusz Brzozowski
17
The Nondeterministic Waiting Time Algorithm: A Review
John Jack and Andrei Păun
29
Testing the Equivalence of Regular Languages
Marco Almeida, Nelma Moreira and Rogério Reis
47
Serializing the Parallelism in Parallel Communicating Pushdown Automata Systems
M. Sakthi Balan
59
Mutation of Directed Graphs – Corresponding Regular Expressions and Complexity of Their Generation
Fevzi Belli and Mutlu Beyazit
69
On the Shuffle Automaton Size for Words
Franziska Biegler, Mark Daley and Ian McQuillan
79
On the Size Complexity of Non-Returning Context-Free PC Grammar Systems
Erzsébet Csuhaj-Varjú and György Vaszil
91
On the Number of Membranes in Unary P Systems
Rudolf Freund, Andreas Klein and Martin Kutrib
101
On Languages Accepted by P/T Systems Composed of joins
Pierluigi Frisco and Oscar H. Ibarra
111
State Complexity Approximation
Yuan Gao and Sheng Yu
121
Translation from Classical Two-Way Automata to Pebble Two-Way Automata
Viliam Geffert and Ľubomíra Ištoňová
131
On Measuring Non-Recursive Trade-Offs
Hermann Gruber, Markus Holzer and Martin Kutrib
141
Nondeterministic State Complexity of Positional Addition
Galina Jirásková and Alexander Okhotin
151
Bounded Languages Meet Cellular Automata with Sparse Communication
Martin Kutrib and Andreas Malcher
163
Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections
Remco Loos, Florin Manea and Victor Mitrana
173
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
Tomáš Masopust and Alexander Meduna
183
Capacity Bounded Grammars and Petri Nets
Ralf Stiebe and Sherzod Turaev
193

Preface

Descriptional Complexity of Formal Systems (DCFS) is the successor workshop and the merger of two related workshops, The workshops DCAGRS took place in Magdeburg, Germany (1999), London, Ontario, Canada (2000), and Vienna, Austria (2001), while the workshops FDSR took place in Paderborn, Germany (1998), Boca Raton, Florida, USA (1999), and San José, California, USA (2000). Finally, the workshops DCFS were previously held in London, Ontario, Canada (2002), Budapest, Hungary (2003), London, Ontario, Canada (2004), Como, Italy (2005), Las Cruces, New Mexico, USA (2006), Nový Smokovec, Slovakia (2007), and Charlottetown, Prince Edward Island, Canada (2008).

The 11th workshop, Descriptional Complexity of Formal Systems 2009, took place in Magdeburg, Germany, on July 6–9, 2009. It was jointly organized by the IFIP Working Group 1.2 on Descriptional Complexity and by the Faculty of Computer Science at the Otto von Guericke University Magdeburg.

This volume contains the papers of the invited lectures and the accepted contributions except for two presentations. The talks given in the discussion session are also not included.

As in the past, the workshop DCFS was a scientifically valuable event with very interesting discussions and has stimulated new investigations and scientific co-operation in the field of the descriptional complexity.

Special thanks go to the invited speakers

for accepting our invitation and presenting their recent results at DCFS 2009.

Papers were submitted by a total of 38 authors from 15 different countries. From these submissions, on the basis of three referee reports each, the Program Committee selected 16 papers. We thank the members of the Program Committee for their excellent work in making this selection:

We also thank the additional reviewers for their careful evaluation:

As in previous years, a special journal issue will be devoted to DCFS. Full versions of selected papers are eligible for publication in a special issue of the Journal of Automata, Languages and Combinatorics (after the standard refereeing process).

We are grateful to the Organizing Committee consisting of Catharina Berner, Jürgen Dassow (Chair), Ronny Harbich, Bernd Reichel, and Bianca Truthe as well as to the technicians Jens Elkner, Susanne Pape, Michael Preuß, and Jürgen Schymaniuk for their support of the sessions, the excursion and the other accompanying events.

We would also like to thank EPTCS, in particular Rob van Glabbeek and Lane A. Hemaspaandra, for accepting to publish these proceedings and for their help during the preparation.

Jürgen Dassow, Giovanni Pighizzini, and Bianca Truthe
Magdeburg and Milano, July 2009