Ci-dessous la liste de mes publications relues par des pairs et
acceptées à des journaux ou conférences internationaux. Cette liste
est orientée vers le contenu (résumés et liens vers les textes en
version électronique). Pour la bibliométrie ou la bibliographie, je
vous renvoie, étant donné mon domaine de recherche, à la base de
donnée en ligne DBLP qui maintient ma
liste de publications.
We study the Monadic Second Order (MSO) Hierarchy over colorings of the discrete plane, and draw links between classes of formula and classes of subshifts. We give a characterization of existential MSO in terms of projections of tilings, and of universal sentences in terms of combinations of “pattern counting†subshifts. Conversely, we characterize logic fragments corresponding to various classes of subshifts (subshifts of finite type, sofic subshifts, all subshifts). Finally, we show by a separation result how the situation here is different from the case of tiling pictures studied earlier by Giammarresi et al.
The paper proposes a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in a unifying and composable manner. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochastic settings. We then provide explicit tools to prove or disprove the existence of such a simulation between two stochastic cellular automata, even though the intrinsic simulation relation is shown to be undecidable in dimension two and higher. The key result behind this is the caracterization of equality of stochastic global maps by the existence of a coupling between the random sources. We then prove that there is a universal non-deterministic cellular automaton, but no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality.
We study intrinsic simulations between cellular automata and introduce a new necessary condition for a CA to simulate another one. Although expressed for general CA, this condition is targeted towards surjective CA and especially linear ones. Following the approach introduced by the first author in an earlier paper, we develop proof techniques to tell whether some linear CA can simulate another linear CA. Besides rigorous proofs, the necessary condition for the simulation to occur can be heuristically checked via simple observations of typical space-time diagrams generated from finite configurations. As an illustration, we give an example of linear reversible CA which cannot simulate the identity and which is 'time-asymmetric', i.e. which can neither simulate its own inverse, nor the mirror of its own inverse.
This paper studies two kinds of simulation between cellular automata:
simulations based on factor and simulations based on sub-automaton. We show
that these two kinds of simulation behave in two opposite ways with respect to
the complexity of attractors and factor subshifts. On the one hand, the factor
simulation preserves the complexity of limits sets or column factors (the simulator
CA must have a higher complexity than the simulated CA). On the other hand,
we show that any CA is the sub-automaton of some CA with a simple limit set
(NL-recognizable) and the sub-automaton of some CA with a simple column factor
(finite type). As a corollary, we get intrinsically universal CA with simple limit
sets or simple column factors. Hence we are able to 'hide' the simulation power
of any CA under simple dynamical indicators.
This paper is the second part of a series of two papers dealing
with bulking: a way to define quasi-order on cellular automata by
comparing space-time diagrams up to rescaling. In the present
paper, we introduce three notions of simulation between cellular
automata and study the quasi-order structures induced by these
simulation relations on the whole set of cellular automata. Various
aspects of these quasi-orders are considered (induced equivalence
relations, maximum elements, induced orders, etc) providing several
formal tools allowing to classify cellular automata.
This paper is the first part of a serie of two papers dealing with
bulking: a quasiorder on cellular automata comparing space-time
diagrams up to some rescaling. Bulking is a generalization of
grouping taking into account universality phenomena, giving rise to
a maximal equivalence class. In the present paper, we discuss the
proper components of grouping and study the most general
extensions. We identify the most general space-time transforms and
give an axiomatization of bulking quasiorder. Finally, we study
some properties of intrinsically universal cellular automata
obtained by comparing grouping to bulking.
This paper studies directional dynamics in cellular automata, a formalism
previously introduced by the third author. The central idea is to study the
dynamical behaviour of a cellular automaton through the conjoint action of
its global rule (temporal action) and the shift map (spacial action):
qualitative behaviours inherited from topological dynamics (equicontinuity,
sensitivity, expansivity) are thus considered along arbitrary curves in
space-time. The main contributions of the paper concern equicontinuous
dynamics which can be connected to the notion of consequences of a word. We
show that there is a cellular automaton with an equicontinuous dynamics along
a parabola, but which is sensitive along any linear direction. We also show
that real numbers that occur as the slope of a limit linear direction with
equicontinuous dynamics in some cellular automaton are exactly the computably
enumerable numbers.
The notions of
universality and completeness are central in the theories of computation and
computational complexity. However, proving lower bounds and necessary
conditions remains hard in most of the cases. In this article, we introduce
necessary conditions for a cellular automaton to be "universal", according to
a precise notion of simulation, related both to the dynamics of cellular
automata and to their computational power. This notion of simulation relies
on simple operations of space-time rescaling and it is intrinsic to the model
of cellular automata. Intrinsinc universality, the derived notion, is
stronger than Turing universality, but more uniform, and easier to define and
study. Our approach builds upon the notion of communication complexity, which
was primarily designed to study parallel programs, and thus is, as we show in
this article, particulary well suited to the study of cellular automata: it
allowed to show, by studying natural problems on the dynamics of cellular
automata, that several classes of cellular automata, as well as many natural
(elementary) examples, could not be intrinsically universal.
The study of factoring
relations between subshifts or cellular automata is central in symbolic
dynamics. Besides, a notion of intrinsic universality for cellular automata
based on an operation of rescaling is receiving more and more attention in
the literature. In this paper, we propose to study the factoring relation up
to rescalings, and ask for the existence of universal objects for that
simulation relation. In classical simulations of a system S by a system T ,
the simulation takes place on a specific subset of configurations of T
depending on S (this is the case for intrinsic universality). Our setting,
however, asks for every configurations of T to have a meaningful
interpretation in S. Despite this strong requirement, we show that there
exists a cellular automaton able to simulate any other in a large class
containing arbitrarily complex ones. We also consider the case of subshifts
and, using arguments from recursion theory, we give negative results about
the existence of universal objects in some classes.
Topological dynamics of cellular automata (CA), inherited from
classical dynamical systems theory, has been essentially studied in
dimension 1. This paper focuses on higher dimensional CA and aims at
showing that the situation is different and more complex starting from
dimension 2. The main results are the existence of non sensitive CA
without equicontinuous points, the non-recursivity of sensitivity
constants, the existence of CA having only non-recursive
equicontinuous points and the existence of CA having only countably
many equicontinuous points. They all show a difference between
dimension 1 and higher dimensions. Thanks to these new constructions,
we also extend undecidability results concerning topological
classification previously obtained in the 1D case. Finally, we show
that the set of sensitive CA is only Pi_2 in dimension 1, but becomes
Sigma_3-hard for dimension 3.
We study the Monadic Second Order (MSO) Hierarchy over
infinite pictures, that is tilings. We give a characterization
of existential MSO in terms of tilings and projections of
tilings. Conversely, we characterise logic fragments
corresponding to various classes of infinite pictures (subshifts
of finite type, sofic subshifts).
Cellular automata (CA) are dynamical systems defined by a
finite local rule but they are studied for their global
dynamics. They can exhibit a wide range of complex behaviours
and a celebrated result is the existence of (intrinsically)
universal CA, that is CA able to fully simulate any other CA. In
this paper, we show that the asymptotic density of universal
cellular automata is 1 in several families of CA defined by
local symmetries. We extend results previously established for
captive cellular automata in two significant ways. First, our
results apply to well-known families of CA (e.g. the family of
outer-totalistic CA containing the Game of Life) and, second, we
obtain such density results with both increasing number of
states and increasing neighbourhood. Moreover, thanks to
universality-preserving encodings, we show that the universality
problem remains undecidable in some of those families.
In this paper, we study amalgamations of cellular automata (CA),
i.e. ways of combining two CA by disjoint union. We show that for
several families of CA obtained by simple amalgamation operations
(including the well-known families of majority and minority CA),
the density of a large class of properties follows a zero-one
law. Besides, we establish that intrinsic universality in those
families is always non-trivial and undecidable for some of
them. Therefore we obtain various syntactical means to produce CA
which are almost all intrinsically universal. These results extend
properties already obtained for captive cellular automata. We
additionally prove that there exists some reversible captive CA
which are (intrinsically) universal for reversible CA.
Topological dynamics of cellular automata (CA), inherited
from classical dynamical systems theory, has been essentially
studied in dimension 1. This paper focuses on 2D CA and aims at
showing that the situation is different and more complex. The
main results are the existence of non sensitive CA without
equicontinuous points, the non-recursivity of sensitivity
constants and the existence of CA having only non-recursive
equicontinuous points. They all show a difference between the 1D
and the 2D case. Thanks to these new constructions, we also
extend undecidability results concerning topological
classification previously obtained in the 1D case.
We study the notion of limit sets of cellular automata
associated with probability measures (mu-limit sets). This
notion was introduced by P. Kurka and A. Maass. It is a
refinement of the classical notion of omega-limit sets dealing
with the typical long term behavior of cellular automata. It
focuses on the words whose probability of appearance does not
tend to 0 as time tends to infinity (the persistent words). In
this paper, we give a characterisation of the persistent
language for non sensible cellular automata associated with
Bernouilli measures. We also study the computational complexity
of these languages. We show that the persistent language can be
non-recursive. But our main result is that the set of
quasi-nilpotent cellular automata (those with a single
configuration in their mu-limit set) is neither recursively
enumerable nor co-recursively enumerable.
We address the problem of the density of intrinsically
universal cellular automata among cellular automata or a
subclass of cellular automata. We show that the density of
captive cellular automata possessing a given poperty follow a
zero-one law for a large class of properties. As a corollary, we
show that they are almost all intrinsically universal. We show
however that intrinsic universality is undecidable for captive
cellular automata. Finally, we show that almost all cellular
automata have no non-trivial sub-automaton.
We introduce a natural class of cellular automata
characterised by a property of the local transition law without
any assumption on the states set. We investigate some algebraic
properties of the class and show that it contains intrinsically
universal cellular automata. In addition we show that Rice's
theorem for limit sets is no longer true for that class,
although infinitely many properties of limit sets are still
undecidable.
Cellular automata and communication complexity. With
Christoph Dürr and Ivan Rapaport. [pdf] Theoretical Computer Science doi:10.1016/j.tcs.2004.03.017
The model of cellular automata is fascinating because very
simple local rules can generate complex global behaviors. The
relationship between local and global function is subject of
many studies. We tackle this question by using results on
communication complexity theory and, as a by-product, we provide
(yet another) classification of cellular automata.
Pre-expansivity in cellular automata[pdf] Winter
FRAC'13 - Montpellier, France, February 2013
Decidability and universality in stochastic cellular automata[pdf] Rencontres ACP - Paris, France, January 2013
Some pictures from cellular automata theory[pdf] Universidad Adolfo Ibañez, Santiago, Chile, November 2012
Don't forgett the lattice![pdf] Universidad de Concepción, Chile, November 2012
On μ-limit Sets of Cellular Automata[pdf] Talk given at Winter
FRAC'12 - Créteil, France, February 2012
Synchronization and Limit Behaviors in Cellular Automata[pdf] Talk given at DISCO - Valparaíso, Chile, November 2011
Selfsimilarity, Simulation and Spacetime Symmetries[pdf] Talk given at AUTOMATA'11 - Santiago, Chile, November 2011
Clandestine Simulations in Cellular Automata[pdf] Talk given at JAC 2010 - Turku, Finland, December 2010
Directional Dynamics of Cellular Automata[pdf] Seminario Universidad de Chile DIM - Santiago, Chile, September 2010
Putting Order into Classifications and Universality[pdf] Talk given at
AUTOMATA'10 - Nancy, France, June 2010
Subshifts and MSO logic[pdf] Talk given at Winter
FRAC'09 - Marne-La-Vallée, France, March 2009
How Common is Universality in Cellular
Automata?[pdf] Seminario de Matemáticas Discretas DIM/CMM - Santiago, Chile, November
2008
Topological Dynamics of 2D Cellular Automata[pdf] Talk given
at CiE'08 - Athens, Greece, June
2008
Amalgamation of Cellular Automata[pdf] Talk given at JAC'08 - Uzès, France, April
2008
Pré-ordres de simulation et automates cellulaires[pdf] Talk
(in French) given at the SDA2 workshop of GDR IM - Paris, France, October
2007 (another version given at LIFO: [pdf] Orléans, France, February
2008)
Higher Dimensional Dynamics[pdf] Talk given at the Summer FRAC'07 - Nice, France, June 2007
Simulation Preorders[pdf] Talk given for the ESCAPE working group - Marseille, France, May 2007
Information Propagation and Simulation Preorders[pdf] Talk
given at the Winter FRAC'07 - Lyon, France, February 2007
On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures[pdf] Talk given at MFCS'06 - Stará Lesná, Slovakia,
August 2006
Autour de l'universalité dans les automates cellulaires[pdf] GREYC seminar (in French) - Caen, France, March 2005
How Common Can Be Universality in Cellular Automata?[pdf] talk given at STACS'05 - Stuttgart, Germany, February 2005
Captive Cellular Automata[pdf] Talk given at MFCS'04 - Prague, Czech Republic, August 2004
Backgrounds in 1D cellular automata[pdf] talk given at AUTOMATA'02 - Prague, Czech Republic, September 2002
J'ai effectué ma thèse sous la direction de M. Delorme et J. Mazoyer,
dans l'équipe MC2 au LIP à
l'École Normale Supérieure de Lyon.
Je l'ai soutenue le 14 décembre 2005 à Lyon, devant un jury composé de
Marie-Pierre Béal
(rapporteur), Marianne Delorme (directeur de thèse), Bruno
Durand (rapporteur),
Antonio Machi (président), Jacques Mazoyer (directeur de thèse) et
Laurent Vuillon.
