NONDETERMINISTIC, PROBABILISTIC AND ALTERNATING COMPUTATIONS ON CELLULAR ARRAY MODELS

A new mechanism for introducing nondeterminism on the cellular automat on model is introduced. It is shown that this form of nondeterminism c orresponds to the traditional notion in the unbounded-time case, but t here appear to be differences when real-time or linear-time cellular a utomata are considered. The notion is then generalised to include prob abilistic and alternating computations. Restricted nondeterminism clas ses are also defined and studied, in an attempt to refine the power of nondeterminism.