Commutators of Bipermutive and Affine Cellular Automata



: Ville Salo, Ilkka Törmä

: Jarkko Kari, Martin Kutrib, Andreas Malcher

: Berlin

: 2013

: Lecture Notes in Computer Science

: Cellular Automata and Discrete Complex Systems: 19th International Workshop, AUTOMATA 2013, Gießen, Germany, September 14-19, 2013, Proceedings

: Lecture Notes in Computer Science

: 8155

: 155

: 170

: 978-3-642-40866-3

: 978-3-642-40867-0

: 0302-9743

DOI: https://doi.org/10.1007/978-3-642-40867-0_11

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


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 ane CA in their commutator. We show the last result also in the multidimensional case, proving a conjecture of [Moore-Boykett, 97].



Last updated on 2024-26-11 at 15:30