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
Descriptional Complexity of Formal Systems (DCFS) is the successor workshop and the
merger of two related workshops,
Descriptional Complexity of Automata, Grammars and Related
Structures (DCAGRS) and
Formal Descriptions and Software Reliability (FDSR).
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
- Christel Baier (Dresden, Germany)
- Janusz A. Brzozowski (Waterloo, Ontario, Canada)
- Andrei Păun (Ruston, USA; Madrid, Spain)
- Nicole Schweikardt (Frankfurt/Main, Germany)
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:
- Cezar Câmpeanu (Charlottetown, PE, Canada)
- Jean-Marc Champarnaud (Rouen, France)
- Erzsébet Csuhaj-Varjú (Budapest, Hungary)
- Jürgen Dassow (Magdeburg, Germany) Co-Chair
- Viliam Geffert (Košice, Slovakia)
- Alexander Okhotin (Turku, Finland)
- Giovanni Pighizzini (Milano, Italy) Co-Chair
- Jeffrey O. Shallit (Waterloo, ON, Canada)
- Bianca Truthe (Magdeburg, Germany)
- Detlef Wotschke (Frankfurt/Main, Germany)
We also thank the additional reviewers for their careful evaluation:
- Michael Domaratzki
- Dominik D. Freydenberger
- Jonathan Goldstine
- Artur Jeż
- Galina Jirásková
- Hing Leung
- Andreas Malcher
- Carlo Mereghetti
- Ludovic Mignot
- Faissal Ouardi
- Beatrice Palano
- György Vaszil
- Frank Weinberg
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