The Communication Hierarchy of Time and Space Bounded Parallel Machines

Norbert Popély

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

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

How to cite

top

Popé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
  1. A.K. Chandra, D.C. Kozen and L.J. Stockmeyer, Alternation. J. ACM28 (1981) 114-33.  Zbl0473.68043
  2. V. Geffert, A communication hierarchy of parallel computations, Elsevier Science. Theoret. Comput. Sci.198 (1998) 99-130.  Zbl0902.68074
  3. 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
  4. A. Slobodová, Communication for alternating machines. Acta Inform.29 (1992) 425-41.  Zbl0769.68022
  5. A. Slobodová, Some properties of space-bounded synchronized alternating Turing machines with universal states only. Theoret. Comput. Sci.96 (1992) 411-19.  Zbl0754.68047
  6. P. van Emde Boas, Machine models and simulations, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen. Elsevier Science (1989).  
  7. J. Wiedermann, On the power of synchronization. (EIK)25 (1989) 499-506.  Zbl0689.68074

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.