Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ita:2003012
Classification : 03D15
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :