Vincent Blondel: Université Catholique de Louvain, Belgium
http://www.inma.ucl.ac.be/~blondel

Discrete Dynamical Systems and Matrices Products

We consider various questions related to discrete dynamical systems and show how several of them can be cast as questions on matrix products. In particular, we provide matrix formulations of questions related to networks of interacting agents, synchronizing automata, graph coloring and trajectories in automata. In several ot these problems the central issue is that of finding the largest asymptotic growth that can be achieved with products of increasing length of matrices taken in a finite set. This simple question was raised more than 30 years ago but is still not clearly understood and is connected to a large and active literature that touches on many issues in discrete mathematics. During the talk I will provide motivation for studying this problem and will overview recent developments.

Jarkko Kari: University of Turku, Finland
http://users.utu.fi/jkari

Classical Cellular Automata Theory: A Tutorial
(his slides are available here)

We begin with some classical results from the 60's on the injectivity and surjectivity aspects of cellular automata. We recall the Garden-of-Eden- and the Curtis-Hedlund-Lyndon-theorems, as well as the balance property of surjective CA. In each case we provide an example that illustrates the proof idea. We relate injectivity and surjectivity properties on periodic and finite configurations, and discuss their algorithmic aspects and indicate some undecidability results. We also review basic concepts in the topological dynamics approach to cellular automata and chaos, including basic results on different variants of sensitivity and mixing properties.

Stephen Wolfram (in videoconference): Wolfram Research, USA

http://www.stephenwolfram.com

The History and Promise of

Cellular Automata

Martin Kutrib: Universität Gießen, Germany

http://www.informatik.uni-giessen.de/staff/kutrib

Cellular Automata and Language Theory

Instances of problems to solve can be encoded as strings of symbols which are the data supplied to cellular automata. If (one piece of) the answer to the problems is binary, the set of possible inputs is split into two sets associated with the binary outcome. From this point of view, the computational capabilities of cellular automata are studied in terms of string acceptance, that is, the determination to which of the two sets a given string belongs. These investigations are with respect to and with the methods of language theory. They originated in articles by S.N. Cole (1966, 1969) and A.R. Smith (1970, 1972). Though a lot of results have been found over the years, there are still some basic open problems with deep relations to other fields. The survey covers the development of cellular automata accepting formal languages, some of their open problems, as well as more recent results and branches of the theory. The latter are questions of descriptional complexity, grammatical characterizations of accepted language families, some interesting structural restrictions of the model, and relations to linguistic language families.

Eric Goles: Universidad Adolfo Ibáñez, Chile.

www.uai.cl/profesores/eric-goles-chacc

Communication Complexity in Cellular Automata

In this lecture we will present Communication Complexity (CC) applied to one-dimensional Cellular Automata (CAs). CC was introduced by Yao to lower bounding the amount of communication needed in distributed algorithms. Here, given a local function  we consider the communication complexity of some canonical problems related to the dynamics of CAs. Given a canonical problem about the dynamics, we may try to find a protocol such that, if Alice knows, say, a vector x, and Bob knows a vector y, one can know the minimum amount of information that Alice has to give Bob in order to compute, for instance, . We will exhibit experimental and theoretical results on those protocols for any one-dimensional, nearest neighbor CA (elementary CAs). On the other hand, we recently proved that for some dynamical problems related with CAs, intrinsic universality implies maximum CC, so that, for some CA to exhibit constant or log(n) protocol, this implies they are not intrinsic universal. We will illustrate that for some nontrivial elementary CAs.