This paper proves a gem of a theorem--one that provides an unexpectedly close connection between a class of formal languages and one type of architecture for parallel algorithms.

The architecture introduced in this paper is the concurrent read, owner write (CROW) machine, a restricted version of the concurrent read, exclusive write (CREW) machine, which is well known from the literature on parallel computation. The authors do a good job of motivating CROW machines, and it should be noted that several follow-on papers by numerous researchers studying CROW machines have appeared in the 14 years between the publication of the preliminary version of this paper in the ICALP conference proceedings and the appearance of this journal paper.

The paper’s key theorem states that the class of problems solvable in logarithmic time on a CROW machine is precisely the class of problems logspace-reducible to a deterministic context-free language. The latter class has been the subject of many research papers, and is known as  LOGDCFL.  As a corollary, new, stronger, and arguably simpler proofs are presented for most of the currently known upper bounds on the parallel complexity of deterministic context-free languages.