Accession Number:

ADA324003

Title:

On Separating the EREW and CREW PRAM Models,

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Report Date:

1988-12-01

Pagination or Media Count:

7.0

Abstract:

Snir proposed the Selection Problem searching in a sorted table to show that the CREW PRAM is strictly more powerful than the EREW PRAM. This problem defines a partial function, that is, one that is defined only on a restricted Set of inputs. Recognizing whether an arbitrary input belongs to this restricted set is hard for both CREW and EREW PRAMs. The existence of a total function that exhibits the power of the CREW model over the EREW model was an open problem. Here we solve this problem by generalizing the selection problem to a Decision Tree problem which is defined on a full domain and to which Snirs lower bound applies.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE