Program

 for printing:

Sunday, July 5
16:00 – 20:00 Registration and Reception (Snacks and Drinks)



Monday, July 6
08:30 – 09:15 Registration
09:15 – 09:30 Opening
09:30 – 10:30 Invited talk
Janusz A. Brzozowski (Waterloo, Canada):
Quotient Complexity of Regular Languages
10:30 – 11:00 Coffee Break
11:00 – 11:30 Martin Kutrib (Giessen, Germany) and Andreas Malcher (Giessen, Germany):
Bounded Languages Meet Cellular Automata with Sparse Communication
11:30 – 12:00 Fevzi Belli (Paderborn, Germany) and Mutlu Beyazit (Paderborn, Germany):
Mutation of Directed Graphs – Corresponding Regular Expressions and Complexity of Their Generation
12:00 – 14:00 Lunch
14:00 – 14:30 Rudolf Freund (Vienna, Austria), Andreas Klein (Ghent, Belgium), and Martin Kutrib (Giessen, Germany):
On the Number of Membranes in Unary P Systems
14:30 – 15:00 Pierre-Yves Angrand (Paris, France), Sylvain Lombardy (Paris, France), and Jacques Sakarovitch (Paris, France):
On the Number of Broken Derived Terms of a Rational Expression
15:00 – 15:30 Marco Almeida (Porto, Portugal), Nelma Moreira (Porto, Portugal), and Rogério Reis (Porto, Portugal):
Testing the Equivalence of Regular Languages
15:30 – 16:00 Coffee Break
16:00 – 16:30 Franziska Biegler (London, Canada), Mark Daley (London, Canada), and Ian McQuillan (Saskatoon, Canada):
On the Shuffle Automaton Size for Words
16:30 – 17:00 Galina Jirásková (Košice, Slovakia) and Alexander Okhotin (Turku, Finland):
Nondeterministic State Complexity of Positional Addition
17:00 – 17:30 Viliam Geffert (Košice, Slovakia) and Lubomíra Ištoňová (Košice, Slovakia):
Translation from Classical Two-Way Automata to Pebble Two-Way Automata



Tuesday, July 7
09:00 – 10:00 Invited talk
Christel Baier (Dresden, Germany):
Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability
10:00 – 10:30 Coffee Break
10:30 – 11:00 Remco Loos (Cambridge, United Kingdom), Florin Manea (Bucharest, Romania), and Victor Mitrana (Valencia, Spain):
Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections
11:00 – 11:30 Erzsébet Csuhaj-Varjú (Budapest, Hungary) and György Vaszil (Budapest, Hungary):
On the Size Complexity of Non-Returning Context-Free PC Grammar Systems
11:30 – 12:00 M. Sakthi Balan (Bangalore, India):
Serializing the Parallelism in Parallel Communicating Pushdown Automata Systems
12:00 – 14:00 Lunch
14:00 – 15:00 Jürgen Dassow:
Ten Years DCFS
15:00 – 15:30 Discussion / Open Problem Session / Stimulations
15:30 – 15:50 Coffee Break
15:50 – 16:30 Business Meeting of Working Group Descriptional Complexity
17:00 Visit of the Cathedral



Wednesday, July 8
09:00 – 10:00 Invited talk
Nicole Schweikardt (Frankfurt/Main, Germany):
The Descriptional Complexity of Fragments of Monadic Second-Order Logic
10:00 – 10:30 Coffee Break
10:30 – 11:00 Pierluigi Frisco (Edinburgh, United Kingdom) and Oscar H. Ibarra (Santa Barbara, USA):
On Languages Accepted by P/T systems Composed of Joins
11:00 – 11:30 Ralf Stiebe (Magdeburg, Germany) and Sherzod Turaev (Tarragona, Spain):
Capacity Bounded Grammars and Petri Nets
11:30 – 13:00 Lunch
13:00 – 21:00 Excursion to Tangermünde (1000 years old town, partly looking like a medieval town), to the monastery in Jerichow (late Romanesque style), to the canal bridge (Europe's longest aquaeduct – Midland canal crossing river Elbe) and Conference Dinner in Hohenwarthe



Thursday, July 9
09:00 – 10:00 Invited talk
Andrei Păun (Bucharest, Romania):
The Nondeterministic Waiting Time Algorithm: A Review
10:00 – 10:30 Coffee Break
10:30 – 11:00 Tomáš Masopust (Brno, Czech Republic) and Alexander Meduna (Brno, Czech Republic):
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
11:00 – 11:30 Hermann Gruber (Giessen, Germany), Markus Holzer (Giessen, Germany), and Martin Kutrib (Giessen, Germany):
On Measuring Non-Recursive Trade-Offs
11:30 – 12:00 Yuan Gao (London, Canada) and Sheng Yu (London, Canada):
State Complexity Approximation
12:00 – 12:15 Closing