The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.
We describe the communicating alternating machines and their
simulation. We show that, in the case of communicating alternating
machines which are bounded, simultaneously, by polynomial time and
logarithmic space, the use of three communication levels instead
of two does not increase computational power of communicating
alternating machines. This resolves an open problem [2]
concerning the exact position of machines with three communication
levels in the hierarchy.
Schöning [14] introduced a notion of helping and suggested the study of the class of the languages that can be helped by oracles in a given class . Later, Ko [12], in order to study the connections between helping and “witness searching”, introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call which contains all the self-helping classes. We introduce the Helping hierarchy whose levels are...
Schöning [14] introduced a notion of helping and suggested
the study of the class of the languages that can be helped
by oracles in a given class . Later, Ko [12], in order to
study the connections between helping and "witness searching" ,
introduced the notion of self-helping for languages.
We extend this notion to classes of languages and show that there exists
a self-helping class that we call SH which contains all the
self-helping classes.
We introduce the Helping hierarchy whose
levels...
We
construct, for each integer n,
three functions from {0,1}n to {0,1} such that any boolean mapping from
{0,1}n to {0,1}n can be computed with a finite sequence of assignations
only using the n input variables and those three functions.
Currently displaying 1 –
11 of
11