Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-26T09:13:55.856Z Has data issue: false hasContentIssue false
  • English
  • Français

The Communication Hierarchy of Time and SpaceBounded Parallel Machines

Published online by Cambridge University Press:  15 November 2003

Norbert Popély
Norbert Popély*
Affiliation:
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia; [email protected].
Get access

Abstract

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.

Keywords

Computational complexitysynchronized alternation.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 37 , Issue 2 , April 2003 , pp. 159 - 176
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.)

References

Chandra, A.K., Kozen, D.C. and Stockmeyer, L.J., Alternation. J. ACM 28 (1981) 114-33. CrossRef
Geffert, V., A communication hierarchy of parallel computations, Elsevier Science. Theoret. Comput. Sci. 198 (1998) 99-130. CrossRef
Hromkovic, J., Karhumäki, J., Rovan, B. and Slobodová, A., On the power of synchronization in parallel computations. Discrete Appl. Math. 32 (1991) 155-82. CrossRef
Slobodová, A., Communication for alternating machines. Acta Inform. 29 (1992) 425-41. CrossRef
Slobodová, A., Some properties of space-bounded synchronized alternating Turing machines with universal states only. Theoret. Comput. Sci. 96 (1992) 411-19. CrossRef
P. van Emde Boas, Machine models and simulations, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen. Elsevier Science (1989).
J. Wiedermann, On the power of synchronization. (EIK) 25 (1989) 499-506.