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.
Mots-clés : computational complexity, synchronized alternation
@article{ITA_2003__37_2_159_0, author = {Pop\'ely, Norbert}, title = {The communication hierarchy of time and space bounded parallel machines}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {159--176}, publisher = {EDP-Sciences}, volume = {37}, number = {2}, year = {2003}, doi = {10.1051/ita:2003012}, mrnumber = {2015690}, zbl = {1064.03027}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2003012/} }
TY - JOUR AU - Popély, Norbert TI - The communication hierarchy of time and space bounded parallel machines JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2003 SP - 159 EP - 176 VL - 37 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2003012/ DO - 10.1051/ita:2003012 LA - en ID - ITA_2003__37_2_159_0 ER -
%0 Journal Article %A Popély, Norbert %T The communication hierarchy of time and space bounded parallel machines %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2003 %P 159-176 %V 37 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2003012/ %R 10.1051/ita:2003012 %G en %F ITA_2003__37_2_159_0
Popély, Norbert. The communication hierarchy of time and space bounded parallel machines. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 2, pp. 159-176. doi : 10.1051/ita:2003012. http://archive.numdam.org/articles/10.1051/ita:2003012/
[1] Alternation. J. ACM 28 (1981) 114-33. | Zbl
, and ,[2] A communication hierarchy of parallel computations, Elsevier Science. Theoret. Comput. Sci. 198 (1998) 99-130. | Zbl
,[3] On the power of synchronization in parallel computations. Discrete Appl. Math. 32 (1991) 155-82. | Zbl
, , and ,[4] Communication for alternating machines. Acta Inform. 29 (1992) 425-41. | Zbl
,[5] Some properties of space-bounded synchronized alternating Turing machines with universal states only. Theoret. Comput. Sci. 96 (1992) 411-19. | Zbl
,[6] Machine models and simulations, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen. Elsevier Science (1989). | MR | Zbl
,[7] On the power of synchronization. J. Inf. Process. Cybern. (EIK) 25 (1989) 499-506. | Zbl
,Cité par Sources :