Algorithms for Group Cellular Automata | SpringerLink
Skip to main content
Springer Nature Link
Log in

Algorithms for Group Cellular Automata

  • Conference paper
  • First Online:
Proceedings of First Asian Symposium on Cellular Automata Technology (ASCAT 2022)

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 1425))

Included in the following conference series:

Abstract

We consider subshifts and cellular automata in the setup where the state set is a finite group. The group does not need to be commutative. A subshift that is also a subgroup is called a group shift, and we call a cellular automaton on a group shift a group cellular automaton if it is also a group homomorphism. Group cellular automata generalize the much studied concept of additive cellular automata into non-commutative groups. The set of space-time diagrams of a group cellular automaton is a group shift, so we can apply classical results by Bruce Kitchens and Klaus Schmidt on group shifts to analyze group cellular automata. In particular, we can effectively construct the limit set and the trace subshifts of any group cellular automaton. We can then algorithmically decide many properties concerning the cellular automaton that are in general undecidable. The talk is based on a joint work with Pierre Béaur.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 20591
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 25739
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Aanderaa, S., Lewis, H.: Linear sampling and the \(\forall \exists \forall \) case of the decision problem. J. Symb. Logic 39(3), 519–548 (1974)

    Article  MathSciNet  Google Scholar 

  2. Amoroso, S., Patt, Y.N.: Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J. Comput. Syst. Sci. 6(5), 448–464 (1972)

    Article  MathSciNet  Google Scholar 

  3. Béaur, P., Kari, J.: Decidability in group shifts and group cellular automata. In: Esparza, J., Král’, D. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020. Volume 170 of LIPIcs, pp. 12:1–12:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  4. Blanchard, F., Tisseur, P.: Some properties of cellular automata with equicontinuity points. Annales de l’I.H.P. Probabilité et statistiques 36(5), 569–582 (2000)

    Google Scholar 

  5. Boyle, M., Kitchens, B.: Periodic points for onto cellular automata. Indagationes Mathematicae 10, 483–493 (1999)

    Google Scholar 

  6. Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, Berlin Heidelberg (2010)

    Google Scholar 

  7. Dennunzio, A., Formenti, E., Grinberg, D., Margara, L.: Additive cellular automata over finite abelian groups: Topological and measure theoretic properties. In: Rossmanith, P., Heggernes, P., Katoen, J.-P. (eds.) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019

    Google Scholar 

  8. Fiorenzi, F.: Cellular automata and strongly irreducible shifts of finite type. Theor. Comput. Sci. 299(1), 477–493 (2003)

    Article  MathSciNet  Google Scholar 

  9. Kari, J.: Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48(1), 149–182 (1994)

    Article  MathSciNet  Google Scholar 

  10. Kari, J.: The nilpotency problem of one-dimensional cellular automata. SIAM J. Comput. 21(3), 571–586 (1992)

    Article  MathSciNet  Google Scholar 

  11. Kari, J., Ollinger, N.: Periodicity and immortality in reversible computing. In: Ochmański, E., Tyszkiewicz, J. (eds.) Mathematical Foundations of Computer Science 2008, MFCS 2008, volume 5162 of Lecture Notes in Computer Science, pp. 419–430. Springer (2008)

    Google Scholar 

  12. Kitchens, B., Schmidt, K.: Automorphisms of compact groups. Ergodic Theory Dyn. Syst. 9(4), 691–735 (1989)

    Article  MathSciNet  Google Scholar 

  13. Lukkarila, V.: Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata. J. Cellular Automata 5(3), 241–272 (2010)

    MathSciNet  MATH  Google Scholar 

  14. Manzini, G., Margara, L.: A complete and efficiently computable topological classification of d-dimensional linear cellular automata over \(Z_m\). Theor. Comput. Sci. 221(1), 157–177 (1999)

    Article  Google Scholar 

  15. Margara, L.: On some topological properties of linear cellular automata. In: Kutyłowski, M., Pacholski, L., Wierzbicki, T. (eds.) Mathematical Foundations of Computer Science 1999, MFCS 1999, volume 1672 of Lecture Notes in Computer Science, pp. 209–219. Springer (1999)

    Google Scholar 

  16. Sablik, M., Theyssier, G.: Topological dynamics of 2d cellular automata. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds.) Logic and Theory of Algorithms, 4th Conference on Computability in Europe, CiE 2008, volume 5028 of Lecture Notes in Computer Science, pp. 523–532. Springer (2008)

    Google Scholar 

  17. Sato, T.: Decidability for some problems of linear cellular automata over finite commutative rings. Inform. Process. Lett. 46(3), 151–155 (1993)

    Article  MathSciNet  Google Scholar 

  18. Wang, H.: Proving theorems by pattern recognition—II. Bell Syst. Tech. J. 40(1), 1–41 (1961)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, University of Turku, Turku, Finland

    Jarkko Kari

Authors
  1. Jarkko Kari
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jarkko Kari .

Editor information

Editors and Affiliations

  1. Department of Information Technology, Indian Institute of Engineering Science and Technology, Shibpur, Howrah, West Bengal, India

    Sukanta Das

  2. National Polytechnic Institute, Mexico City, Mexico

    Genaro J. Martinez

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kari, J. (2022). Algorithms for Group Cellular Automata. In: Das, S., Martinez, G.J. (eds) Proceedings of First Asian Symposium on Cellular Automata Technology. ASCAT 2022. Advances in Intelligent Systems and Computing, vol 1425. Springer, Singapore. https://doi.org/10.1007/978-981-19-0542-1_2

Download citation

Publish with us

Policies and ethics

Search

Navigation