Some subclasses of context-free languages in \(NC^ 1\) (Q1112610): Difference between revisions
From MaRDI portal
Latest revision as of 11:12, 19 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some subclasses of context-free languages in \(NC^ 1\) |
scientific article |
Statements
Some subclasses of context-free languages in \(NC^ 1\) (English)
0 references
1988
0 references
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\).
0 references
parallel computations
0 references
complexity classes
0 references
parallel algorithm
0 references
context- free languages
0 references
alternating Turing machine
0 references
parallel computing model
0 references
Dyck languages
0 references