Geodesic
Dynamics groups of asynchronous cellular automata
Journal of Algebraic Combinatorics, Tome 33 (2011) no. 1, pp. 11-35.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: We say that a finite asynchronous cellular automaton (or more generally, any sequential dynamical system) is $\pi $-independent if its set of periodic points are independent of the order that the local functions are applied. In this case, the local functions permute the periodic points, and these permutations generate the dynamics group. We have previously shown that exactly 104 of the possible $2 ^{2 $^3$=256 2$^2^3=256 cellular automaton rules are $\pi $-independent. In the article, we classify the periodic states of these systems and describe their dynamics groups, which are quotients of Coxeter groups. The dynamics groups provide information about permissible dynamics as a function of update sequence and, as such, connect discrete dynamical systems, group theory, and algebraic combinatorics in a new and interesting way. We conclude with a discussion of numerous open problems and directions for future research.
Keywords: keywords sequential dynamical systems, cellular automata, update order, dynamics groups, Coxeter groups, periodic points, Fibonacci numbers, Lucas numbers 
@article{JAC_2011__33_1_a8,
     author = {Macauley, Matthew and McCammond, Jon and Mortveit, Henning S.},
     title = {Dynamics groups of asynchronous cellular automata},
     journal = {Journal of Algebraic Combinatorics},
     pages = {11--35},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2011__33_1_a8/}
}
TY  - JOUR
AU  - Macauley, Matthew
AU  - McCammond, Jon
AU  - Mortveit, Henning S.
TI  - Dynamics groups of asynchronous cellular automata
JO  - Journal of Algebraic Combinatorics
PY  - 2011
SP  - 11
EP  - 35
VL  - 33
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2011__33_1_a8/
LA  - en
ID  - JAC_2011__33_1_a8
ER  - 
%0 Journal Article
%A Macauley, Matthew
%A McCammond, Jon
%A Mortveit, Henning S.
%T Dynamics groups of asynchronous cellular automata
%J Journal of Algebraic Combinatorics
%D 2011
%P 11-35
%V 33
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2011__33_1_a8/
%G en
%F JAC_2011__33_1_a8
Macauley, Matthew; McCammond, Jon; Mortveit, Henning S. Dynamics groups of asynchronous cellular automata. Journal of Algebraic Combinatorics, Tome 33 (2011) no. 1, pp. 11-35. http://geodesic.mathdoc.fr/item/JAC_2011__33_1_a8/