A note on the XRAM and PRAM models
Pierre Fraigniaud, Centre National de la Recherche Scientifique (CNRS), 69 - Lyon (France). Lab. de l'Informatique du Parallelisme, Ecole Normale Superieure de Lyon, 69 (France). Lab. de l'Informatique du Parallelisme, Lyon-1 Univ., 69 (France). Lab. de l'Informatique du Parallelisme · 1996
In this paper, we deal with the XRAM model introduced in [3]. We mainly show that the original definition of the XRAM model was not consistent, and must be slightly modified. Therefore, we modify the definition of the XRAM model to make it consistent, and we study the consequence of this modification on the complexity theory developed in the XRAM model. The new model modifies, in particular, the definition of a problem on a XRAM, and thus on a PRAM and on a RAM since these two models are particular cases of the XRAM. However, we show that, though theoretically important, this modification has no practical consequence on the complexity theory developed on the XRAM model. Keywords: PRAM, complexity R'esum'e Cet article traite du mod`ele XRAM introduit dans [3] et de ses implications sur le mod`ele PRAM. Il rectifie en particulier la d'efinition originelle du mod`ele XRAM pour rendre ce mod`ele robuste vis-`a-vis de l'isomorphisme de graphe. Mots-cl'es: PRAM, complexit'e A n...