Document Open Access Logo

Decidability in Group Shifts and Group Cellular Automata

Authors Pierre Béaur, Jarkko Kari

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.12.pdf
  • Filesize: 458 kB
  • 13 pages

Document Identifiers

Author Details

Pierre Béaur
  • École Normale Supérieure Paris-Saclay, Gif-sur-Yvette, France
Jarkko Kari
  • University of Turku, Finland

Funding

  • Kari, Jarkko: Supported by the Academy of Finland grant 296018.

Cite AsGet BibTex

Pierre Béaur and Jarkko Kari. Decidability in Group Shifts and Group Cellular Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.12

Abstract

Many undecidable questions concerning cellular automata are known to be decidable when the cellular automaton has a suitable algebraic structure. Typical situations include linear cellular automata where the states come from a finite field or a finite commutative ring, and so-called additive cellular automata in the case the states come from a finite commutative group and the cellular automaton is a group homomorphism. In this paper we generalize the setup and consider so-called group cellular automata whose state set is any (possibly non-commutative) finite group and the cellular automaton is a group homomorphism. The configuration space may be any subshift that is a subgroup of the full shift and still many properties are decidable in any dimension of the cellular space. Decidable properties include injectivity, surjectivity, equicontinuity, sensitivity and nilpotency. Non-transitivity is semi-decidable. It also turns out that the the trace shift and the limit set can be effectively constructed, that injectivity always implies surjectivity, and that jointly periodic points are dense in the limit set. Our decidability proofs are based on developing algorithms to manipulate arbitrary group shifts, and viewing the set of space-time diagrams of group cellular automata as multidimensional group shifts.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
  • Theory of computation → Models of computation
Keywords
  • group cellular automata
  • group shifts
  • symbolic dynamics
  • decidability

Metrics

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

References

  1. T. Ceccherini-Silberstein and M. Coornaert. Cellular Automata and Groups. Springer Monographs in Mathematics. Springer Berlin Heidelberg, 2010. Google Scholar
  2. A. Dennunzio, E. Formenti, D. Grinberg, and L. Margara. Dynamical behavior of additive cellular automata over finite abelian groups. Theoretical Computer Science, (in press, available online), 2020. Google Scholar
  3. A. Dennunzio, E. Formenti, L. Manzoni, L. Margara, and A. E. Porreca. On the dynamical behaviour of linear higher-order cellular automata and its decidability. Information Sciences, 486:73-87, 2019. URL: https://doi.org/10.1016/j.ins.2019.02.023.
  4. B. Durand, E. Formenti, and G. Varouchas. On undecidability of equicontinuity classification for cellular automata. In M. Morvan and E. Rémila, editors, Discrete Models for Complex Systems, DMCS'03, Lyon, France, June 16-19, 2003, volume AB of DMTCS Proceedings, pages 117-128. DMTCS, 2003. URL: http://dmtcs.episciences.org/2302.
  5. G. A. Hedlund. Endomorphisms and automorphisms of the shift dynamical systems. Mathematical Systems Theory, 3(4):320-375, 1969. Google Scholar
  6. M. Hochman. On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones Mathematicae, 176(1):131-167, 2009. Google Scholar
  7. J. Kari. The nilpotency problem of one-dimensional cellular automata. SIAM Journal on Computing, 21(3):571-586, 1992. Google Scholar
  8. J. Kari. Reversibility and surjectivity problems of cellular automata. Journal of Computer and System Sciences, 48(1):149-182, 1994. Google Scholar
  9. J. Kari. Theory of cellular automata: A survey. Theoretical Computer Science, 334(1-3):3-33, 2005. Google Scholar
  10. J. Kari. Reversible cellular automata: From fundamental classical results to recent developments. New Generation Computing, 36(3):145-172, 2018. Google Scholar
  11. J. Kari and N. Ollinger. Periodicity and immortality in reversible computing. In E. Ochmanski and J. Tyszkiewicz, editors, Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings, volume 5162 of Lecture Notes in Computer Science, pages 419-430. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-85238-4_34.
  12. B. Kitchens and K. Schmidt. Periodic points, decidability and Markov subgroups. In J. C. Alexander, editor, Dynamical Systems, pages 440-454, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg. Google Scholar
  13. B. Kitchens and K. Schmidt. Automorphisms of compact groups. Ergodic Theory and Dynamical Systems, 9(4):691–735, 1989. Google Scholar
  14. P. Kůrka. Topological and Symbolic Dynamics. Collection SMF. Société mathématique de France, 2003. Google Scholar
  15. D. Lind and B. Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge, 1995. Google Scholar
  16. D. A. Lind. Multi-dimensional symbolic dynamics. In S.G. Williams, editor, Symbolic Dynamics and its Applications, AMS Short Course Lecture Notes, pages 61-79. American Mathematical Society, 2004. Google Scholar
  17. V. Lukkarila. Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata. Journal of Cellular Automata, 5(3):241-272, 2010. URL: http://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-5-number-3-2010/jca-5-3-p-241-272/.
  18. H. Lewis S. Aanderaa. Linear sampling and the ∀∃∀ case of the decision problem. The Journal of Symbolic Logic, 39:519-548, 1974. Google Scholar
  19. K. Schmidt. Dynamical systems of algebraic origin. Progress in mathematics. Birkhäuser Verlag, 1995. Google Scholar
  20. H. Wang. Proving theorems by pattern recognition - II. The Bell System Technical Journal, 40(1):1-41, 1961. 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 Imprint Privacy Contact