• 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. In: Jarkko Kari, Martin Kutrib, Andreas Malcher (Eds.), 19th International Workshop, AUTOMATA 2013, Gießen, Germany, September 17-19, 2013. Proceedings, Lecture Notes in Computer Science 8155, 139–154, Springer Berlin Heidelberg, 2013.

http://dx.doi.org/10.1007/978-3-642-40867-0_10

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.

BibTeX entry:

@INPROCEEDINGS{inpSaTx13c,
  title = {Color Blind Cellular Automata},
  booktitle = {19th International Workshop, AUTOMATA 2013, Gießen, Germany, September 17-19, 2013. Proceedings},
  author = {Salo, Ville and Törmä, Ilkka},
  volume = {8155},
  series = {Lecture Notes in Computer Science},
  editor = {Kari, Jarkko and Kutrib, Martin and Malcher, Andreas},
  publisher = {Springer Berlin Heidelberg},
  pages = {139–154},
  year = {2013},
  keywords = {cellular automata, commutation, symbol permutations, homomorphisms},
}

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

Publication Forum rating of this publication: level 1

Edit publication