Some subclasses of context-free languages in \(NC^ 1\) (Q1112610): Difference between revisions

One way to show that a problem can be efficiently computed in parallel is to find a parallel algorithm working with a polynomial number of processors in logarithmic time, i.e., to prove that the problem is in \(NC^ 1\) [\textit{N. Pippenger}, On simultaneous resource bounds, 20th IEEE Symp. Fundam. Comput. Sci., 307-310 (1979)]. It was shown by \textit{W. Ruzzo} [J. Comput. Syst. Sci. 22, 365-383 (1981; Zbl 0462.68013)] that context-free languages (cfl's) are in \(NC^ 2\). Since one conjectures that cfl's do not belong to \(NC^ 1\) (if they belong to \(NC^ 1\) then \(DLOGSPACE=NLOGSPACE)\) the authors try to find some subclasses of cfl's which are in \(NC^ 1\). Using alternating Turing machine as a parallel computing model it is shown that the one-sided Dyck languages, structured cfl's, bracketed cfl's, and deterministic linear cfl's are in \(NC^ 1\).