2 Search Results for "Delacourt, Martin"

Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.6
Rice’s Theorem for Generic Limit Sets of Cellular Automata

Authors: Martin Delacourt

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract
The generic limit set of a cellular automaton is a topologically defined set of configurations that intends to capture the asymptotic behaviours while avoiding atypical ones. It was defined by Milnor then studied by Djenaoui and Guillon first, and by Törmä later. They gave properties of this set related to the dynamics of the cellular automaton, and the maximal complexity of its language. In this paper, we prove that every non trivial property of these generic limit sets of cellular automata is undecidable.
Cite as

Martin Delacourt. Rice’s Theorem for Generic Limit Sets of Cellular Automata. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{delacourt:OASIcs.AUTOMATA.2021.6,
  author =	{Delacourt, Martin},
  title =	{{Rice’s Theorem for Generic Limit Sets of Cellular Automata}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{6:1--6:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.6},
  URN =		{urn:nbn:de:0030-drops-140151},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.6},
  annote =	{Keywords: cellular automata, dynamical systems, generic-limit sets, Rice’s theorem, subshifts}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.262
Construction of mu-Limit Sets of Two-dimensional Cellular Automata

Authors: Martin Delacourt and Benjamin Hellouin de Ménibus

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We prove a characterisation of \mu-limit sets of two-dimensional cellular automata, extending existing results in the one-dimensional case. This sets describe the typical asymptotic behaviour of the cellular automaton, getting rid of exceptional cases, when starting from the uniform measure.
Cite as

Martin Delacourt and Benjamin Hellouin de Ménibus. Construction of mu-Limit Sets of Two-dimensional Cellular Automata. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 262-274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{delacourt_et_al:LIPIcs.STACS.2015.262,
  author =	{Delacourt, Martin and Hellouin de M\'{e}nibus, Benjamin},
  title =	{{Construction of mu-Limit Sets of Two-dimensional Cellular Automata}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{262--274},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.262},
  URN =		{urn:nbn:de:0030-drops-49197},
  doi =		{10.4230/LIPIcs.STACS.2015.262},
  annote =	{Keywords: cellular automata, dynamical systems, mu-limit sets, subshifts, measures}
}
  • Refine by Author
  • 2 Delacourt, Martin
  • 1 Hellouin de Ménibus, Benjamin

  • Refine by Classification
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 2 cellular automata
  • 2 dynamical systems
  • 2 subshifts
  • 1 Rice’s theorem
  • 1 generic-limit sets
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2021

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact