Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T05:21:57.160Z Has data issue: false hasContentIssue false

The Communication Hierarchyof Time and SpaceBounded Parallel Machines

Published online by Cambridge University Press:  15 November 2003

Norbert Popély*
Affiliation:
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia; popely@mail.com.
Get access

Abstract

We describe the communicating alternating machines and theirsimulation. We show that, in the case of communicating alternatingmachines which are bounded, simultaneously, by polynomial time andlogarithmic space, the use of three communication levels insteadof two does not increase computational power of communicatingalternating machines. This resolves an open problem [2]concerning the exact position of machines with three communicationlevels in the hierarchy.

Information

Type
Research Article
Copyright
© EDP Sciences, 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable