- 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.
- 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)
- Susanne Gretschel
- Markus Holzer (Co-Chair)
- Sebastian Jakobi
- Martin Kutrib (Co-Chair)
- Andreas Malcher
- Heinz Rübeling
- Matthias Wendlandt (Co-Chair)
- 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)