The Communication Hierarchy of Time and Space Bounded Parallel Machines
Department of Computer Science, P. J. Šafárik University,
Jesenná 5, 04154 Košice, Slovakia; firstname.lastname@example.org.
Accepted: August 2003
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  concerning the exact position of machines with three communication levels in the hierarchy.
Mathematics Subject Classification: 03D15
Key words: Computational complexity / synchronized alternation.
© EDP Sciences, 2003