10 Search Results for "Theyssier, Guillaume"

Document
DOI: 10.4230/LIPIcs.DNA.31.9
Synchronous Versus Asynchronous Tile-Based Self-Assembly

Authors: Florent Becker, Phillip Drake, Matthew J. Patitz, and Trent A. Rogers

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
In this paper we study the relationship between mathematical models of tile-based self-assembly which differ in terms of the synchronicity of tile additions. In the standard abstract Tile Assembly Model (aTAM), each step of assembly consists of a single tile being added to an assembly. At any given time, each location on the perimeter of an assembly to which a tile can legally bind is called a frontier location, and for each step of assembly one frontier location is randomly selected and a tile is added. In the Synchronous Tile Assembly Model (syncTAM), at each step of assembly every frontier location simultaneously receives a tile. Our results show that while directed, non-cooperative syncTAM systems are capable of universal computation (while directed, non-cooperative aTAM systems are known not to be), and they are capable of building shapes that can't be built within the aTAM, the non-cooperative aTAM is also capable of building shapes that can't be built within the syncTAM even cooperatively. We show a variety of results that demonstrate the similarities and differences between these two models.
Cite as

Florent Becker, Phillip Drake, Matthew J. Patitz, and Trent A. Rogers. Synchronous Versus Asynchronous Tile-Based Self-Assembly. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DNA.31.9,
  author =	{Becker, Florent and Drake, Phillip and Patitz, Matthew J. and Rogers, Trent A.},
  title =	{{Synchronous Versus Asynchronous Tile-Based Self-Assembly}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.9},
  URN =		{urn:nbn:de:0030-drops-238580},
  doi =		{10.4230/LIPIcs.DNA.31.9},
  annote =	{Keywords: self-assembly, noncooperative self-assembly, models of computation, tile assembly systems}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.139
Minimality and Computability of Languages of G-Shifts

Authors: Djamel Eddine Amir and Benjamin Hellouin de Menibus

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for G-shifts, where G is a finitely generated group with decidable word problem. A G-shift has strong computable type if one can compute its language from the complement of its language. We obtain a characterization of G-shifts with strong computable type in terms of a notion of minimality with respect to properties with a bounded computational complexity. We provide a self-contained direct proof, and also explain how this characterization can be obtained from an existing similar characterization for sets by Amir and Hoyrup, and discuss its connexions with results by Jeandel on closure spaces. We apply this characterization to several classes of shifts that are minimal with respect to specific properties. This provides a unifying approach that not only generalizes many existing results but also has the potential to yield new findings effortlessly. In contrast to the case of sets, we prove that strong computable type for G-shifts is preserved under products. We conclude by discussing some generalizations and future directions.
Cite as

Djamel Eddine Amir and Benjamin Hellouin de Menibus. Minimality and Computability of Languages of G-Shifts. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 139:1-139:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.ICALP.2025.139,
  author =	{Amir, Djamel Eddine and Hellouin de Menibus, Benjamin},
  title =	{{Minimality and Computability of Languages of G-Shifts}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{139:1--139:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.139},
  URN =		{urn:nbn:de:0030-drops-235161},
  doi =		{10.4230/LIPIcs.ICALP.2025.139},
  annote =	{Keywords: shifts, subshifts, minimal shifts, computable language, computability, strong computable type, descriptive complexity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2025.24
Brief Announcement: Intrinsic Universality in Seeded Active Tile Self-Assembly

Authors: Tim Gomez, Elise Grizzell, Asher Haun, Ryan Knobel, Tom Peters, Robert Schweller, and Tim Wylie

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
The Tile Automata (TA) model describes self-assembly systems in which monomers can build structures and transition with an adjacent monomer to change their states. This paper shows that seeded TA is a non-committal intrinsically universal model of self-assembly. We present a single universal Tile Automata system containing approximately 4600 states that can simulate (a) the output assemblies created by any other Tile Automata system Γ, (b) the dynamics involved in building Γ’s assemblies, and (c) Γ’s internal state transitions. It does so in a non-committal way: it preserves the full non-deterministic dynamics of a tile’s potential attachment or transition by selecting its state in a single step, considering all possible outcomes until the moment of selection. The system uses supertiles, each encoding the complete system being simulated. The universal system builds supertiles from its seed, each representing a single tile in Γ, transferring the information to simulate Γ to each new tile. Supertiles may also asynchronously transition states according to the rules of Γ. This result also implies IU for pairwise asynchronous Cellular Automata.
Cite as

Tim Gomez, Elise Grizzell, Asher Haun, Ryan Knobel, Tom Peters, Robert Schweller, and Tim Wylie. Brief Announcement: Intrinsic Universality in Seeded Active Tile Self-Assembly. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 24:1-24:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gomez_et_al:LIPIcs.SAND.2025.24,
  author =	{Gomez, Tim and Grizzell, Elise and Haun, Asher and Knobel, Ryan and Peters, Tom and Schweller, Robert and Wylie, Tim},
  title =	{{Brief Announcement: Intrinsic Universality in Seeded Active Tile Self-Assembly}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{24:1--24:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.24},
  URN =		{urn:nbn:de:0030-drops-230772},
  doi =		{10.4230/LIPIcs.SAND.2025.24},
  annote =	{Keywords: Intrinsic Universality, Tile Automata, Cellular Automata, Self-assembly}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.48
Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata

Authors: Benjamin Hellouin de Menibus and Pacôme Perrotin

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Plane-walking automata were introduced by Salo & Törma to recognise languages of two-dimensional infinite words (subshifts), the counterpart of 4-way finite automata for two-dimensional finite words. We extend the model to allow for nondeterminism and alternation of quantifiers. We prove that the recognised subshifts form a strict subclass of sofic subshifts, and that the classes corresponding to existential and universal nondeterminism are incomparable and both larger that the deterministic class. We define a hierarchy of subshifts recognised by plane-walking automata with alternating quantifiers, which we conjecture to be strict.
Cite as

Benjamin Hellouin de Menibus and Pacôme Perrotin. Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hellouindemenibus_et_al:LIPIcs.STACS.2025.48,
  author =	{Hellouin de Menibus, Benjamin and Perrotin, Pac\^{o}me},
  title =	{{Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.48},
  URN =		{urn:nbn:de:0030-drops-228540},
  doi =		{10.4230/LIPIcs.STACS.2025.48},
  annote =	{Keywords: Formal languages, Finite automata, Subshifts, Symbolic dynamics, Tilings}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.154
FO Logic on Cellular Automata Orbits Equals MSO Logic

Authors: Guillaume Theyssier

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We introduce an extension of classical cellular automata (CA) to arbitrary labeled graphs, and show that FO logic on CA orbits is equivalent to MSO logic. We deduce various results from that equivalence, including a characterization of finitely generated groups on which FO model checking for CA orbits is undecidable, and undecidability of satisfiability of a fixed FO property for CA over finite graphs. We also show concrete examples of FO formulas for CA orbits whose model checking problem is equivalent to the domino problem, or its seeded or recurring variants respectively, on any finitely generated group. For the recurring domino problem, we use an extension of the FO signature by a relation found in the well-known Garden of Eden theorem, but we also show a concrete FO formula without the extension and with one quantifier alternation whose model checking problem does not belong to the arithmetical hierarchy on group ℤ².
Cite as

Guillaume Theyssier. FO Logic on Cellular Automata Orbits Equals MSO Logic. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 154:1-154:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{theyssier:LIPIcs.ICALP.2024.154,
  author =	{Theyssier, Guillaume},
  title =	{{FO Logic on Cellular Automata Orbits Equals MSO Logic}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{154:1--154:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.154},
  URN =		{urn:nbn:de:0030-drops-202972},
  doi =		{10.4230/LIPIcs.ICALP.2024.154},
  annote =	{Keywords: MSO logic, FO logic, cellular automata, domino problem, Cayley graphs}
}
Document
DOI: 10.4230/LIPIcs.DNA.28.6
On Turedo Hierarchies and Intrinsic Universality

Authors: Samuel Nalin and Guillaume Theyssier

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)

Abstract
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.
Cite as

Samuel Nalin and Guillaume Theyssier. On Turedo Hierarchies and Intrinsic Universality. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.DNA.28.6},
  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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.51
Oritatami Systems Assemble Shapes No Less Complex Than Tile Assembly Model (ATAM)

Authors: Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, and Guillaume Theyssier

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
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 Π₂-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.
Cite as

Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, and Guillaume Theyssier. Oritatami Systems Assemble Shapes No Less Complex Than Tile Assembly Model (ATAM). In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 51:1-51:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.STACS.2022.51},
  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}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.9
Universal Gauge-Invariant Cellular Automata

Authors: Pablo Arrighi, Marin Costes, and Nathanaël Eon

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Gauge symmetries play a fundamental role in Physics, as they provide a mathematical justification for the fundamental forces. Usually, one starts from a non-interactive theory which governs "matter", and features a global symmetry. One then extends the theory so as make the global symmetry into a local one (a.k.a gauge-invariance). We formalise a discrete counterpart of this process, known as gauge extension, within the Computer Science framework of Cellular Automata (CA). We prove that the CA which admit a relative gauge extension are exactly the globally symmetric ones (a.k.a the colour-blind). We prove that any CA admits a non-relative gauge extension. Both constructions yield universal gauge-invariant CA, but the latter allows for a first example where the gauge extension mediates interactions within the initial CA.
Cite as

Pablo Arrighi, Marin Costes, and Nathanaël Eon. Universal Gauge-Invariant Cellular Automata. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arrighi_et_al:LIPIcs.MFCS.2021.9,
  author =	{Arrighi, Pablo and Costes, Marin and Eon, Nathana\"{e}l},
  title =	{{Universal Gauge-Invariant Cellular Automata}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.9},
  URN =		{urn:nbn:de:0030-drops-144490},
  doi =		{10.4230/LIPIcs.MFCS.2021.9},
  annote =	{Keywords: Cellular automata, Gauge-invariance, Universality}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.32
Rice-Like Theorems for Automata Networks

Authors: Guilhem Gamard, Pierre Guillon, Kevin Perrot, and Guillaume Theyssier

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
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.
Cite as

Guilhem Gamard, Pierre Guillon, Kevin Perrot, and Guillaume Theyssier. Rice-Like Theorems for Automata Networks. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gamard_et_al:LIPIcs.STACS.2021.32,
  author =	{Gamard, Guilhem and Guillon, Pierre and Perrot, Kevin and Theyssier, Guillaume},
  title =	{{Rice-Like Theorems for Automata Networks}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.32},
  URN =		{urn:nbn:de:0030-drops-136770},
  doi =		{10.4230/LIPIcs.STACS.2021.32},
  annote =	{Keywords: Automata networks, Rice theorem, complexity classes, polynomial hierarchy, hardness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1836
On Local Symmetries and Universality in Cellular Automata

Authors: Laurent Boyer and Guillaume Theyssier

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
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 reviously 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.
Cite as

Laurent Boyer and Guillaume Theyssier. On Local Symmetries and Universality in Cellular Automata. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 195-206, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{boyer_et_al:LIPIcs.STACS.2009.1836,
  author =	{Boyer, Laurent and Theyssier, Guillaume},
  title =	{{On Local Symmetries and Universality in Cellular Automata}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{195--206},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1836},
  URN =		{urn:nbn:de:0030-drops-18369},
  doi =		{10.4230/LIPIcs.STACS.2009.1836},
  annote =	{Keywords: Cellular automata, Universality, Asymptotic density}
}
  • Refine by Type
  • 10 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2024
  • 2 2022
  • 2 2021
  • 1 2009

  • Refine by Author
  • 5 Theyssier, Guillaume
  • 2 Hellouin de Menibus, Benjamin
  • 1 Amir, Djamel Eddine
  • 1 Arrighi, Pablo
  • 1 Becker, Florent
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Models of computation
  • 2 Theory of computation → Computability
  • 2 Theory of computation → Formal languages and automata theory
  • 1 Applied computing → Molecular structural biology
  • 1 Computer systems organization → Molecular computing
  • Show More...

  • Refine by Keyword
  • 2 Cellular automata
  • 2 Universality
  • 1 2D Turing machines
  • 1 Arithmetical hierarchy of real numbers
  • 1 Asymptotic density
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact