We identify and study a natural and frequently occurring subclass of Concurrent-Read, Exclusive-Write Parallel Random Access Machines (CREW-PRAMs). Called Concurrent-Read, Owner-Write, or CROW-PRAMs, these are machines in which each global memory location is assigned a unique ``owner'' processor, which is the only processor allowed to write into it. Considering the difficulties that would be involved in physically realizing a full CREW-PRAM model, it is interesting to observe that in fact, most known CREW-PRAM algorithms satisfy the CROW restriction or can be easily modified to do so.

This paper makes three main contributions. First, we formally define the CROW-PRAM model and demonstrate its stability under several definitional changes.

Second, we precisely characterize the power of the CROW-PRAM by showing that the class of languages recognizable by it in time $O(\log n)$ is exactly the class LOGDCFL of languages log space reducible to deterministic context free languages.

Third, using the same basic machinery, we show that the recognition problem for deterministic context-free languages can be solved in time order of (n to the power1+ epsilon) over S(n) for any epsilon > 0 and any S(n) satisfying square of log n < =S(n) <=n on a deterministic auxiliary pushdown automaton having a log n space work tape, pushdown store of maximum height S(n), and random access to its input tape. These results extend and unify work of von Braunmuhl, Cook, Mehlhorn, and Verbeek; Klein and Reif; and Rytter.

Download paper in PDF format.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.