Separating the Power of EREW and CREW PRAMs with Small Communication Width

P. Beame, 1986, Lower Bounds in Parallel Machine Computation, Department of Computer Science, University of Toronto Cook, 1986, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM J. Comput., 15, 87, 10.1137/0215006 M. Dietzfelbinger, M. Kutyłowski, R. Reischuk, 1990, Exact time bounds for computing Boolean functions on PRAMs without simultaneous writes, Proceedings of the 1990 ACM Symposium on Parallel Algorithms and Architectures, Crete, 125, 135 Dymond, 1986, Parallel random access machines with owned global memory and deterministic context-free language recognition, Lecture Notes in Computer Science, 226, 95, 10.1007/3-540-16761-7_59 Fich, 1993, The complexity of computation on the parallel random access machine, 843 Fich, 1990, Towards understanding exclusive read, SIAM J. Comput., 19, 717, 10.1137/0219050 Gafni, 1989, On separating the EREW and CREW PRAM models, Theoret. Comput. Sci., 68, 343, 10.1016/0304-3975(89)90169-2 JáJá, 1992 Kutyłowski, 1991, The complexity of Boolean functions on CREW PRAMs, SIAM J. Comput., 20, 824, 10.1137/0220051 Nisan, 1991, CREW PRAMs and decision trees, SIAM J. Comput., 20, 999, 10.1137/0220062 Snir, 1985, On parallel searching, SIAM J. Comput., 14, 688, 10.1137/0214051 Vishkin, 1985, Trade-offs between depth and width in parallel computation, SIAM J. Comput., 14, 303, 10.1137/0214024