On deterministic asynchronous automata [SLIDES]

Asynchronous Cellular Automata (ACA) are receiving more and more attention as formal models for physical and biological phenomena. Historically they were introduced as a formal model for concurrent systems.
In the first part of this talk we will briefly review these historical models for ACA and make the transition to fully deterministic ACA. Afterwards we will review some basic results about deterministic ACA and their relations to classical cellular automata.

Around Probabilistic Cellular Automata

Probabilistic Cellular Automata (PCA) are an extension of Cellular Automata. The state space remains the same as well as the local and synchronous character of the dynamic. The novelty is that each site updates its value randomly according to a probability distribution which depends on the neighbouring sites. There exist several motivations for considering PCA: they are the synchronous counterparts of the "interacting particle systems" actively studied in probability; they appear in combinatorial problems related to statistical physics (enumeration of directed lattice animals); they enable to study the robustness to failures of classical cellular automata. A PCA is a Markov chain and we are interested in the equilibrium behavior(s) characterized by the stationary distribution(s) of the chain. We discuss several related questions on the stationary distribution: uniqueness; possibility of explicit computation; perfect sampling.

Brownian Cellular Automata: the Ultimate Asynchronicity?

Brownian Cellular Automata (CA) are asynchronous CA that exploit the properties of randomness to improve the efficiency of computation in terms of model complexity. After giving a brief overview of computation on asynchronous CA, we show that Brownian CA have a more "natural" form of asynchronicity in which phenomena like arbitration can be realized in a straightforward way. The fitness of Brownian CA for implementations by nanotechnology will also be highlighted.

Cellular Automata: Putting Order into Classifications and Universality [SLIDES]

Cellular automata are known to be Turing-powerful since the pioneering work of von Neumann. However, analysing their ability to process information only through translations into the Turing world is very restrictive. It is possible, instead, to define pre-orders (transitive relations) on the set of CA interpreted as simulation relations between CA. Then, each pre-order can be used as a classification tool (induced equivalence relation, topology of the pre-order, etc) or as the core ingredient of a notion of universality (maximal elements of the pre-orders). The key point is that meaningful simulation pre-orders can be obtained in a simple way from very basic ingredients, the main one being the notion of space and time rescaling. We will give an overview of old and new results concerning such pre-orders and their corresponding notions of universality.