ON ASYNCHRONOUS CELLULAR AUTOMATA

A. Å. Hansson (), H. S. Mortveit () and C. M. Reidys ()
Additional contact information
A. Å. Hansson: Los Alamos National Laboratory, CCS-DSS, 87545 New Mexico, USA
H. S. Mortveit: VBI/Department of Mathematics, Virgina Polytechnic Institute and State University, Blacksburg, VA 24061, USA
C. M. Reidys: Los Alamos National Laboratory, CCS-DSS, 87545 New Mexico, USA

Advances in Complex Systems (ACS), 2005, vol. 08, issue 04, 521-538

Abstract: 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 graphYwith vertex set{v1,…,vn}and where each vertexvihas a statexviin a finite fieldK, (b) a sequence of functions(Fvi,Y)i, and (c) a wordw = (w1,…,wk), where eachwiis a vertex inY. The functionFvi,Yupdates the state of vertexvias a function of the state ofviand itsY-neighbors and maps all other vertex states identically. The SDS is the composed map$[\mathfrak{F}_Y,w]=\prod_{i=1}^{k} F_{w_{i}}: K^n\rightarrow K^n$. In the particular case of ACA, the graph is the circle graph onnvertices(Y =Circn), and all the mapsFviare induced by a common Boolean function. Our main result is the identification of allw-independent ACA, that is, all ACA with periodic points that are independent of the word (update schedule)w. In general, for eachw-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 allw-independent ACA, and we also compute their associated groups in the case ofY =Circ4. Finally, we analyze invertible ACA and offer an interpretation of S35as the group of an SDS over the three-dimensional cube with local functions induced by nor3+ nand3.

Keywords: Sequential dynamical system; asynchronous cellular automaton; periodic point; phase space; update schedule invariance; invertibility (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219525905000555
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:acsxxx:v:08:y:2005:i:04:n:s0219525905000555

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219525905000555

Access Statistics for this article

Advances in Complex Systems (ACS) is currently edited by Frank Schweitzer

More articles in Advances in Complex Systems (ACS) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().