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

Commutators of Bipermutive and Affine Cellular Automata

Ville Salo, Ilkka Törmä, Commutators of Bipermutive and Affine 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, 155–170, Springer Berlin Heidelberg, 2013.

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

Abstract:

We discuss bipermutive cellular automata from a combinatorial and topological perspective. We prove a type of topological randomizing property for bipermutive CA, show that the commutator of a bipermutive CA is always small and that bipermutive affine CA have only affine CA in their commutator. We show the last result also in the multidimensional case, proving a conjecture of [Moore-Boykett, 97].

BibTeX entry:

@INPROCEEDINGS{inpSaTx13b,
  title = {Commutators of Bipermutive and Affine 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 = {155–170},
  year = {2013},
  keywords = {cellular automata, bipermutivity, commutation, affine cellular automata},
}

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

Publication Forum rating of this publication: level 1

Edit publication