A note on the XRAM and PRAM models.

Pierre Fraigniaud (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Cet article traite du modèle XRAM introduit dans [3] et de ses implications sur le modèle PRAM. Il rectifie en particulier la définition originelle du modèle XRAM pour rendre ce modèle robuste vis-à-vis de l'isomorphisme de graphe.

Mots clés: PRAM; complexity

Mots clés: complexité

Domaines: Informatique [cs]

Pierre Fraigniaud. A note on the XRAM and PRAM models.. [Research Report] LIP RR-1996-03, Laboratoire de l'informatique du parallélisme. 1996, 2+12p. ⟨hal-02102089⟩