A Study on Homo-Asynchronous Cellular Automata

Abstract

This work studies a new type of asynchronism, called homo-asynchronism, on cellular automata. A configuration of a one-dimensional cellular automaton can be decomposed into a number of homogeneous components. Homo-asynchronous refers to asynchronous update of the homogeneous components to evolve the automaton. In this study, we assume that exactly one homogeneous component is chosen uniformly and randomly for the update at each step. To identify the constituent homogeneous components of a configuration, this work introduces the normal forms of the configurations. Finally, the work reports a preliminary study on the convergence of homo-asynchronous cellular automata to fixed points.