Nondeterministic, probabilistic and alternating computations on cellular array models

Abstract

A new mechanism for introducing nondeterminism on the cellular automaton model is introduced. It is shown that this form of nondeterminism corresponds to the traditional notion in the unbounded-time case, but there appear to be differences when real-time or linear-time cellular automata are considered. The notion is then generalised to include probabilistic and alternating computations. Restricted nondeterminism classes are also defined and studied, in an attempt to refine the power of nondeterminism.