🚀 go-pugleaf

Can anyone clarify the status of the following "folk theorem":

		NC^1 = log time on an EREW PRAM.

In particular
	* Is it correct?
	* If so, where is it proved?
	* Is this question discussed anywhere?


Note that this is NOT the definition of NC^1 (although one occasionally
sees a paper in which ANY log-time algorithm -- or at least log time
on an EREW PRAM -- is called an NC^1 algorithm).

Instead, NC^1 is usually defined in terms of (uniform) families of
log-depth fan-in 2 circuits of AND and OR gates, or in terms of Boolean
formulae, or in terms of alternating Turing machines, or in terms of
Bounded-Width Branching Programs, or in any of many other equivalent
formulations.

Note that various other models of PRAM are known to correspond exactly
to complexity classes.  For example:
	log time on a CRCW PRAM = AC^1		[Stockmeyer and Vishkin]
	log time on a CROW PRAM = log(DCFL)	[Dymond and Ruzzo]
(This last result requires some explanation.  CROW means "Concurrent
Read Owner Write"; the "owner write" restriction means that a processor
can only write into memory locations that it "owns".  Thus this gives
a policy for enforcing the "exclusive write" restriction.  The class
of sets reducible to determistic context-free languages is log(DCFL).)

It is easy to define something like an "Owner Read Owner Write" PRAM
that corresponds exactly to NC^1, but such a model seems quite restrictive.
Thus it would be nice if NC^1 really does correspond to EREW PRAMs.
Note that it is not a-priori obvious that a CROW PRAM can simulate an
EREW PRAM (although log(DCFL) clearly contains NC^1).

Any pointers will be appreciated,
-- Eric Allender