English, Article edition: ON ASYNCHRONOUS CELLULAR AUTOMATA A. Ã…. HANSSON; H. S. MORTVEIT; C. M. REIDYS

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/134161
Physical Description
  • article
Language
  • English

Edition details

Title
  • ON ASYNCHRONOUS CELLULAR AUTOMATA
Author
  • A. Ã…. HANSSON
  • H. S. MORTVEIT
  • C. M. REIDYS
Physical Description
  • article
Notes
  • 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 {v1,â¦,vn} and where each vertex vi has a state xvi in a finite field K, (b) a sequence of functions (Fvi,Y)i, and (c) a word w =​ (w1,â¦,wk), where each wi is a vertex in Y. The function Fvi,Y updates the state of vertex vi as a function of the state of vi and its Y-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 on n vertices (Y =​ Circn), and all the maps Fvi 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 =​ Circ4. Finally, we analyze invertible ACA and offer an interpretation of S35 as the group of an SDS over the three-dimensional cube with local functions induced by nor3 + nand3.
  • Sequential dynamical system, asynchronous cellular automaton, periodic point, phase space, update schedule invariance, invertibility
  • RePEc:wsi:acsxxx:v:08:y:2005:i:04:p:521-538
Language
  • English
Contributed by
OAIster

Get this edition

  • Set up My libraries

    How do I set up "My libraries"?

    In order to set up a list of libraries that you have access to, you must first login or sign up. Then set up a personal list of libraries from your profile page by clicking on your user name at the top right of any screen.

  • All (1)
  • Unknown (1)
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment