5 Search Results for "Theyssier, Guillaume"


Document
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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 Author
  • 4 Theyssier, Guillaume
  • 1 Arrighi, Pablo
  • 1 Boyer, Laurent
  • 1 Costes, Marin
  • 1 Eon, Nathanaël
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Models of computation
  • 1 Applied computing → Molecular structural biology
  • 1 Computer systems organization → Molecular computing
  • 1 Computing methodologies → Molecular simulation
  • 1 Theory of computation → Complexity classes
  • 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...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2021
  • 2 2022
  • 1 2009

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail