Mikhail Vyalyi
 
Models of a nondeterministic computation by automata
 
Abstract: 
A nondeterminism can be introduced in two different ways. The
standard way is to change a transition function of an automaton by a
transition relation. In a nondeterministic state a computation
branches into several computation paths. The computation is successful
iff it is successful on some computation path.
 
The second way is to supply an automaton by an access to additional
data (a guess). An automaton performs a deterministic computation
using an input and a guess. The computation is successful iff it is
successful on some guess. To complete the definition one should choose
a memory model for a guess and should specify a form of a guess. Thus
we obtain in this way a variety of computational models. 
 
In the talk we present examples of generalized nondeterministic models
defined in this way for 2-way multi-head automata. Using these models
it is possible to characterize various computational resources for the
standard model of Turing machine. The standard complexity classes of
deterministic and nondeterministic logarithmic space, deterministic
and nondeterministic polynomial time and polynomial space will be
described in terms of generalized nondeterministic computation by
automata.