Document Type

Article

Publication Date

5-2010

Publication Title

Journal of Algebraic Combinatorics

Volume

33

Issue

1

Publisher

Springer Link

Abstract

We say that a finite asynchronous cellular automaton (or more generally, any sequential dynamical system) is π-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 223 = 256 cellular automaton rules are π-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.

Comments

This manuscript has been published in the Journal of Algebraic Combinatorics. Please find the published version here (note that a subscription is necessary to access this version):

https://link.springer.com/article/10.1007/s10801-010-0231-y

Springer holds the copyright in this article.

Download

Included in

Mathematics Commons

Share

COinS