Automata networks can be seen as bare finite dynamical systems, but their growing theory has shown the importance of the underlying communication graph of such networks. This paper tackles the question of what dynamics can be realized up to isomorphism if we suppose that the communication graph has bounded degree. We prove several negative results about parameters like the number of fixed points or the rank. We also give bounds on the complexity of the problem of recognizing such dynamics. However, we leave open the embarrassingly simple question of whether a dynamics consisting of a single cycle can be realized with bounded degree.
@article{https://doi.org/10.5281/zenodo.8276252,
doi = {10.5281/ZENODO.8276252},
url = {https://zenodo.org/record/8276252},
author = {Aracena, Julio and Bridoux, Florian and Guillon, Pierre and {Kévin Perrot} and Richard, Adrien and Theyssier, Guillaume},
title = {On the Dynamics of Bounded-Degree Automata Networks},
publisher = {Zenodo},
year = {2023},
copyright = {Creative Commons Attribution 4.0 International}
}
An automata network is a graph of entities, each holding a state from a finite set and evolving according to a local update rule which depends only on its neighbors in the network's graph. It is freezing if there is an order on the states such that the state evolution of any node is non-decreasing in any orbit. They are commonly used to model epidemic propagation, diffusion phenomena like bootstrap percolation or cristal growth. Previous works have established that, under the hypothesis that the network graph is of bounded treewidth, many problems that can be captured by trace specifications at individual nodes admit efficient algorithms. In this paper we study the even more restricted case of a network of bounded pathwidth and show two hardness results that somehow illustrate the complexity of freezing dynamics under such a strong graph constraint. First, we show that the trace specification checking problem is NL-complete. Second, we show that deciding first order properties of the orbits augmented with a reachability predicate is NP-hard.
@article{https://doi.org/10.5281/zenodo.8276242,
doi = {10.5281/ZENODO.8276242},
url = {https://zenodo.org/record/8276242},
author = {Goles, Eric and Montealegre, Pedro and Mart{\'{\i}}n R{\'{\i}}os Wilson and Theyssier, Guillaume},
title = {On the complexity of freezing automata networks of bounded pathwidth},
publisher = {Zenodo},
year = {2023},
copyright = {Creative Commons Attribution 4.0 International}
}
This paper is about turedos, which are Turing machines whose head can move in the plane (or in a higher-dimensional space) but only in a self-avoiding way, by putting marks (letters) on visited positions and moving only to unmarked, therefore unvisited, positions. The turedo model has been introduced recently as a useful abstraction of oritatami systems, which where established a few years ago as a theoretical model of RNA co-transcriptional folding. The key parameter of turedos is their lookup radius: the distance up to which the head can look around in order to make its decision of where to move to and what mark to write. In this paper we study the hierarchy of turedos according to their lookup radius and the dimension of space using notions of simulation up to spatio-temporal rescaling (a standard approach in cellular automata or self-assembly systems). We establish that there is a rich interplay between the turedo parameters and the notion of simulation considered. We show in particular, for the most liberal simulations, the existence of 3D turedos of radius 1 that are intrinsically universal for all radii, but that this is impossible in dimension 2, where some radius 2 turedo are impossible to simulate at radius 1. Using stricter notions of simulation, intrinsic universality becomes impossible, even in dimension 3, and there is a strict radius hierarchy. Finally, when restricting to radius 1, universality is again possible in dimension 3, but not in dimension 2, where we show however that a radius 3 turedo can simulate all radius 1 turedos.
@InProceedings{nalin_et_al:LIPIcs.DNA.28.6,
author = {Nalin, Samuel and Theyssier, Guillaume},
title = {{On Turedo Hierarchies and Intrinsic Universality}},
booktitle = {28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
pages = {6:1--6:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-253-2},
ISSN = {1868-8969},
year = {2022},
volume = {238},
editor = {Ouldridge, Thomas E. and Wickham, Shelley F. J.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16791},
URN = {urn:nbn:de:0030-drops-167915},
doi = {10.4230/LIPIcs.DNA.28.6},
annote = {Keywords: Turedos, intrinsic universality, Higher-dimensional Turing machines, Oritatami systems}
}
This tutorial is about cellular automata that exhibit cold dynamics. By this we mean zero Kolmogorov-Sinai entropy, stabilization of all orbits, trivial asymptotic dynamics, or similar properties. These are essentially transient and irreversible dynamics, but they capture many examples from the literature, ranging from crystal growth to epidemic propagation and symmetric majority vote. A collection of properties is presented and discussed: nilpotency and asymptotic, generic or mu- variants, unique ergodicity, convergence, bounded-changeness, freezingness. They all correspond to the cold dynamics paradigm at various degrees, and we study their links and differences by key examples and results. Besides dynamical considerations, we also focus on computational aspects: we show how such cold cellular automata can still compute under their dynamical constraints, and what are their computational limitations. The purpose of this tutorial is to illustrate how the richness and complexity of the model of cellular automata are preserved under such strong constraints. By putting forward some open questions, it is also an invitation to look more closely at this cold dynamics territory, which is far from being completely understood.
@article{Theyssier_2022,
doi = {10.1007/s11047-022-09886-2},
url = {https://doi.org/10.1007%2Fs11047-022-09886-2},
year = 2022,
month = {may},
publisher = {Springer Science and Business Media {LLC}},
author = {Guillaume Theyssier},
title = {Cold dynamics in cellular automata: a tutorial},
journal = {Natural Computing}
}
We study qualitative properties of two-dimensional freezing cellular automata with a binary state set initialized on a random configuration. If the automaton is also monotone, the setting is equivalent to bootstrap percolation. We explore the extent to which monotonicity constrains the possible asymptotic dynamics by proving two results that do not hold in the subclass of monotone automata. First, it is undecidable whether the automaton almost surely fills the space when initialized on a Bernoulli random configuration with density p, for some/all non-trivial p. Second, there exists an automaton whose space-filling property depends on p in a non-monotone way.
@article{Salo_2022,
doi = {10.1016/j.tcs.2022.04.015},
url = {https://doi.org/10.1016%2Fj.tcs.2022.04.015},
year = 2022,
month = {may},
publisher = {Elsevier {BV}},
author = {Ville Salo and Guillaume Theyssier and Ilkka T{"o}rm{"a}},
title = {Cellular automata and bootstrap percolation},
journal = {Theoretical Computer Science}
}
This note is a survey of examples and results about cellular automata with the purpose of recalling that there is no ‘universal’ way of being computationally universal. In particular, we show how some cellular automata can embed efficient but bounded computation, while others can embed unbounded computations but not efficiently. We also study two variants of Boolean circuit embedding, transient versus repeatable simulations, and underline their differences. Finally we show how strong forms of universality can be hidden inside some seemingly simple cellular automata according to some classical dynamical parameters.
@incollection{Theyssier_2022,
doi = {10.1007/978-3-030-92551-2_5},
url = {https://doi.org/10.1007%2F978-3-030-92551-2_5},
year = 2022,
publisher = {Springer International Publishing},
pages = {57--70},
author = {Guillaume Theyssier},
title = {The Mirage of Universality in Cellular Automata},
booktitle = {Automata and Complexity}
}
Different models have been proposed to understand natural phenomena at the molecular scale from a computational point of view. Oritatami systems are a model of molecular co-transcriptional folding: the transcript (the "molecule") folds as it is synthesized according to a local energy optimisation process, in a similar way to how actual biomolecules such as RNA fold into complex shapes and functions. We introduce a new model, called turedo, which is a self-avoiding Turing machine on the plane that evolves by marking visited positions and that can only move to unmarked positions. Any oritatami can be seen as a particular turedo. We show that any turedo with lookup radius 1 can conversely be simulated by an oritatami, using a universal bead type set. Our notion of simulation is strong enough to preserve the geometrical and dynamical features of these models up to a constant spatio-temporal rescaling (as in intrinsic simulation). As a consequence, turedo can be used as a readable oritatami "higher-level" programming language to build readily oritatami "smart robots", using our explicit simulation result as a compiler. As an application of our simulation result, we prove two new complexity results on the (infinite) limit configurations of oritatami systems (and radius-1 turedos), assembled from a finite seed configuration. First, we show that such limit configurations can embed any recursively enumerable set, and are thus exactly as complex as aTAM limit configurations. Second, we characterize the possible densities of occupied positions in such limit configurations: they are exactly the Pi_2-computable numbers between 0 and 1. We also show that all such limit densities can be produced by one single oritatami system, just by changing the finite seed configuration. None of these results is implied by previous constructions of oritatami embedding tag systems or 1D cellular automata, which produce only computable limit configurations with constrained density.
@InProceedings{pchelina_et_al:LIPIcs.STACS.2022.51,
author = {Pchelina, Daria and Schabanel, Nicolas and Seki, Shinnosuke and Theyssier, Guillaume},
title = {{Oritatami Systems Assemble Shapes No Less Complex Than Tile Assembly Model (ATAM)}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {51:1--51:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-222-8},
ISSN = {1868-8969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15861},
URN = {urn:nbn:de:0030-drops-158618},
doi = {10.4230/LIPIcs.STACS.2022.51},
annote = {Keywords: Molecular Self-assembly, Co-transcriptional folding, Intrinsic simulation, Arithmetical hierarchy of real numbers, 2D Turing machines, Computability}
}
Freezing, Bounded-Change and Convergent Cellular Automata N. Ollinger, G. Theyssier Discrete Mathematics & Theoretical Computer Science (37p.) doi:10.46298/dmtcs.5734 Article complet
This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-K
{u}rka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from convergent cellular automata in dimension~1, but also dimension~1 versus higher dimensions for freezing cellular automata. Another surprising dimension-sensitive result obtained is that nilpotency becomes decidable in dimension~ 1 for all the three classes, while it stays undecidable even for freezing cellular automata in higher dimension.
An automata network is a network of entities, each holding a state from a finite set and evolving according to a local update rule which depends only on its neighbors in the network’s graph. It is freezing if there is an order on states such that the state evolution of any node is non-decreasing in any orbit. They are commonly used to model epidemic propagation, diffusion phenomena like bootstrap percolation or cristal growth. In this paper we establish how alphabet size, treewidth and maximum degree of the underlying graph are key parameters which influence the overall computational complexity of finite freezing automata networks. First, we define a general specification checking problem that captures many classical decision problems such as prediction, nilpotency, predecessor, asynchronous reachability. Then, we present a fast-parallel algorithm that solves the general problem when the three parameters are bounded, hence showing that the problem is in NC. Finally, we show that these problems are hard from two different perspectives. First, the general problem is W[2]-hard when taking either treewidth or alphabet as single parameter and fixing the others. Second, the classical problems are hard in their respective classes when restricted to families of graphs with sufficiently large treewidth.
@incollection{Goles_2021,
doi = {10.1007/978-3-030-80049-9_24},
url = {https://doi.org/10.1007%2F978-3-030-80049-9_24},
year = 2021,
publisher = {Springer International Publishing},
pages = {260--272},
author = {Eric Goles and Pedro Montealegre and Mart{\'{\i}}n R{\'{\i}}os Wilson and Guillaume Theyssier},
title = {On the Impact of Treewidth in the Computational Complexity of Freezing Dynamics},
booktitle = {Lecture Notes in Computer Science}
}
We prove general complexity lower bounds on automata networks, in the style of Rice’s theorem, but in the computable world. Our main result is that testing any fixed first-order property on the dynamics of an automata network is either trivial, or NP-hard, or coNP-hard. Moreover, there exist such properties that are arbitrarily high in the polynomial-time hierarchy. We also prove that testing a first-order property given as input on an automata network (also part of the input) is PSPACE-hard. Besides, we show that, under a natural effectiveness condition, any nontrivial property of the limit set of a nondeterministic network is PSPACE-hard. We also show that it is PSPACE-hard to separate deterministic networks with a very high and a very low number of limit configurations; however, the problem of deciding whether the number of limit configurations is maximal up to a polynomial quantity belongs to the polynomial-time hierarchy.
@inproceedings{https://doi.org/10.4230/lipics.stacs.2021.32,
doi = {10.4230/LIPICS.STACS.2021.32},
url = {https://drops.dagstuhl.de/opus/volltexte/2021/13677/},
author = {Gamard, Guilhem and Guillon, Pierre and Perrot, Kevin and Theyssier, Guillaume},
language = {en},
title = {Rice-Like Theorems for Automata Networks},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
year = {2021},
copyright = {Creative Commons Attribution 4.0 International license}
}
Automata networks are mappings of the form f:Q^Z->Q^Z, where Q is a finite alphabet and Z is a set of entities; they generalise Cellular Automata and Boolean networks. An update schedule dictates when each entity updates its state according to its local function f_i:Q^Z->Q. One major question is to study the behaviour of a given automata networks under different update schedules. In this paper, we study automata networks that are invariant under many different update schedules. This gives rise to two definitions, locally commutative and globally commutative networks. We investigate the relation between commutativity and different forms of locality of update functions; one main conclusion is that globally commutative networks have strong dynamical properties, while locally commutative networks are much less constrained. We also give a complete classification of all globally commutative Boolean networks.
@incollection{Bridoux_2020,
doi = {10.1007/978-3-030-61588-8_4},
url = {https://doi.org/10.1007%2F978-3-030-61588-8_4},
year = 2020,
publisher = {Springer International Publishing},
pages = {43--58},
author = {Florian Bridoux and Maximilien Gadouleau and Guillaume Theyssier},
title = {Commutative Automata Networks},
booktitle = {Cellular Automata and Discrete Complex Systems}
}
An automata network is a finite graph where each node holds a state from some finite alphabet and is equipped with an update function that changes its state according to the configuration of neighboring states. More concisely, it is given by a finite map f:Q^n->Q^n. In this paper we study how some (sets of) automata networks can be simulated by some other (set of) automata networks with prescribed update mode or interaction graph. Our contributions are the following. For non-Boolean alphabets and for any network size, there are intrinsically non-sequential transformations (i.e. that can not be obtained as composition of sequential updates of some network). Moreover there is no universal automaton network that can produce all non-bijective functions via compositions of asynchronous updates. On the other hand, we show that there are universal automata networks for sequential updates if one is allowed to use a larger alphabet and then use either projection onto or restriction to the original alphabet. We also characterize the set of functions that are generated by non-bijective sequential updates. Following Tchuente, we characterize the interaction graphs D whose semigroup of transformations is the full semigroup of transformations on 𝑄𝑛, and we show that they are the same if we force either sequential updates only, or all asynchronous updates.
@incollection{Bridoux_2020,
doi = {10.1007/978-3-030-51466-2_24},
url = {https://doi.org/10.1007%2F978-3-030-51466-2_24},
year = 2020,
publisher = {Springer International Publishing},
pages = {277--288},
author = {Florian Bridoux and Maximilien Gadouleau and Guillaume Theyssier},
title = {On Simulation in Automata Networks},
booktitle = {Lecture Notes in Computer Science}
}
An Automata Network is a map f:Q->Q where Q is a finite alphabet. It can be viewed as a network of n entities, each holding a state from Q, and evolving according to a deterministic synchronous update rule in such a way that each entity only depends on its neighbors in the network's graph, called interaction graph. In this work we introduce the following property called expansivity: the observation of the sequence of states at any given node is sufficient to determine the initial configuration of the whole network. A major trend in automata network theory is to understand how the interaction graph affects dynamical properties of f. Our first result is a characterization of interaction graphs that allow expansivity. Moreover, we show that this property is generic among linear automata networks over such graphs with large enough alphabet. We show however that the situation is more complex when the alphabet is fixed independently of the size of the interaction graph: no alphabet is sufficient to obtain expansivity on all admissible graphs, and only non-linear solutions exist in some cases. Besides, we show striking differences between the linear and the general non-linear case, in particular we prove that deciding expansivity is PSPACE-complete in the general case, while it can be done in polynomial time in the linear case. Finally, we consider a stronger version of expansivity where we ask to determine the initial configuration from any large enough observation of the system. We show that it can be achieved for any number of nodes and naturally gives rise to maximum distance separable codes.
@article{Bridoux_2020,
doi = {10.1016/j.tcs.2020.06.019},
url = {https://doi.org/10.1016%2Fj.tcs.2020.06.019},
year = 2020,
month = {dec},
publisher = {Elsevier {BV}},
volume = {843},
pages = {25--44},
author = {Florian Bridoux and Maximilien Gadouleau and Guillaume Theyssier},
title = {Expansive automata networks},
journal = {Theoretical Computer Science}
}
We introduce the notion of pre-expansivity for cellular automata (CA): it is the property of being positively expansive on asymptotic pairs of configurations (i.e. configurations that differ in only finitely many positions). Pre-expansivity therefore lies between positive expansivity and pre-injectivity, two important notions of CA theory. We show that there exist one-dimensional pre-expansive CAs which are not positively expansive and they can be chosen reversible (while positive expansivity is impossible for reversible CAs). We provide both linear and non-linear examples. In the one-dimensional setting, we also show that pre-expansivity implies sensitivity to initial conditions in any direction. We show however that no two-dimensional Abelian CA can be pre-expansive. We also consider the finer notion of k-expansivity (positive expansivity over pairs of configurations with exactly k differences) and show examples of linear CA in dimension 2 and on the free group that are k-expansive depending on the value of k, whereas no (positively) expansive CA exists in this setting.
@article{Gajardo_2020,
doi = {10.1016/j.tcs.2019.10.034},
url = {https://doi.org/10.1016%2Fj.tcs.2019.10.034},
year = 2020,
month = {may},
publisher = {Elsevier {BV}},
volume = {816},
pages = {37--66},
author = {A. Gajardo and V. Nesme and G. Theyssier},
title = {Pre-expansivity in cellular automata},
journal = {Theoretical Computer Science}
}
Characterizing asymptotic randomization in abelian cellular automata B. Hellouin de Menibus, V. Salo, G. Theyssier Ergodic Theory and Dynamical Systems (21p.) doi:10.1017/etds.2018.75 Article complet
Abelian cellular automata (CAs) are CAs which are group endomorphisms of the full group shift when endowing the alphabet with an abelian group structure. A CA randomizes an initial probability measure if its iterated images have weak*-convergence towards the uniform Bernoulli measure (the Haar measure in this setting). We are interested in structural phenomena, i.e., randomization for a wide class of initial measures (under some mixing hypotheses). First, we prove that an abelian CA randomizes in Cesàro mean if and only if it has no soliton, i.e., a non-zero finite configuration whose time evolution remains bounded in space. This characterization generalizes previously known sufficient conditions for abelian CAs with scalar or commuting coefficients. Second, we exhibit examples of strong randomizers, i.e., abelian CAs randomizing in simple convergence; this is the first proof of this behaviour to our knowledge. We show, however, that no CA with commuting coefficients can be strongly randomizing. Finally, we show that some abelian CAs achieve partial randomization without being randomizing: the distribution of short finite words tends to the uniform distribution up to some threshold, but this convergence fails for larger words. Again this phenomenon cannot happen for abelian CAs with commuting coefficients.
@article{HELLOUIN_DE_MENIBUS_2018,
doi = {10.1017/etds.2018.75},
url = {https://doi.org/10.1017%2Fetds.2018.75},
year = 2018,
month = {sep},
publisher = {Cambridge University Press ({CUP})},
volume = {40},
number = {4},
pages = {923--952},
author = {B. HELLOUIN DE MENIBUS and V. SALO and G. THEYSSIER},
title = {Characterizing asymptotic randomization in abelian cellular automata},
journal = {Ergodic Theory and Dynamical Systems}
}
Cellular Automata have been used since their introduction as a discrete tool of modelization. In many of the physical processes one may modelize thus (such as bootstrap percolation, forest fire or epidemic propagation models, life without death, etc), each local change is irreversible. The class of freezing Cellular Automata (FCA) captures this feature. In a freezing cellular automaton the states are ordered and the cells can only decrease their state according to this “freezing-order”. We investigate the dynamics of such systems through the questions of simulation and universality in this class: is there a Freezing Cellular Automaton (FCA) that is able to simulate any Freezing Cellular Automata, i.e. an intrinsically universal FCA? We show that the answer to that question is sensitive to both the number of changes cells are allowed to make, and geometric features of the space. In dimension 1, there is no universal FCA. In dimension 2, if either the number of changes is at least 2, or the neighborhood is Moore, then there are universal FCA. On the other hand, there is no universal FCA with one change and Von Neumann neighborhood. We also show that monotonicity of the local rule with respect to the freezing-order (a common feature of bootstrap percolation) is also an obstacle to universality.
@incollection{Becker_2018,
doi = {10.1007/978-3-319-94418-0_5},
url = {https://doi.org/10.1007%2F978-3-319-94418-0_5},
year = 2018,
publisher = {Springer International Publishing},
pages = {50--59},
author = {Florent Becker and Diego Maldonado and Nicolas Ollinger and Guillaume Theyssier},
title = {Universality in Freezing Cellular Automata},
booktitle = {Sailing Routes in the World of Computation}
}
On the complexity of two-dimensional signed majority cellular automata E. Goles, P. Montealegre, K. Perrot, G. Theyssier Journal of Computer and System Sciences (32p.) doi:10.1016/j.jcss.2017.07.010 Article complet
We study the complexity of signed majority cellular automata on the planar grid. We show that, depending on their symmetry and uniformity, they can simulate different types of logical circuitry under different modes. We use this to establish new bounds on their overall complexity, concretely: the uniform asymmetric and the non-uniform symmetric rules are Turing universal and have a P-complete prediction problem; the non-uniform asymmetric rule is intrinsically universal; no symmetric rule can be intrinsically universal. We also show that the uniform asymmetric rules exhibit cycles of super-polynomial length, whereas symmetric ones are known to have bounded cycle length.
@article{Goles_2018,
doi = {10.1016/j.jcss.2017.07.010},
url = {https://doi.org/10.1016%2Fj.jcss.2017.07.010},
year = 2018,
month = {feb},
publisher = {Elsevier {BV}},
volume = {91},
pages = {1--32},
author = {Eric Goles and Pedro Montealegre and K{'{e}}vin Perrot and Guillaume Theyssier},
title = {On the complexity of two-dimensional signed majority cellular automata},
journal = {Journal of Computer and System Sciences}
}
In this article we study the minimum number κ of additional automata that a Boolean automata network (BAN) associated with a given block-sequential update schedule needs in order to simulate a given BAN with a parallel update schedule. We introduce a graph that we call 𝖭𝖤𝖢𝖢 graph built from the BAN and the update schedule. We show the relation between κ and the chromatic number of the 𝖭𝖤𝖢𝖢 graph. Thanks to this 𝖭𝖤𝖢𝖢 graph, we bound κ in the worst case between n / 2 and 2n/3+2 (n being the size of the BAN simulated) and we conjecture that this number equals n / 2. We support this conjecture with two results: the clique number of a 𝖭𝖤𝖢𝖢 graph is always less than or equal to n / 2 and, for the subclass of bijective BANs, κ is always less than or equal to n/2+1.
@incollection{Bridoux_2017,
doi = {10.1007/978-3-319-55911-7_9},
url = {https://doi.org/10.1007%2F978-3-319-55911-7_9},
year = 2017,
publisher = {Springer International Publishing},
pages = {112--128},
author = {Florian Bridoux and Pierre Guillon and K{'{e}}vin Perrot and Sylvain Sen{'{e}} and Guillaume Theyssier},
title = {On the Cost of Simulating a Parallel Boolean Automata Network by a Block-Sequential One},
booktitle = {Lecture Notes in Computer Science}
}
A large part of the study of cellular automata dynamics consists in comparing pairs of configurations and their orbits. Here we focus on pairs of configurations having a finite number of differences (diamonds) like in the celebrated Garden-of-Eden theorem. First, we show that it allows to study expansive-like phenomena where classical notions of chaotic behavior like positive expansivity or strong transitivity don’t apply (in reversible CAs for instance). Second, we establish that for a large class of linear CA, diffusion of diamonds is equivalent to randomization (a large class of probability measures converge weakly towards the uniform measure under the action of the CA). Both properties are also equivalent to the absence of gliders in the CA. Finally, we give examples of reversible linear CAs that are strong randomizers (the convergence towards the uniform measure is simple and not only in Cesaro mean). This strong behavior is however provably impossible with linear CA having commuting coefficients (e.g. linear CA over cyclic groups).
@incollection{Theyssier_2016,
doi = {10.1007/978-3-319-39300-1_1},
url = {https://doi.org/10.1007%2F978-3-319-39300-1_1},
year = 2016,
publisher = {Springer International Publishing},
pages = {3--9},
author = {Guillaume Theyssier},
title = {Propagation, Diffusion and Randomization in Cellular Automata},
booktitle = {Cellular Automata and Discrete Complex Systems}
}
μ-Limit sets of cellular automata from a computational complexity perspective L. Boyer, M. Delacourt, V. Poupet, M. Sablik, G. Theyssier Journal of Computer and System Sciences (41p.) doi:10.1016/j.jcss.2015.05.004 Article complet
This paper concerns μ-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial μ-random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, μ-limit sets can have a Σ3-hard language, second, they can contain only α-complex configurations, third, any non-trivial property concerning them is at least Π3-hard. We prove complexity upper bounds, study restrictions of these questions to particular classes of CA, and different types of (non-)convergence of the measure of a word during the evolution.
@article{Boyer_2015,
doi = {10.1016/j.jcss.2015.05.004},
url = {https://doi.org/10.1016%2Fj.jcss.2015.05.004},
year = 2015,
month = {dec},
publisher = {Elsevier {BV}},
volume = {81},
number = {8},
pages = {1623--1647},
author = {L. Boyer and M. Delacourt and V. Poupet and M. Sablik and G. Theyssier},
title = {mu-Limit sets of cellular automata from a computational complexity perspective},
journal = {Journal of Computer and System Sciences}
}
We introduce the class of freezing cellular automata (CA): those where the state of a cell can only increase according to some order on states. It contains some well-studied examples like the bootstrap percolation CA or 'life without death' , but here we aim at studying the class as a whole and deriving general properties of freezing CA. Our focus is mainly on the complexity of these CA and we show that, if their definition imposes strong constraints on their possible dynamics, they still can produce complex computational behaviors, even in dimension 1. Our main results are that the prediction problem of these CA can be P-complete in dimension 2 or more, but is always NL in dimension 1. Moreover its communication complexity is always at most O(n d−1 log(n)) in dimension d (while it can be Ω(n d) for a CA in general). As another dimension-sensitive property, we show that the nilpotency problem is decidable in dimension 1 but not in higher dimension. Finally, although simpler, we show that one-dimensional freezing CA can still be Turing universal.
@inproceedings{goles:hal-01294144,
TITLE = {{Introducing Freezing Cellular Automata}},
AUTHOR = {Goles, Eric and Ollinger, Nicolas and Theyssier, Guillaume},
URL = {https://hal.archives-ouvertes.fr/hal-01294144},
BOOKTITLE = {{Cellular Automata and Discrete Complex Systems, 21st International Workshop (AUTOMATA 2015)}},
ADDRESS = {Turku, Finland},
SERIES = {TUCS Lecture Notes},
VOLUME = {24},
PAGES = {65--73},
YEAR = {2015},
MONTH = Jun,
KEYWORDS = {cellular automata ; bootstrap percolation ; self-assembly tiling ; complexity},
PDF = {https://hal.archives-ouvertes.fr/hal-01294144/file/ifca.pdf},
HAL_ID = {hal-01294144},
HAL_VERSION = {v1},
}
Strict Majority Bootstrap Percolation in the r-wheel M. A. Kiwi, P. Moisset de Espanés, I. Rapaport, S. Rica, G. Theyssier Information Processing Letters (12p.) doi:10.1016/j.ipl.2014.01.005 Article complet
In this paper we study the strict majority bootstrap percolation process on graphs. Vertices may be active or passive. Initially, active vertices are chosen independently with probability p. Each passive vertex becomes active if at least half of its neighbors are active (and thereafter never changes its state). If at the end of the process all vertices become active then we say that the initial set of active vertices percolates on the graph. We address the problem of finding graphs for which percolation is likely to occur for small values of p. Specifically, we study a graph that we call r-wheel: a ring of n vertices augmented with a universal vertex where each vertex in the ring is connected to its r closest neighbors to the left and to its r closest neighbors to the right. We prove that the critical probability is 1/4. In other words, if p>1/4 then for large values of r percolation occurs with probability arbitrarily close to 1 as n goes to infinity. On the other hand, if p<1/4 then the probability of percolation is bounded away from 1.
@article{Kiwi_2014,
doi = {10.1016/j.ipl.2014.01.005},
url = {https://doi.org/10.1016%2Fj.ipl.2014.01.005},
year = 2014,
month = {jun},
publisher = {Elsevier {BV}},
volume = {114},
number = {6},
pages = {277--281},
author = {M. Kiwi and P. Moisset de Espan{'{e}}s and I. Rapaport and S. Rica and G. Theyssier},
title = {Strict Majority Bootstrap Percolation in the r-wheel},
journal = {Information Processing Letters}
}
We prove a negative result on the power of a model of algorithmic self-assembly for which finding general techniques and results has been notoriously difficult. Specifically, we prove that Winfree's abstract Tile Assembly Model is not intrinsically universal when restricted to use noncooperative tile binding. This stands in stark contrast to the recent result that the abstract Tile Assembly Model is indeed intrinsically universal when cooperative binding is used (FOCS 2012). Noncooperative self-assembly, also known as 'temperature 1', is where all tiles bind to each other if they match on at least one side. On the other hand, cooperative self-assembly requires that some tiles bind on at least two sides. Our result shows that the change from non-cooperative to cooperative binding qualitatively improves the range of dynamics and behaviors found in these models of nanoscale self-assembly. The result holds in both two and three dimensions; the latter being quite surprising given that three-dimensional noncooperative tile assembly systems simulate Turing machines. This shows that Turing universal behavior in self-assembly does not imply the ability to simulate all algorithmic self-assembly processes. In addition to the negative result, we exhibit a three-dimensional noncooperative self-assembly tile set capable of simulating any two-dimensional noncooperative self-assembly system. This tile set implies that, in a restricted sense, non-cooperative self-assembly is intrinsically universal for itself.
@inproceedings{Meunier_2013,
doi = {10.1137/1.9781611973402.56},
url = {https://doi.org/10.1137%2F1.9781611973402.56},
year = 2013,
month = {dec},
publisher = {Society for Industrial and Applied Mathematics},
author = {Pierre-Etienne Meunier and Matthew J. Patitz and Scott M. Summers and Guillaume Theyssier and Andrew Winslow and Damien Woods},
title = {Intrinsic universality in tile self-assembly requires cooperation},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM}-{SIAM} Symposium on Discrete Algorithms}
}
Stochastic Cellular Automata: Correlations, Decidability and Simulations P. Arrighi, N. Schabanel, G. Theyssier Fundamentae Informaticae (35p.) doi:10.3233/FI-2013-875 Article complet
This paper introduces a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in an unified and composable manner. This formalism allows for local probabilistic correlations, a feature which is not present in usual definitions. We show that this feature allows for strictly more behaviors (for instance, number conserving stochastic cellular automata require these local probabilistic correlations). We also show that several problems which are deceptively simple in the usual definitions, become undecidable when we allow for local probabilistic correlations, even in dimension one. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochastic settings. Although the intrinsic simulation relation is shown to become undecidable in dimension two and higher, we provide explicit tools to prove or disprove the existence of such a simulation between any two given stochastic cellular automata. Those tools rely upon a characterization of equality of stochastic global maps, shown to be equivalent to the existence of a stochastic coupling between the random sources. We apply them to prove that there is no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality, as well as a universal non-deterministic cellular automaton.
@article{Arrighi_Schabanel_Theyssier_2013, place={NL}, title={Stochastic Cellular Automata: Correlations, Decidability and Simulations}, volume={126}, ISSN={01692968}, url={https://doi.org/10.3233/FI-2013-875}, DOI={10.3233/FI-2013-875}, number={2-3}, journal={Fundamenta Informaticae}, publisher={IOS Press}, author={Arrighi, Pablo and Schabanel, Nicolas and Theyssier, Guillaume}, year={2013}, pages={121-156} }
Asymptotically almost all lambda-terms are strongly normalizing R. David, C. Raffali, K. Grygiel, J. Kozik, G. Theyssier, M. Zaionc Logical Methods in Computer Science (38p.) doi:10.2168/LMCS-9(1:2)2013 Article complet
We present quantitative analysis of various (syntactic and behavioral) properties of random lambda-terms. Our main results are that asymptotically all the terms are strongly normalizing and that any fixed closed term almost never appears in a random term. Surprisingly, in combinatory logic (the translation of the lambda-calculus into combinators), the result is exactly opposite. We show that almost all terms are not strongly normalizing. This is due to the fact that any fixed combinator almost always appears in a random combinator.
@article{David_2013,
doi = {10.2168/lmcs-9(1:2)2013},
url = {https://doi.org/10.2168%2Flmcs-9%281%3A2%292013},
year = 2013,
month = {feb},
publisher = {Logical Methods in Computer Science e.V.},
volume = {9},
number = {1},
author = {Ren{'{e}} David and Katarzyna Grygiel and Jakub Kozik and Christophe Raffalli and Guillaume Theyssier and Marek Zaionc},
editor = {Henk Barendregt},
title = {Asymptotically almost all lambda-terms are strongly normalizing},
journal = {Logical Methods in Computer Science}
}
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.
@article{Jeandel_2013,
doi = {10.1016/j.ic.2013.01.003},
url = {https://doi.org/10.1016%2Fj.ic.2013.01.003},
year = 2013,
month = {apr},
publisher = {Elsevier {BV}},
volume = {225},
pages = {1--15},
author = {Emmanuel Jeandel and Guillaume Theyssier},
title = {Subshifts as models for {MSO} logic},
journal = {Information and Computation}
}
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.
@article{Arrighi_2012,
doi = {10.4204/eptcs.90.17},
url = {https://doi.org/10.4204%2Feptcs.90.17},
year = 2012,
month = {aug},
publisher = {Open Publishing Association},
volume = {90},
pages = {208--224},
author = {Pablo Arrighi and Nicolas Schabanel and Guillaume Theyssier},
title = {Intrinsic Simulations between Stochastic Cellular Automata},
journal = {Electronic Proceedings in Theoretical Computer Science}
}
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.
Clandestine Simulations in Cellular Automata P. Guillon, P.-E. Meunier, G. Theyssier JAC 2010 (18p.) Article complet
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.
Bulking II: Classifications of Cellular Automata M. Delorme, J. Mazoyer, N. Ollinger, G. Theyssier Theoretical Computer Science (42p.) doi:10.1016/j.tcs.2011.02.024 Article complet
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.
@article{Delorme_2011,
doi = {10.1016/j.tcs.2011.02.024},
url = {https://doi.org/10.1016%2Fj.tcs.2011.02.024},
year = 2011,
month = {jul},
publisher = {Elsevier {BV}},
volume = {412},
number = {30},
pages = {3881--3905},
author = {M. Delorme and J. Mazoyer and N. Ollinger and G. Theyssier},
title = {Bulking {II}: Classifications of cellular automata},
journal = {Theoretical Computer Science}
}
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.
@article{Delorme_2011,
doi = {10.1016/j.tcs.2011.02.023},
url = {https://doi.org/10.1016%2Fj.tcs.2011.02.023},
year = 2011,
month = {jul},
publisher = {Elsevier {BV}},
volume = {412},
number = {30},
pages = {3866--3880},
author = {M. Delorme and J. Mazoyer and N. Ollinger and G. Theyssier},
title = {Bulking I: An abstract theory of bulking},
journal = {Theoretical Computer Science}
}
Directional Dynamics along Arbitrary Curves in Cellular Automata M. Delacourt, V. Poupet, M. Sablik, G. Theyssier Theoretical Computer Science (37p.) doi:10.1016/j.tcs.2011.02.019 Article complet
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.
@article{Delacourt_2011,
doi = {10.1016/j.tcs.2011.02.019},
url = {https://doi.org/10.1016%2Fj.tcs.2011.02.019},
year = 2011,
month = {jul},
publisher = {Elsevier {BV}},
volume = {412},
number = {30},
pages = {3800--3821},
author = {M. Delacourt and V. Poupet and M. Sablik and G. Theyssier},
title = {Directional dynamics along arbitrary curves in cellular automata},
journal = {Theoretical Computer Science}
}
Communication Complexity and Intrinsic Universality in Cellular Automata E. Goles, P.-E. Meunier, I. Rapaport, G. Theyssier Theoretical Computer Science (32p.) doi:10.1016/j.tcs.2010.10.005 Article completErratum
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.
@article{Goles_2011,
doi = {10.1016/j.tcs.2010.10.005},
url = {https://doi.org/10.1016%2Fj.tcs.2010.10.005},
year = 2011,
month = {jan},
publisher = {Elsevier {BV}},
volume = {412},
number = {1-2},
pages = {2--21},
author = {E. Goles and P.-E. Meunier and I. Rapaport and G. Theyssier},
title = {Communication complexity and intrinsic universality in cellular automata},
journal = {Theoretical Computer Science}
}
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.
@incollection{Boyer_2010,
doi = {10.1007/978-3-642-15155-2_20},
url = {https://doi.org/10.1007%2F978-3-642-15155-2_20},
year = 2010,
publisher = {Springer Berlin Heidelberg},
pages = {209--220},
author = {Laurent Boyer and Guillaume Theyssier},
title = {On Factor Universality in Symbolic Spaces},
booktitle = {Mathematical Foundations of Computer Science 2010}
}
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.
@article{Sablik_2010,
doi = {10.1007/s00224-010-9255-x},
url = {https://doi.org/10.1007%2Fs00224-010-9255-x},
year = 2010,
month = {apr},
publisher = {Springer Science and Business Media {LLC}},
volume = {48},
number = {3},
pages = {693--714},
author = {Mathieu Sablik and Guillaume Theyssier},
title = {Topological Dynamics of Cellular Automata: Dimension Matters},
journal = {Theory of Computing Systems}
}
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).
@incollection{Jeandel_2009,
doi = {10.1007/978-3-642-02737-6_23},
url = {https://doi.org/10.1007%2F978-3-642-02737-6_23},
year = 2009,
publisher = {Springer Berlin Heidelberg},
pages = {288--299},
author = {Emmanuel Jeandel and Guillaume Theyssier},
title = {Subshifts, Languages and Logic},
booktitle = {Developments in Language Theory}
}
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.
@article{https://doi.org/10.4230/lipics.stacs.2009.1836,
doi = {10.4230/LIPICS.STACS.2009.1836},
url = {http://drops.dagstuhl.de/opus/volltexte/2009/1836/},
author = {Boyer, Laurent and Theyssier, Guillaume},
keywords = {Computer Science, 000 Computer science, knowledge, general works},
language = {en},
title = {On Local Symmetries and Universality in Cellular Automata},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany},
year = {2009}
}
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.
@incollection{Sablik_2008,
doi = {10.1007/978-3-540-69407-6_56},
url = {https://doi.org/10.1007%2F978-3-540-69407-6_56},
year = 2008,
publisher = {Springer Berlin Heidelberg},
pages = {523--532},
author = {Mathieu Sablik and Guillaume Theyssier},
title = {Topological Dynamics of 2D Cellular Automata},
booktitle = {Logic and Theory of Algorithms}
}
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.
@incollection{Boyer_2006,
doi = {10.1007/11821069_17},
url = {https://doi.org/10.1007%2F11821069_17},
year = 2006,
publisher = {Springer Berlin Heidelberg},
pages = {190--201},
author = {Laurent Boyer and Victor Poupet and Guillaume Theyssier},
title = {On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures},
booktitle = {Lecture Notes in Computer Science}
}
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.
@incollection{Theyssier_2005,
doi = {10.1007/978-3-540-31856-9_10},
url = {https://doi.org/10.1007%2F978-3-540-31856-9_10},
year = 2005,
publisher = {Springer Berlin Heidelberg},
pages = {121--132},
author = {Guillaume Theyssier},
title = {How Common Can Be Universality for Cellular Automata?},
booktitle = {{STACS} 2005}
}
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.
@incollection{Theyssier_2004,
doi = {10.1007/978-3-540-28629-5_32},
url = {https://doi.org/10.1007%2F978-3-540-28629-5_32},
year = 2004,
publisher = {Springer Berlin Heidelberg},
pages = {427--438},
author = {Guillaume Theyssier},
title = {Captive Cellular Automata},
booktitle = {Lecture Notes in Computer Science}
}
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.
@article{D_rr_2004,
doi = {10.1016/j.tcs.2004.03.017},
url = {https://doi.org/10.1016%2Fj.tcs.2004.03.017},
year = 2004,
month = {aug},
publisher = {Elsevier {BV}},
volume = {322},
number = {2},
pages = {355--368},
author = {Christoph Dürr and Ivan Rapaport and Guillaume Theyssier},
title = {Cellular automata and communication complexity},
journal = {Theoretical Computer Science}
}