Upper Bound on the Number of Cycles in Border-Decisive Cellular Automata
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
Abstract
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.
