Header menu link for other important links
X
Nondeterministic, probabilistic and alternating computations on cellular array models
Kamala Krithivasan
Published in
1995
Volume: 143
   
Issue: 1
Pages: 23 - 49
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. © 1995.
About the journal
JournalTheoretical Computer Science
ISSN03043975
Open AccessYes
Concepts (10)
  •  related image
    ALTERNATING COMPUTATIONS
  •  related image
    CELLULAR ARRAY MODELS
  •  related image
    NONDETERMINISM
  •  related image
    Cellular arrays
  •  related image
    Computation theory
  •  related image
    Finite automata
  •  related image
    Mathematical models
  •  related image
    Probabilistic logics
  •  related image
    Real time systems
  •  related image
    AUTOMATA THEORY