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

Color Blind Cellular Automata

Ville Salo, Ilkka Törmä, Color Blind Cellular Automata. Journal of Cellular Automata 9(5-6), 477–509, 2014.

Abstract:

We introduce the classes of color blind and typhlotic cellular automata, that is, cellular automata that commute with all symbol permutations and all symbol mappings, respectively. We show that color blind cellular automata form a relatively large subclass of all cellular automata which contains an intrinsically universal automaton. On the other hand, we give simple characterizations for the color blind CA which are also group homomorphisms, and for general typhlotic CA, showing that both must be trivial in most cases. Using an extension lemma for a generalization of color blind CA, we show that the centralizer of a finite equicontinuous family of CA always contains an intrinsically universal automaton, as does that of an almost equicontinuous family with a blocking word of certain special type.

BibTeX entry:

@ARTICLE{jSaTx14b,
  title = {Color Blind Cellular Automata},
  author = {Salo, Ville and Törmä, Ilkka},
  journal = {Journal of Cellular Automata},
  volume = {9},
  number = {5-6},
  publisher = {Old City Publishing},
  pages = {477–509},
  year = {2014},
  keywords = {cellular automaton, commutation, symbol permutation, homomorphism, intrinsic universality, equicontinuity},
  ISSN = {1557-5969},
}

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

Publication Forum rating of this publication: level 1

Edit publication