Some algorithms for real-time generation of non-regular sequences on one-bit inter-cell-communication cellular automata

摘要

A model of cellular automata (CA) is considered to be a non-linear model of complex systems in which an infinite one-dimensional array of finite state machines (cells) updates itself in a synchronous manner according to a uniform local rule. We study a sequence generation problem on a special restricted class of cellular automata having 1-bit inter-cell communications (CA1-bit) and propose several state-efficient real-time sequence generation algorithms for non-regular sequences. The 1-bit CA can be thought to be one of the most powerless and simplest models in a variety of CAs.