BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-88-1240
       ENTRY:: April 24, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On Separat1ng the EREW and CREW PRAM Models
        TYPE:: Technical Report
      AUTHOR:: Gafni, E.
      AUTHOR:: Naor, J.
      AUTHOR:: Ragde, P.
        DATE:: December 1988
       PAGES:: 6
    ABSTRACT:: In [6], 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 Snir's lower bound applies.
       NOTES:: [Adminitrivia V1/Prg/19950424]
         END:: STAN//CS-TR-88-1240