Complex Systems

Upper Bound on the Number of Cycles in Border-Decisive Cellular Automata Download PDF

Puhua Guan
Department of Mathematics, University of Puerto Rico,
Rio Pedras, PR 00931, USA

Yu He
Center for Complex Systems Research and Department of Physics
University of Illinois,508 South Sixth Street,
Champaign, IL 61820, USA


The number of stable states of any one-dimensional -state border-decisive cellular automaton on a finite lattice with periodic boundary conditions is proved to be bounded by and the number of cycles of length is bounded by , where is the number of neighbors and is the Möbius function.