THE COMMUNICATION HIERARCHY OF TIME AND SPACE BOUNDED PARALLEL MACHINES

摘要

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.