| Enrico Formenti |
Université de Nice-Sophia Antipolis
| || |
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
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
their relations to classical cellular automata.
| Jean Mairesse |
Université Paris 7
| || |
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
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.
| Ferdinand Peper |
National Institute of Information and Communications Technology
| || |
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
| Guillaume Theyssier |
Université de Savoie
| || |
Cellular Automata: Putting Order into Classifications and Universality
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.