 Weak colored local rules for planar tilings
 A paraître dans Ergodic Theory and Dynamical Systems.
[PDF][Abstract]
[arXiv]
A linear subspace E of ℝ^{n} has colored local rules if there exists a finite set of decorated tiles whose tilings are digitizations of E. The local rules are weak if the digitizations can slightly wander around E. We prove that a linear subspace has weak colored local rules if and only if it is computable. This goes beyond the previous results, all based on algebraic subspaces. We prove an analogous characterization for sets of linear subspaces, including the set of all the linear subspaces of ℝ^{n}.
 A generalisation of the simulation theorem for semidirect products
 A paraître dans Ergodic Theory and Dynamical Systems.
[PDF][Abstract][arXiv]
We generalize a result of Hochman in two simultaneous directions: Instead of
realizing an effectively closed Z^{d} action as a factor of a
subaction of a Z^{d+2}SFT we realize an action of a finitely
generated group analogously in any semidirect product of the group with
Z^{2}. Let H be a finitely generated group and G the semi direct product of Z^{2} with H. We show that for any effectively closed
Hdynamical system (Y,f) where Y is a Cantor set, there exists a
Gsubshift of finite type (X,\sigma) such that the Hsubaction of
(X,\sigma) is an extension of (Y,f). In the case where f is an expansive
action of a recursively presented group H, a subshift conjugated to (Y,f)
can be obtained as the Hprojective subdynamics of a Gsofic subshift. As a
corollary, we obtain that G admits a nonempty strongly aperiodic subshift of
finite type whenever the word problem of H is decidable.
 Selforganisation in cellular automata with coalescent particles: Qualitative and quantitative approaches
 Paru dans Journal of Statistical PhysicsVolume 167, Issue 5, pp 1180–1220, June 2017.
[PDF][Abstract][arXiv]
This article introduces new tools to study selforganisation in a family of simple cellular automata which contain some particlelike objects with good collision properties (coalescence) in their time evolution. We draw an initial configuration at random according to some initial σergodic measure μ, and use the limit measure to descrbe the asymptotic behaviour of the automata.
We first take a qualitative approach, i.e. we obtain information on the limit measure(s). We prove that only particles moving in one particular direction can persist asymptotically. This provides some previously unknown information on the limit measures of various deterministic and probabilistic cellular automata: 3 and 4cyclic cellular automata (introduced in [Fis90b]), onesided captive cellular automata (introduced in [The04]), N. Fatès’ candidate to solve the density classification problem [Fat13], self stabilization process toward a discrete line [RR15]. . .
In a second time we restrict our study to to a subclass, the gliders cellular automata. For this class we show quantitative results, consisting in the asymptotic law of some parameters: the entry times (generalising [KFD11]), the density of particles and the rate of convergence to the limit measure.
 Probability and algorithmics: a focus on some recent developments
 Paru dans ESAIM: Proceedings and Surveys, 2017, Vol. 60, p. 203224.
Travail en collaboration avec Peggy Cénac, Irène Marcovici, Christelle Rovetta et Rémi Varloot .
[PDF][Abstract]
This article presents different recent theoretical results illustrating the interactions between probability and algorithmics. These contributions deal with various topics: cellular automata and calculability, variable length Markov chains and persistent random walks, perfect sampling via coupling from the past. All of them involve discrete dynamics on complex random structures.
 A notion of effectiveness for subshifts on finitely generated groups
 Paru dans Theoretical Computer Science, Volume 661, 24 January 2017, Pages 3555.
[PDF][Abstract][arXiv]
We generalize the classical definition of effectively closed subshift to finitely generated groups. We study classical stability properties of this class and then extend this notion by allowing the usage of an oracle to the word problem of a group. This new class of subshifts forms a conjugacy class that contains all sofic subshifts. Motivated by the question of whether there exists a group where the class of sofic subshifts coincides with that of effective subshifts, we show that the inclusion is strict for several groups, including recursively presented groups with undecidable word problem, amenable groups and groups with more than two ends. We also provide an extended model of Turing machine which uses the group itself as a tape and characterizes our extended notion of effectiveness. As applications of these machines we prove that the origin constrained domino problem is undecidable for any group of the form G×ℤ subject to a technical condition on G and we present a simulation theorem which is valid in any finitely generated group.
 Characterization of sets of limit measures after iteration of a cellular automaton on an initial measure
 A paraître dans Ergodic Theory and Dynamical Systems.
[PDF][arXiv]
[Abstract]
The asymptotic behavior of a cellular automaton iterated on a random configuration is well described by its limit probability measure(s). In this paper, we characterize measures and sets of measures that can be reached as limit points after iterating a cellular automaton on a simple initial measure, in the same spirit as SRB measures. In addition to classical topological constraints, we exhibit necessary computational obstructions. With an additional hypothesis of connectivity, we show these computability conditions are sufficient by constructing a cellular automaton realising these sets, using auxiliary states in order to perform computations. Adapting this construction, we obtain a similar characterization for the Cesàro mean convergence, a Rice theorem on the sets of limit points, and we are able to perform computation on the set of measures, i.e. the cellular automaton converges towards a set of limit points that depends on the initial measure. Last, under nonsurjective hypotheses, it is possible to remove auxiliary states from the construction.
 μLimit Sets of Cellular Automata from a Computational Complexity Perspective
 Paru dans Journal of Computer and System Sciences, Volume 81, Issue 8, December 2015, Pages 16231647.
[PDF][arXiv][Abstract]
This paper is about \mulimit sets of cellular automata, i.e. sets of configurations made of words which have a positive probability to appear arbitrarily late in the evolution, starting from an initial \murandom confi guration. More precisely, we investigate the computational complexity of these sets and of decision problems concerning them. Our main results are: first, that such a set can have a \Signma_3hard language, second that it can contain only \alphacomplex confi gurations and third that any nontrivial property concerning these sets is at least \Pi_3hard. We also prove various complexity upper bounds, study some restriction of these questions to particular classes of cellular automata, and study different types of (non)convergence of the probability of appearance of a word in the evolution.
 Multidimensional effective Sadic systems are sofic
 Parru dans Uniform Distribution Theory, Volume 9, issue 2, 2014.
[PDF][arXiv]
[Abstract]
In this article we prove that multidimensional effective Sadic systems, obtained by applying an effective sequence of substitutions chosen among a finite set of substitutions, are sofic subshifts.
 Simulation of recursively enumerable subshifts by two dimensional SFT.
 Paru dans Acta Applicandae Mathematicae, Volume 128, issue 1, p.3563, 2013.
[PDF][arXiv]
[Abstract]
In this article we study how a subshift can simulate another one, where the notion of simulation is given by operations on subshifts inspired by the dynamical systems theory (factor, projective subaction...). There exists a correspondence between the notion of simulation and the set of forbidden patterns. The main result of this paper states that any effective subshift of dimension d  that is a subshift whose set of forbidden patterns can be generated by a Turing machine  can be obtained by applying dynamical operations on a subshift of finite type of dimension d+1  a subshift that can be defined by a finite set of forbidden patterns. This result improves Hochman's.
 Directional Dynamics along Arbitrary Curves in Cellular Automata.
 Paru dans Theoretical Computer Science, Volume 412(30): 38003821, 2011.
[PDF]
[arXiv]
[Abstract]
This paper studies directional dynamics on onedimensional 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 spacetime. 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.
 Topological Dynamics of Cellular Automata: Dimension Matters
 Paru dans Theory of Computing Systems , Volume 48, p693714, 2011.
[PDF]
[arXiv]
[Abstract]
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 differ ent and more complex starting from dimension 2. The main results are the existence of non sensitive CA without equicontinuous points, the nonrecursivity of sensitiv ity constants, the existence of CA having only nonrecursive 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 classifi cation previously obtained in the 1D case. Finally, we show that the set of sensitive CA is only Π_{2}^{0} in dimension 1, but becomes Σ_{3}^{0}hard for dimension 3.
 Recherche de mesures invariantes pour l'action conjointe d'un automate cellulaire et du décalage.
 Paru dans Séminaires et Congrès de la SMF 20 (2010), 207251.
[PDF]
[Abstract]
Soit A un alphabet fini, un automate cellulaire peut être défini comme une fonction continue sur A^{Z} qui commute avec le décalage σ. On considère la N × Zaction (F, σ) et on se propose de caractériser les mesures de probabilité (F, σ)invariantes.
Dans un premier temps, on s’intéresse aux conditions imposées par la dynamique directionnelle introduite dans [Sab08] sur les mesures (F, σ)invariantes. Pour la classe des automates cellulaires qui ont un cône d’expansivité, on s’aperçoit qu’il y a une certaine rigidité des mesures (F,σ)invariantes. Cela signifie qu’il y a des contraintes sur les mesures (F, σ)invariantes, notamment un lien entre l’entropie métrique de F et l’entropie métrique de σ. On étudie en particulier la classe des automates cellulaires algébriques. L’étude de cette classe rappelle la conjecture de Furstenberg [Fur67] qui énonce que les seules mesures invariantes par la multiplication par 2 et par 3 sur le tore sont la mesure de Lebesgue et les mesures uniformément portées par les orbites (F, σ)périodiques.
 Positive circuits and ddimensional spatial differentiation: Application to the formation of sense organs in drosophila.
 Paru dans BioSystems, Volume 94, Issues 12, OctoberNovember 2008, Pages 102108.
[PDF]
[Abstract]
We discuss a rule proposed by the biologist R.Thomas according to which the possibility for a genetic network (represented by a signed directed graph called a regulatory graph) to have several stable states implies the existence of a positive circuit. This result is already known for different models, differential or discrete formalism, but always with a network of genes contained in a single cell. Thus we can ask about the validity of this rule for a system contained several cells and so with intercellular genetic interactions. In this paper, we consider the genetic interactions between several cells located on a ddimensional lattice, i.e. each point of lattice represent a cell we associate the expression level of $n$ genes contained in this cell. With this configuration, we show that the existence of a positive circuit is a necessary condition for a specific form of multistationarity, which naturally corresponds to spatial differentiation. We then illustrate this theorem through the example of the formation of sense organs in Drosophila.
 Directional dynamic for cellular automata: A sensitivity to initial condition approach
 Paru dans Theoretical Computer Science, Volume 400, Issues 13, 9 June 2008, Pages 118.
[PDF]
[Abstract]
A cellular automaton is a continuous function F defined on a fullshift A^{Z} which commutes with the shift σ. Often, to study the dynamics of F one only considers implicitly σ. However, it is possible to emphasize the spatiotemporal structure produced by considering the dynamics of the Z×Naction induced by (σ,F).
In this purpose we study the notion of directional dynamics. In particular, we are interested in directions of equicontinuity and expansivity, which generalize the concepts introduced by R.H. Gilman and P. Kurka. We study the sets of directions which exhibit this special kind of dynamics showing that they induce a discrete geometry in spacetime diagrams.
 Measure rigidity for algebraic bipermutative cellular
 Paru dans
Ergodic Theory and Dynamical Systems, Volume 27, Issue 06, Dec 2007, pp 19651990.
[PDF]
[arXiv]
[Abstract]
Let (A^{Z},F) be a bipermutative algebraic cellular automaton. We present conditions which force a probability measure which is invariant for the N×Zaction of F and the shift map σ to be the Haar measure on Σ, a closed shiftinvariant subgroup of the Abelian compact group A^{Z}. This generalizes simultaneously results of B. Host, A. Maass and S. Martinez and M. Pivato. This result is applied to give conditions which also force a (F, σ)invariant probability measure to be the uniform Bernoulli measure when F is a particular invertible expansive cellular automaton on A^{N}.
 Algorithmic optimization for the realization of an effective subshift by a sofic
 Accepté à International Colloquium on Automata, Languages and Programming 2016.
[PDF][Abstract]
Realization of ddimensional effective subshifts as projective subactions of d+d′dimensional sofic subshifts for d′≥1 is now well known. In this paper we are interested in qualitative aspects of this realization. We introduce a new topological conjugacy invariant for effective subshifts, the speed of convergence, in view to exhibit algorithmic properties of these subshifts in contrast to the usual framework that focuses on undecidable properties.
 Effective Sadic symbolic dynamical system.
 Accepté à Computability in Europe 2016.
[PDF][Abstract]
We focus in this survey on effectiveness issues for Sadic sub shifts and tilings. An Sadic subshift or tiling space is a dynamical system obtained by iterating an infinite composition of substitutions, where a substitution is a rule that replaces a letter by a word (that might be multidimensional), or a tile by a finite union of tiles. Several notions of effectiveness exist concerning Sadic subshifts and tiling spaces, such as the computability of the sequence of iterated substitutions, or the effec tiveness of the language. We compare these notions and discuss effective ness issues concerning classical properties of the associated subshifts and tiling spaces, such as the computability of shiftinvariant measures and the existence of local rules (soficity). We also focus on planar tilings.
 The domino problem for self similar structure
 Accepté à Computability in Europe 2016.
[PDF][Abstract]
We define the domino problem for tilings over selfsimilar structures of Z^{d} given by forbidden patterns. In this setting we exhibit nontrivial families of subsets with decidable and undecidable domino problem.
 Local Rules for Computable Planar Tilings
 Accepté à Automata and Journées Automates Cellulaires 2012.
[PDF][arXiv]
[Abstract]
Aperiodic tilings are nonperiodic tilings characterized by local constraints. They play a key role in the proof of the undecidability of the domino problem (1964) and naturally model quasicrystals (discovered in 1982). A central question is to characterize, among a class of nonperiodic tilings, the aperiodic ones. In this paper, we answer this question for the wellstudied class of nonperiodic tilings obtained by digitizing irrational vector spaces. Namely, we prove that such tilings are aperiodic if and only if the digitized vector spaces are computable.
 Entry times in automata with simple defect dynamics
 Accepté à Automata and Journées Automates Cellulaires 2012.
[PDF][arXiv]
[Abstract]
[PDF,version avec annexe]
In this paper, we consider a simple cellular automaton with two particles of different speeds that annihilate on contact. Following a previous work by K\r urka et al., we study the asymptotic distribution, starting from a random configuration, of the waiting time before a particle crosses the central column after time n. Drawing a parallel between the behaviour of this automata on a random initial configuration and a certain random walk, we approximate this walk using a Brownian motion, and we obtain explicit results for a wide class of initial measures and other automata with similar dynamics.
 Selforganization in cellular automata : a particlebased approach
 Accepté à Developements in Language Theory 2011.
[PDF]
[Abstract]
In this paper, we consider a simple cellular automaton with two particles of different speeds that annihilate on contact. Following a previous work by Kurka et al., we study the asymptotic distribution, starting from a random configuration, of the waiting time before a particle crosses the central column after time n. Drawing a parallel between the behaviour of this automata on a random initial configuration and a certain random walk, we approximate this walk using a Brownian motion, and we obtain explicit results for a wide class of initial measures and other automata with similar dynamics.
 Construction of μlimit sets
 Accepté aux Journées Automates Cellulaires 2010.
[PDF]
[arXiv]
[Abstract]
The μlimit set of a cellular automaton is a subshift whose forbidden patterns are exactly those, whose probabilities tend to zero as time tends to infinity. In this article, for a given subshift in a large class of subshifts, we propose the construction of a cellular automaton which realizes this subshift as μlimit set where μ is the uniform Bernoulli measure.
 An Order on Sets of Tilings Corresponding to an Order on Languages
 Accepté à Symposium on Theoretical Aspects of Computer Science 2009.
[PDF]
[arXiv]
[Abstract]
Traditionally a tiling is defined with a finite number of finite forbidden patterns. We can generalize this notion considering any set of patterns. Generalized tilings defined in this way can be studied with a dynamical point of view, leading to the notion of subshift. In this article we establish a correspondence between an order on subshifts based on dynamical transformations on them and an order on languages of forbidden patterns based on computability properties.
 Topological Dynamics of 2D Cellular automata
 Accepté à Computability in Europe 2008.
[PDF]
[arXiv]
[Abstract]
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 nonrecursivity of sensitivity constants and the existence of CA having only nonrecursive 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.
 Two points of view to study the iterates of a random configuration by a Cellular Automaton
 Accepté aux Journées Automates Cellulaires 2008.
[PDF]
[Abstract]
We study the dynamics of the action of cellular automata on the set of shiftinvariant probability measures according two points of view. First, the robustness of the simulation of a cellular automaton on a random configuration can be viewed considering the sensitivity to initial condition in the space of shiftinvariant probability measures. Secondly we consider the evolution of the quantity of information in the orbit of a random initial state.
 Conditions nécessaires pour la multistabilité dans l'approche intercellulaire
 Accepé à Réseaux d'Interactions: Analyse, Modélisation, Simulation 2007.
[PDF]
[Abstract]
Dans les années 80, le biologiste R. Thomas a conjecturé une règle liant multistationnarité dans un système de gènes interagissant dans une seule cellule et l’existence d'un circuit positif dans le graphe d'interaction génétique. Ce résultat a été prouvé pour différents modèles, différentiels ou booléens. Ainsi on peut s'interroger sur la validité de cette règle pour un système contenant plusieurs cellules et de ce fait, avec des interactions génétiques intercellulaires. Dans ce papier, on propose de formaliser la répartition des cellules par un réseau, i.e, chaque point du réseau représente une cellule auquelle est associée le niveau d’expression des n gènes contenus dans cette cellule. A l'aide de cette configuration, nous montrons que l'existence d'un circuit positif est une condition nécessaire pour une forme spécifique de multistationnarité. Nous illustrons ce théorème à travers deux exemples issus du développement de la Drosophile.
 The dynamics of cellular automata in shiftinvariant topologies
 Accepté à Developements in Language Theory 2007, 8495, Lecture Notes in Comput. Sci., 4588, Springer, Berlin, 2007.
[PDF]
[Abstract]
We study the dynamics of cellular automata, and more specifically their transitivity, when the set of configurations is endowed with a shiftinvariant (pseudo)distance. We first give an original proof of the nontransitivity of cellular automata when the set of configurations is endowed with the Besicovitch pseudodistance. We then show that the Besicovitch pseudodistance induces a distance on the set of shiftinvariant measures, and we prove that in this space also, there exist no transitive cellular automata. We end the paper with a discussion on the relations between this distance and the distance induced on the set of shiftinvariant measures by the Cantor distance.
 Ergodicity of some classes of cellular automata subject to noise.

[PDF]
[Abstract]
Cellular automata (CA) are dynamical systems on symbolic configurations on the lattice. They are also used as models of massively parallel computers. As dynamical systems, one would like to understand the effect of small random perturbations on the dynamics of CA. As models of computation, they can be used to study the reliability of computation against noise.
We consider various families of CA (nilpotent, permutive, gliders, CA with a spreading symbol, surjective, algebraic) and prove that they are highly unstable against noise, meaning that they forget their initial conditions under slightest positive noise. This is manifested as the ergodicity of the resulting probabilistic CA. The proofs involve a collection of different techniques (couplings, entropy, Fourier analysis), depending on the dynamical properties of the underlying deterministic CA and the type of noise.
 Action of cellular automata on shiftinvariant measure

[PDF]
[Abstract]
In this article we introduce a general process to construct σinvariant pseudodistance. An other σinvariant object is the set of σinvariant probability measures. We give a general framework for studying the action of cellular automata on this set and establish some properties of the dynamics of the action of cellular automata on this space.
 Rowconstrained effective sets of colourings in the 2fold horocyclic tessellations of H^{2} are sofic

[PDF]
[Abstract]
[arXiv]
In this article we prove that, restricted to the rowconstrained case, effective sets of colourings in the 2fold horocyclic tessellations of the hyperbolic plane ℍ^{2} are sofic.
 Speed of convergence towards an effective subshift

[PDF][Abstract]
[arXiv]
Realization of ddimensional effective subshifts as projective subactions of d+d′dimensional sofic subshifts for d′≥1 is now well know [Hoc09, DRS10, AS11]. In this paper we are interested in the speed of convergence of this realization. That is to say given an effective subshift Σ realized as projective subaction of a sofic T, we study the function which on input an integer k returns the smallest width of the strip which verify the local rules of T necessary to obtain exclusively the language of size k of Σ in the central row of the strip. We study this topological conjugacy invariant for effective subshifts in order to exhibit algorithmic properties of these subshifts.
 Block gluing intensity of bidimensional SFT: computability of the entropy and periodic points

[PDF][Abstract]
[arXiv]
It is possible to define mixing properties for subshifts according to the intensity which allows to concatenate two rectangular blocks. We study the interplay between this intensity and computational properties. In particular we prove that there exists linearly block gluing subshift of finite type which are aperiodic and that all rightrecursively enumerable positive number can be realized as entropy of linearly block gluing Z^{2}subshift of finite type. Like linearly block gluing imply transitivity, this last point answer a question asked in [HM10] about the characterization of the entropy of transitive subshift of finite type.