• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

A Characterization of Cellular Automata Generated by Idempotents on the Full Shift

Ville Salo, A Characterization of Cellular Automata Generated by Idempotents on the Full Shift. In: Edward Hirsch, Juhani Karhumäki, Arto Lepistö, Michail Prilutskii (Eds.), 7th International Computer Science Symposium in Russia, CSR 2012, 290–301, Springer, 2012.

Abstract:

In this article, we discuss the family of cellular automata generated by so-called idempotent cellular automata (CA G such that G^2 = G) on the full shift. We prove a characterization of products of idempotent CA, and show examples of CA which are not easy to directly decompose into a product of idempotents, but which are trivially seen to satisfy the conditions of the characterization. Our proof uses ideas similar to those used in the well-known Embedding Theorem and Lower Entropy Factor Theorem in symbolic dynamics. We also consider some natural decidability questions for the class of products of idempotent
CA.

BibTeX entry:

@INPROCEEDINGS{inpSalo_Ville12a,
  title = {A Characterization of Cellular Automata Generated by Idempotents on the Full Shift},
  booktitle = {7th International Computer Science Symposium in Russia, CSR 2012},
  author = {Salo, Ville},
  editor = {Hirsch, Edward and Karhumäki, Juhani and Lepistö, Arto and Prilutskii, Michail},
  publisher = {Springer},
  pages = {290–301},
  year = {2012},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication