# The Communication Hierarchy of Time and Space Bounded Parallel Machines

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 37, Issue: 2, page 159-176
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topPopély, Norbert. "The Communication Hierarchy of Time and Space Bounded Parallel Machines." RAIRO - Theoretical Informatics and Applications 37.2 (2010): 159-176. <http://eudml.org/doc/92720>.

@article{Popély2010,

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.
},

author = {Popély, Norbert},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Computational complexity; synchronized alternation.; communicating alternating machines; synchronized alternating machines},

language = {eng},

month = {3},

number = {2},

pages = {159-176},

publisher = {EDP Sciences},

title = {The Communication Hierarchy of Time and Space Bounded Parallel Machines},

url = {http://eudml.org/doc/92720},

volume = {37},

year = {2010},

}

TY - JOUR

AU - Popély, Norbert

TI - The Communication Hierarchy of Time and Space Bounded Parallel Machines

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 37

IS - 2

SP - 159

EP - 176

AB -
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.

LA - eng

KW - Computational complexity; synchronized alternation.; communicating alternating machines; synchronized alternating machines

UR - http://eudml.org/doc/92720

ER -

## References

top- A.K. Chandra, D.C. Kozen and L.J. Stockmeyer, Alternation. J. ACM28 (1981) 114-33. Zbl0473.68043
- V. Geffert, A communication hierarchy of parallel computations, Elsevier Science. Theoret. Comput. Sci.198 (1998) 99-130. Zbl0902.68074
- J. Hromkovic, J. Karhumäki, B. Rovan and A. Slobodová, On the power of synchronization in parallel computations. Discrete Appl. Math.32 (1991) 155-82. Zbl0734.68036
- A. Slobodová, Communication for alternating machines. Acta Inform.29 (1992) 425-41. Zbl0769.68022
- A. Slobodová, Some properties of space-bounded synchronized alternating Turing machines with universal states only. Theoret. Comput. Sci.96 (1992) 411-19. Zbl0754.68047
- 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. Zbl0689.68074

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.