Published: 30th July 2009|
|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|
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
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:
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