A note on the XRAM and PRAM models. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1996

A note on the XRAM and PRAM models.

(1)
1

Résumé

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

Fichier principal
Vignette du fichier
RR1996-03.pdf (241.92 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102089 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102089 , version 1

Citer

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⟩
17 Consultations
18 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More