Some subclasses of context-free languages in \(NC^ 1\) (Q1112610): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0190(88)90047-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2039393392 / rank | |||
Normal rank |
Revision as of 22:50, 19 March 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