# Invited Speakers

- Jarkko Kari (Turku, Finland)
**Linear Algebra based Bounds for One-dimensional Cellular Automata.**A relevant complexity measure for a cellular automaton is the size of its neighborhood. If a cellular automaton is reversible with a small neighborhood, the inverse automaton may need a much larger neighborhood. Our interest is to find good upper bounds for the size of this inverse neighborhood. It turns out that a linear algebra approach provides better bounds than any known combinatorial methods. In fact, the obtained bounds are optimal. We also consider cellular automata that are not surjective. In this case there must exist so-called orphans, finite patterns without a pre-image. The length of the shortest orphan measures the degree of non-surjectiveness of the map. Again, a linear algebra approach provides better bounds on this length than known combinatorial methods. We also use linear algebra to bound the minimum lengths of any diamond and any word with a non-balanced number of pre-images. These both exist when the cellular automaton in question is not surjective. All our results deal with one-dimensional cellular automata. Undecidability results imply that in higher dimensional cases no computable upper bound exists for any of the considered quantities.

- Friedrich Otto (Kassel, Germany)
**On Restarting Automata with Window Size One.**The*restarting automaton*is a machine model that is motivated by the technique of*analysis by reduction*from linguistics. It consists of a finite-state control and a flexible type with end markers and a read/write window of a fixed size. This talk begins with a short description of the general model of the restarting automaton and its major variants. In particular, the influence that the size of the*read/write window*has on the expressive power of the various types of restarting automata is discussed. The main part of the talk then focuses on the weakest model of the restarting automaton: the so-called*R-automaton*with a read/write window of size one (R(1)-automaton for short). It is well-known that R(1)-automata only accept regular languages, but it will be shown that several seemingly rather powerful variants have the same expressive power only. Accordingly it is of interest to study the descriptional complexity of these types of restarting automata in relation to the R(1)-automata on the one hand and the (deterministic and nondeterministic) finite-state acceptors on the other hand. Then various types of cooperating distributed systems (CD-systems) of deterministic R(1)-automata are presented. If all components of such a system are stateless, then the language accepted by the system has a semi-linear Parikh image, and actually the rational trace languages and the context-free trace languages have been characterized in terms of certain CD-systems of stateless deterministic R(1)-automata. However, if the components of such a CD-system are not stateless, then these systems are strictly more expressive, as then they even accept some languages that are not semi-linear. Also for these devices the question about their descriptional complexity will be addressed in short.

- Stefan Schwoon (Cachan, France)
**Efficiently Unfolding Contextual Petri Nets.**Unfoldings are a useful tool for analyzing Petri nets. They are a means to reduce state-space explosion, describing the possible behaviours more succinctly than the reachability graph by exploiting the concurrency inherent in a Petri net. However, Petri nets are not well-suited to model concurrent read accesses to the same resource, that is, if multiple actions at the same time require non-exclusive access to one common resource. Consequently, the unfolding technique becomes inefficient in the presence of such situations. Contextual nets, which explicitly do model concurrent read accesses, address this problem. Their accurate representation of concurrency makes contextual unfoldings up to exponentially smaller in the presence of multiple readers, but their construction becomes more complicated. The talk, which represents joint work with César Rodríguez, Paolo Baldan, and others, will present this theory and its applications, as well as our solutions to the underlying algorithmic challenges.

- Denis Thérien (Montreal, QC, Canada)
**The Power of Diversity.**In mathematics, as in other aspects of life, diversity of points of view represents a great advantage. In the restricted case of finite-state machines, the most uniform model of computation, the duality between the structural algebraic approach and the descriptive logico-combinatorial approach offers a magnificent example of this principle. Several beautiful theorems provide us with deep understanding of important computational concepts in that context. The major question is to carry this understanding into more interesting models, for example such as general boolean circuits. We review the state of our knowledge there and some of the many difficulties that remain to be resolved in the land of non-uniform computations.

# Program Committee

- Jean-Mark Champarnaud (Rouen, France)
- Erzsébet Csuhaj-Varjú (Budapest, Hungary)
- Zoltan Ésik (Szeged, Hungary)
- Markus Holzer (Giessen, Germany) (Co-Chair)
- Galina Jirásková (Košice, Slovakia)
- Martin Kutrib (Giessen, Germany) (Co-Chair)
- Carlos Martín-Vide (Tarragona, Spain)
- Tomáš Masopust (Brno Czech Republic; Amsterdam, The Netherlands)
- Ian McQuillan (Saskatoon, SK, Canada)
- Carlo Mereghetti (Milano, Italy)
- Victor Mitrana (Bucureşti, Romania)
- Alexander Okhotin (Turku, Finland)
- Giovanni Pighizzini (Milano, Italy) (Co-Chair)
- Bala Ravikumar (Sonoma, USA)
- Rogério Reis (Porto, Portugal)
- Kai Salomaa (Kingston, ON, Canada)
- Bianca Truthe (Magdeburg, Germany)

# Organizing Committee

- Susanne Gretschel
- Markus Holzer (Co-Chair)
- Sebastian Jakobi
- Martin Kutrib (Co-Chair)
- Andreas Malcher
- Heinz Rübeling
- Matthias Wendlandt (Co-Chair)

# Steering Committee

- Erzsébet Csuhaj-Varjú (Budapest, Hungary)
- Jürgen Dassow (Magdeburg, Germany)
- Helmut Jürgensen (Potsdam, Germany; London, ON, Canada)
- Hing Leung (Las Cruces, New Mexico)
- Giovanni Pighizzini (Milano, Italy) (Chair)
- Detlef Wotschke (Frankfurt, Germany; Giessen, Germany)