On the parallel recognition of unambiguous context-free languages

AbstractWe present a simple parallel algorithm recognizing unambiguous context-free languages on a CREW PRAM in time log2 n with only n3 processors. This gives the smallest number of processors known for the recognition of unambiguous context-free languages in polylogarithmic time. Using the same framework a new algorithm is also given for the recognition of deterministic context-free languages in log2 n time with quadratic number of processors