Publications

Articles acceptés dans des revues internationales

Arithmetical Hierarchy of the Besicovitch-Stability of Noisy Tilings

Paru dans Theory of Computing Systems, 2023.

Travail en collaboration avec L. Gayral.

[PDF][Abstract] [arXiv]

The purpose of this article is to study the algorithmic complexity of the Besicovitch stability of noisy subshifts of finite type, a notion studied in a previous article. First, we exhibit an unstable aperiodic tiling, and then see how it can serve as a building block to implement several reductions from classical undecidable problems on Turing machines. It will follow that the question of stability of subshifts of finite type is undecidable, and the strongest lower bound we obtain in the arithmetical hierarchy is Π_2-hardness. Lastly, we prove that this decision problem, which requires to quantify over an uncountable set of probability measures, has a Π_4 upper bound.

On the Besicovitch-Stability of Noisy Random Tilings

Paru dans Electronic Journal of Probability, 28, 1-38, 2023.

Travail en collaboration avec L. Gayral.

[PDF][Abstract] [arXiv]

In this paper, we introduce a noisy framework for SFTs, allowing some amount of forbidden patterns to appear. Using the Besicovitch distance, which permits a global comparison of configurations, we then study the closeness of noisy measures to non-noisy ones as the amount of noise goes to 0. Our first main result is the full classification of the (in)stability in the one-dimensional case. Our second main result is a stability property under Bernoulli noise for higher-dimensional periodic SFTs, which we finally extend to an aperiodic example through a variant of the Robinson tiling.

Parametrization by Horizontal Constraints in the Study of Algorithmic Properties of ℤ²-Subshift of Finite Type.

Paru dans Discrete and Continuous Dynamical Systems, 2023, 43(5): 2002-2046.

Travail en collaboration avec S. Esnay.

[PDF][Abstract] [arXiv]

The non-emptiness, called the Domino Problem, and the characterization of the possible entropies of ℤ²-subshifts of finite type are standard problems of symbolic dynamics. In this article we study these questions with horizontal constraints fixed beforehand as a parameter. We determine for which horizontal constraints the Domino Problem is undecidable and when all right-recursively enumerable numbers can be obtained as entropy, with two approaches: either the additional local rules added to the horizontal constraints can be of any shape, or they can only be vertical rules.

Quantified block gluing for multidimensional subshift of finite type: aperiodicity and entropy

Paru dans Journal d'Analyse Mathématique, 144, pages 21–118 (2021).

Travail en collaboration avec S. Gangloff.

[PDF][Abstract] [arXiv]

It is possible to extend the notion of block gluing for subshifts studied in [PS15] adding a gap function which gives the distance which allows to concatenate two rectangular blocks of the language. In this article, we study the interplay between this intensity and computational properties. In particular, we prove that there exists block gluing SFTs with linear gap which are aperiodic and that all the non-negative right-recursively enumerable (Π₁-computable) numbers can be realized as entropy of such subshifts of finite type. As block gluing with linear gap implies transitivity, this last point provides a solution to Problem 9.1 in [HM10] about the characterization of the entropies of transitive subshift of finite type.

On the computability properties of topological entropy: a general approach.

Paru dans Discrete and Continuous dynamical systems, 2020, 40(7): 4259-4286..

Travail en collaboration avec S. Gangloff, A. Herrera et C. Rojas.

[PDF][Abstract] [arXiv]

The dynamics of symbolic systems, such as multidimensional subshifts of finite type or cellular automata, are known to be closely related to computability theory. In particular, the appropriate tools to describe and classify topological entropy for this kind of systems turned out to be of computational nature. Part of the great importance of these symbolic systems relies on the role they have played in understanding more general systems over non-symbolic spaces. The aim of this article is to investigate topological entropy from a computability point of view in this more general, not necessarily symbolic setting. In analogy to effective subshifts, we consider computable maps over effective compact sets in general metric spaces, and study the computability properties of their topological entropies. We show that even in this general setting, the entropy is always a $\Sigma_2$-computable number. We then study how various dynamical and analytical constrains affect this upper bound, and prove that it can be lowered in different ways depending on the constraint considered. In particular, we obtain that all $\Sigma_2$-computable numbers can already be realized within the class of surjective computable maps over $\{0,1\}^{\mathbb{N}}$, but that this bound decreases to $\Pi_{1}$(or upper)-computable numbers when restricted to expansive maps. On the other hand, if we change the geometry of the ambient space from the symbolic $\{0,1\}^{\mathbb{N}}$ to the unit interval $[0,1]$, then we find a quite different situation -- we show that the possible entropies of computable systems over $[0,1]$ are exactly the $\Sigma_{1}$(or lower)-computable numbers and that this characterization switches down to precisely the computable numbers when we restrict the class of system to the quadratic family.

Ergodicity of some classes of cellular automata subject to noise.

Paru dans Electronic Journal of Probability, 24, paper #41, 44pp, 2019.

Travail en collaboration avec I. Marcovici et S. Taati.

[PDF][Abstract][arXiv]

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.

Weak colored local rules for planar tilings

Paru dans Ergodic Theory and Dynamical Systems, Volume 39 / Numéro 12 / Décembre 2019.

Travail en collaboration avec T. Fernique.

[PDF][Abstract] [arXiv]

A linear subspace E of ℝⁿ 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 ℝⁿ.

A generalisation of the simulation theorem for semidirect products

Paru dans Ergodic Theory and Dynamical Systems, Volume 39 / Numéro 12 / Décembre 2019.

Travail en collaboration avec S. Barbieri.

[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². Let H be a finitely generated group and G the semi direct product of Z² with H. We show that for any effectively closed H-dynamical system (Y,f) where Y is a Cantor set, there exists a G-subshift of finite type (X,\sigma) such that the H-subaction 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 H-projective subdynamics of a G-sofic subshift. As a corollary, we obtain that G admits a non-empty strongly aperiodic subshift of finite type whenever the word problem of H is decidable.

Characterization of sets of limit measures after iteration of a cellular automaton on an initial measure

Paru dans Ergodic Theory and Dynamical Systems, Volume 38 / Numéro 2 / Avril 2018.

Travail en collaboration avec B. Hellouin De Menibus.

[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 non-surjective hypotheses, it is possible to remove auxiliary states from the construction.

Self-organisation in cellular automata with coalescent particles: Qualitative and quantitative approaches

Paru dans Journal of Statistical PhysicsVolume 167, Issue 5, pp 1180–1220, June 2017.

Travail en collaboration avec B. Hellouin De Menibus.

[PDF][Abstract][arXiv]

This article introduces new tools to study self-organisation in a family of simple cellular automata which contain some particle-like 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 4-cyclic cellular automata (introduced in [Fis90b]), one-sided 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. 203-224.

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 35-55.

Travail en collaboration avec N. Aubrun et S. Barbieri.

[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.

μ-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 1623-1647.

Travail en collaboration avec L. Boyer, M. Delacourt, V. Poupet et G. Theyssier.

[PDF][arXiv][Abstract]

This paper is about \mu-limit 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 \mu-random 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_3-hard language, second that it can contain only \alpha-complex confi gurations and third that any non-trivial property concerning these sets is at least \Pi_3-hard. 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 S-adic systems are sofic

Parru dans Uniform Distribution Theory, Volume 9, issue 2, 2014.

Travail en collaboration avec N. Aubrun.

[PDF][arXiv] [Abstract]

In this article we prove that multidimensional effective S-adic 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.35-63, 2013.

Travail en collaboration avec N. Aubrun.

[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): 3800-3821, 2011.

Travail en collaboration avec M. Delacourt, V. Poupet et G. Theyssier.

[PDF] [arXiv] [Abstract]

This paper studies directional dynamics on one-dimensional 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.

Topological Dynamics of Cellular Automata: Dimension Matters

Paru dans Theory of Computing Systems , Volume 48, p693-714, 2011.

Travail en collaboration avec G. Theyssier.

[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 non-recursivity of sensitiv- ity 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 classifi- cation previously obtained in the 1D case. Finally, we show that the set of sensitive CA is only Π₂⁰ in dimension 1, but becomes Σ₃⁰-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), 207-251.
[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 × Z-action (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 d-dimensional spatial differentiation: Application to the formation of sense organs in drosophila.

Paru dans BioSystems, Volume 94, Issues 1-2, October-November 2008, Pages 102-108.

Travail en collaboration avec A. Crumière.

[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 d-dimensional 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 1-3, 9 June 2008, Pages 1-18.
[PDF] [Abstract]

A cellular automaton is a continuous function F defined on a full-shift 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 spatio-temporal structure produced by considering the dynamics of the Z×N-action 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 space-time diagrams.

Measure rigidity for algebraic bipermutative cellular

Paru dans Ergodic Theory and Dynamical Systems, Volume 27, Issue 06, Dec 2007, pp 1965-1990.
[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×Z-action of F and the shift map σ to be the Haar measure on Σ, a closed shift-invariant 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.

Articles acceptés dans des conférences internationales

Domino Problem Under Horizontal Constraints

Accepté à 37th International Symposium on Theoretical Aspects of Computer Science 2020 (STACS 2020).

Travail en collaboration avec N. Aubrun et Julien Esnay.

[PDF][Abstract]

The Domino Problem on Z² asks if it is possible to tile the plane with a given set of Wang tiles; it is a classical decision problem which is known to be undecidable. The purpose of this article is to parameterize this problem to explore the frontier between decidability and undecidability. To do so we fix horizontal constraints H on the tiles and consider a new Domino Problem DP_H: given a vertical constraint, is it possible to tile the plane? We characterize the nearest-neighbor horizontal constraints where DP_H is decidable using graphs combinatorics.

Algorithmic optimization for the realization of an effective subshift by a sofic

Accepté à International Colloquium on Automata, Languages and Programming 2016.

Travail en collaboration avec M. Schraudner.

[PDF][Abstract]

Realization of d-dimensional effective subshifts as projective sub-actions 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 S-adic symbolic dynamical system.

Accepté à Computability in Europe 2016.

Travail en collaboration avec T. Fernique et V. Berthe.

[PDF][Abstract]

We focus in this survey on effectiveness issues for S-adic sub- shifts and tilings. An S-adic 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 multi-dimensional), or a tile by a finite union of tiles. Several notions of effectiveness exist concerning S-adic 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 shift-invariant 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.

Travail en collaboration avec S. Barbieri.

[PDF][Abstract]

We define the domino problem for tilings over self-similar structures of Z^d given by forbidden patterns. In this setting we exhibit non-trivial families of subsets with decidable and undecidable domino problem.

Local Rules for Computable Planar Tilings

Accepté à Automata and Journées Automates Cellulaires 2012.

Travail en collaboration avec T. Fernique.

[PDF][arXiv] [Abstract]

Aperiodic tilings are non-periodic 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 non-periodic tilings, the aperiodic ones. In this paper, we answer this question for the well-studied class of non-periodic 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.

Travail en collaboration avec B. Hellouin De Menibus.

[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.

Self-organization in cellular automata : a particle-based approach

Accepté à Developements in Language Theory 2011.

Travail en collaboration avec B. Hellouin De Menibus.

[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.

Travail en collaboration avec L. Boyer et M. Delacourt.

[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.

Travail en collaboration avec N. Aubrun.

[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.

Travail en collaboration avec G. Theyssier.

[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 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.

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 shift-invariant 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 shift-invariant 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.

Travail en collaboration avec A. Crumière.

[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 shift-invariant topologies

Accepté à Developements in Language Theory 2007, 84-95, Lecture Notes in Comput. Sci., 4588, Springer, Berlin, 2007.

Travail en collaboration avec L. Bienvenue

[PDF] [Abstract]

We study the dynamics of cellular automata, and more specifically their transitivity, when the set of configurations is endowed with a shift-invariant (pseudo-)distance. We first give an original proof of the non-transitivity of cellular automata when the set of configurations is endowed with the Besicovitch pseudo-distance. We then show that the Besicovitch pseudo-distance induces a distance on the set of shift-invariant 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 shift-invariant measures by the Cantor distance.

Prépublications

Characterisation of the Set of Ground States of Uniformly Chaotic Finite-Range Lattice Models

Travail en collaboration avec L. Gayral et S. Taati.

[PDF][Abstract] [arXiv]

Chaotic dependence on temperature refers to the phenomenon of divergence of Gibbs measures as the temperature approaches a certain value. Models with chaotic behaviour near zero temperature have multiple ground states, none of which are stable. We study the class of uniformly chaotic models, that is, those in which, as the temperature goes to zero, every choice of Gibbs measures accumulates on the entire set of ground states. We characterise the possible sets of ground states of uniformly chaotic finite-range models up to computable homeomorphisms.
Namely, we show that the set of ground states of every model with finite-range and rational-valued interactions is topologically closed and connected, and belongs to the class Π2 of the arithmetical hierarchy. Conversely, every Π2-computable, topologically closed and connected set of probability measures can be encoded (via a computable homeomorphism) as the set of ground states of a uniformly chaotic two-dimensional model with finite-range rational-valued interactions.

Strong stochastic stability of cellular automata

Travail en collaboration avec H. Marsan.

[PDF][Abstract] [arXiv]

We define the notion of stochastic stability, already present in the literature in the context of smooth dynamical systems, for invariant measures of cellular automata perturbed by a random noise, and the notion of strongly stochastically stable cellular automaton. We study these notions on basic examples (nilpotent cellular automata, spreading symbols) using different methods inspired by those presented in \cite{MST19}. We then show that this notion of stability is not trivial by proving that a Turing machine cannot decide if a given invariant measure of a cellular automaton is stable under a uniform perturbation.

Soficity of free extensions of effective subshifts

Travail en collaboration avec S. Barbieri et V. Salo.

[PDF][Abstract] [arXiv]

Let G be a group and H⩽G a subgroup. The free extension of an H-subshift X to G is the G-subshift X˜ whose configurations are those for which the restriction to every coset of H is a configuration from X. We study the case of G=H×K for finitely generated groups H and K: on the one hand we show that if K is nonamenable and H has decidable word problem, then the free extension to G of any H-subshift which is effectively closed is a sofic G-subshift. On the other hand we prove that if both H and K are amenable, there are always H-subshifts which are effectively closed by patterns whose free extension to G is non-sofic. We also present a few applications in the form of a new simulation theorem and a new class of groups which admit strongly aperiodic SFTs.

Groups with self-simulable zero-dimensional dynamics

Travail en collaboration avec S. Barbieri et V. Salo.

[PDF][Abstract] [arXiv]

We say that a finitely generated group Γ is (dynamically) self-simulable if every effectively closed action of Γ on a closed subset of {𝟶,𝟷}ℕ is the topological factor of a Γ-subshift of finite type. We show that self-simulable groups exist, that any direct product of non-amenable finitely generated groups is self-simulable, that under technical conditions self-simulability is inherited from subgroups, and that the subclass of self-simulable groups is stable under commensurability and quasi-isometries of finitely presented groups. Some notable examples of self-simulable groups obtained are the direct product Fk×Fk of two free groups of rank k≥2, non-amenable finitely generated branch groups, the simple groups of Burger and Mozes, Thompson's V, the groups GLn(ℤ), SLn(ℤ), Aut(Fn) and Out(Fn) for n≥5; The Braid groups Bm for m≥7, and certain classes of RAAGs. We also show that Thompson's F is self-simulable if and only if F is non-amenable, thus giving a computability characterization of this well-known open problem. We also exhibit a few applications of self-simulability on the dynamics of these groups, notably, that every self-simulable group with decidable word problem admits a nonempty strongly aperiodic subshift of finite type.

Action of cellular automata on shift-invariant measure

[PDF] [Abstract]

In this article we introduce a general process to construct σ-invariant pseudo-distance. 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.

Row-constrained effective sets of colourings in the 2-fold horocyclic tessellations of H² are sofic

Travail en collaboration avec N. Aubrun.

[PDF] [Abstract] [arXiv]

In this article we prove that, restricted to the row-constrained case, effective sets of colourings in the 2-fold horocyclic tessellations of the hyperbolic plane ℍ² are sofic.

Speed of convergence towards an effective subshift

Travail en collaboration avec A. Crumière et M. Schraudner.

[PDF][Abstract] [arXiv]

Realization of d-dimensional effective subshifts as projective sub-actions 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 sub-action 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.

A characterization of the possible entropy dimensions of minimal Z^3-SFT

Travail en collaboration avec S. Gangloff.

[PDF][Abstract] [arXiv]

In this text, we studied another constraint on multidimensional SFT and the effect of this restriction on embedding computations in these subshifts. We prove that this embedding is still possible under this constraint. We adapt a construction by Meyerovitch in order to characterize the possible entropy dimensions of tridimensional SFT. This adaptation involves many information processing mechanisms that are not observed in other constructions in the literature. The main tool is the use of counters that alternates all the "random behaviors" that happen in the configurations of the subshifts. The value of these counters code entirely the behavior of the machines in the computing units. They also have a non-coding part and a suspension mechanism which allow the counter to have a Fermat number as period. Goldbach's theorem ensures that these numbers are all coprime. We use this fact to have the minimality property.

Simulation of minimal effective dynamical systems on the Cantor set by minimal tridimensional SFT

Travail en collaboration avec S. Gangloff.

[PDF][Abstract] [arXiv]

In this text, we explore further the effect of minimality on "dense" computation. This means that, unlike the recent constructions of minimal multidimensional subshifts of finite type by B. Durand and A. Romashchenko, which use a sparse way to implement machines into the subshifts in order to ensure the minimality, we keep the implementation dense. We use the tools developed for the characterization of entropy dimensions of minimal tridimensional SFT, in order to provide a simulation theorem of dynamical systems on the Cantor sets which is robust to minimality constraint. The idea is to encode sequences of the Cantor set in hierarchical structures and make machines control evolution of sequences in a fixed direction. One specific aspect of the construction is that it makes appear a one dimensional full shift degenerated behavior. We thus developped a way to simulate this, using back Fermat number period counters. Moreover, the implementation is done in two dimensional sections, and it needs functional specialisation of the computing units in order to not break the minimality.

On entropies of block-gluing subshifts

Travail en collaboration avec Svetlana Puzynina.

[PDF][Abstract] [arXiv]

A subshift X is called c-block gluing if for any integer n≥c and any two blocks u and v from the language of X there exists an element of X which has occurrences of u and v at distance n. In this note we study the topological entropies of c-block gluing binary one-dimensional subshifts. We define the set Rc to be the set of entropies of all c-block-gluing subshifts, and R=∪c∈ℕRc. We show that the set R is dense, while R1 and R2 are not; in particular, they have isolated points. We conjecture that the same holds for any c.

Travaux en cours

Exploration of rigidity and randomisation problems for expansive cellular automata.

Travail en collaboration avec B. Hellouin De Menibus, I. Marcovici et A. Maass.