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.
We show that one-way Π-alternating Turing machines cannot
accept unary nonregular languages in (log ) space. This holds
for an mode of space complexity measure, defined as
the worst cost of any accepting computation. This lower bound
should be compared with the corresponding bound for one-way
Σ-alternating machines, that are able to accept unary
nonregular languages in space (log log ). Thus, Σ-alternation is more powerful than Π-alternation
for space bounded one-way machines with unary inputs.
...
Download Results (CSV)