Advances in Complex Systems · 2005 · 19 citations · 5 references
Natural SciencesComputer ScienceMathematicsCombinatoricsComplex SystemsDynamical SystemsAutomata TheoryBoolean AlgebraCellular AutomataFinite AutomataFinite-state MachinesGraph TheoryAsynchronous Cellular AutomataBoolean Function RepresentationBoolean FunctionsDynamical Systems ModelingPeriodic PointsSymmetric Functions
We study asynchronous cellular automata (ACA) induced by symmetric Boolean functions [1]. These systems can be considered as sequential dynamical systems (SDS) over words, a class of dynamical systems that consists of (a) a finite, labeled graph Y with vertex set {v 1 ,…,v n } and where each vertex v i has a state x v i in a finite field K, (b) a sequence of functions (F v i ,Y ) i , and (c) a word w = (w 1 ,…,w k ), where each w i is a vertex in Y. The function F v i ,Y updates the state of vertex v i as a function of the state of v i and its Y-neighbors and maps all other vertex states identically. The SDS is the composed map [Formula: see text]. In the particular case of ACA, the graph is the circle graph on n vertices (Y = Circ n ), and all the maps F v i are induced by a common Boolean function. Our main result is the identification of all w-independent ACA, that is, all ACA with periodic points that are independent of the word (update schedule) w. In general, for each w-independent SDS, there is a finite group whose structure contains information about for example SDS with specific phase space properties. We classify and enumerate the set of periodic points for all w-independent ACA, and we also compute their associated groups in the case of Y = Circ 4 . Finally, we analyze invertible ACA and offer an interpretation of S 35 as the group of an SDS over the three-dimensional cube with local functions induced by nor 3 + nand 3 .
5
Discrete, sequential dynamical systems
Henning Mortveit, Christian M. Reidys · Discrete Mathematics · 2001 · 96 citations
Sequential Dynamical Systems Over Words
Christian M. Reidys · Annals of Combinatorics · 2006 · 23 citations