🚀 go-pugleaf

Many thanks to those of you who responded with information concerning
EREW PRAMs and NC^1.

Thanks especially to Paul Beame, Joan Lucas, and Vijaya Ramachandran,
who pointed out that any language in DLOG (deterministic log space) can
be recognized by an EREW PRAM in log time.  Since NC^1 is contained in
DLOG, and many people suspect that the containment is proper, it seems
unlikely that NC^1 corresponds to log time on an EREW PRAM.
	(Sketch of the simulation: use the "Euler Tour" method.  The
	configuration graph of a DLOG machine yields two trees: one
	rooted at the ACCEPT state, and one rooted at the REJECT state.
	Assign two processors to each edge in this graph -- one processor
	for the "forward" direction, and one for the "backward" direction.
	The processors can easily compute their predecessors and successors
	in an Euler tour of their tree, starting at the root.  Now use
	pointer jumping to find which tree the start configuration is in.)

OPEN QUESTION: To whom can this be attributed?

Thanks also to Peter Clote and Ruediger Reischuk, for bringing to my attention
a paper by Klaus-Joern Lange in the upcoming Structure conference, in
which CREW-PRAM time is characterized in terms of "unambiguous" circuits.

- Eric Allender