A parallel random access machine (P-RAM) is a collection of synchronous deterministic RAMs that share memory locations in the following way. At each step, more than one processor can read a given memory location, but no two distinct processors can write to the same location. The W-RAM model extends this idea by allowing more than one processor to write to a given location if all such processors attempt to write the same value. As a simple example, a W-RAM with n processors can compute the Boolean or or n variables in a single step by having each processor store true if its corresponding variable is true. If it is known that no more than one variable is true at a given time, then a P-RAM can be used to evaluate the function.

The paper starts with an algorithm for determining in O(log n) time on a W-RAM if a given context-free grammar G generates a word w. If a particular node (which corresponds to having the start symbol of the grammar derive the entire string of terminals) in a graph constructed from G and w is marked by the algorithm, then the string w is generated by G. The original algorithm may have write conflicts (i.e., attempts by two or more processors to simultaneously store the same value in a given memory location). These can be eliminated because the grammar G is unambiguous; having two or more processors write to a given location would imply two or more distinct derivations for w. Therefore, the algorithm provides an O(log n) recognition method for unambiguous context-free languages (CFLs) on a P-RAM. This extends and simplifies an earlier result that showed that a P-RAM could recognize a deterministic CFL in O(log n) time. It is still not known if this result can be extended to the entire class of CFLs.

The author’s native language is not English, and the paper has a number of misspellings and awkward phrases. However, the author does present a number of examples, and the paper is reasonably easy to follow.