Document Open Access Logo

Construction of mu-Limit Sets of Two-dimensional Cellular Automata

Authors Martin Delacourt, Benjamin Hellouin de Ménibus

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.262.pdf
  • Filesize: 0.64 MB
  • 13 pages

Document Identifiers

Author Details

Martin Delacourt
Benjamin Hellouin de Ménibus

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.STACS.2015.262

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.

Subject Classification

Keywords
  • cellular automata
  • dynamical systems
  • mu-limit sets
  • subshifts
  • measures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alexis Ballier, Pierre Guillon, and Jarkko Kari. Limit sets of stable and unstable cellular automata. Fundam. Inf., 110(1-4):45-57, January 2011. Google Scholar
  2. Laurent Boyer, Martin Delacourt, Victor Poupet, Mathieu Sablik, and Guillaume Theyssier. μ-limit sets of cellular automata from a computational complexity perspective. CoRR, abs/1309.6730, 2014. Google Scholar
  3. Laurent Boyer, Martin Delacourt, and Mathieu Sablik. Construction of μ-limit sets. In JAC, pages 76-87, 2010. Google Scholar
  4. Laurent Boyer, Victor Poupet, and Guillaume Theyssier. On the complexity of limit sets of cellular automata associated with probability measures. In MFCS, pages 190-201, 2006. Google Scholar
  5. Benjamin Hellouin de Menibus and Mathieu Sablik. Characterisation of sets of limit measures after iteration of a cellular automaton on an initial measure. CoRR, abs/1301.1998, 2013. Google Scholar
  6. Martin Delacourt. Rice’s theorem for -limit sets of cellular automata. In ICALP (2), pages 89-100, 2011. Google Scholar
  7. Gustav A. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Mathematical Systems Theory, 3(4):320-375, 1969. Google Scholar
  8. Glenn Hurlbert and Garth Isaak. On the de bruijn torus problem. Journal of Combinatorial Theory, Series A, 64(1):50 - 62, 1993. Google Scholar
  9. J. Kari. Rice’s theorem for the limit sets of cellular automata. Theoretical Computer Science, 127:229-254, 1994. Google Scholar
  10. P. Kůrka and A. Maass. Limit Sets of Cellular Automata Associated to Probability Measures. Journal of Statistical Physics, 100(5-6):1031-1047, 2000. Google Scholar
  11. Alejandro Maass. On the sofic limit sets of cellular automata. Ergodic Theory and Dynamical Systems, 15:663-684, 7 1995. Google Scholar
  12. John von Neumann. Theory of Self-Reproducing Automata. University of Illinois Press, Champaign, IL, USA, 1966. Google Scholar
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 About DROPS Imprint Privacy Contact