A language L is accepted by a CROW-PRAM in O(log n) time (and implicitly with a polynomial number of processors) if and only if L is log-space reducible to a DCFL.
We use the DCFL characterization to demonstrate the stability of CROW-PRAM complexity classes under definitional changes.
The DCFL recognition algorithms of von Braunmuhl et al.
Section 4 introduces some definitions and notation needed in our DCFL recognition algorithm.
Since two dimensional arrays appear to play an important part in the DCFL simulation algorithm of Section 6, this suggests that quite different techniques would be needed to recognize DCFLs in time O(log n) on the PPM, if this is indeed possible.
k] defined above can be used for a time O(log n) parallel algorithm for DCFL recognition on a CROW-PRAM.
Every DCFL can be recognized by a CROW-PRAM satisfying restrictions R1-R3 in time O(log n) with O([n.
1994] gave a CREW-PRAM algorithm for DCFL recognition that, for any [Epsilon] [is greater than] 0, uses O(log n) time and [n.
1983], DCFL recognition is in simultaneous space S(n) and time O([n.
Any DCFL can be recognized by a log space DauxPDA with random access to its input tape, stack height bounded by O(S(n)), and time bounded by O([n.
show that DCFL recognition is possible in simultaneous space S(n) and time O([n.
The class LOGDCFL of languages log-space reducible to DCFLs was first defined and studied by Sudborough , who showed that it is equal to the class of languages recognizable in polynomial time by log-space bounded deterministic auxiliary pushdown automata (DauxPDAs), defined by Cook .