Some subclasses of context-free languages in \(NC^ 1\) (Q1112610): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Alternation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A taxonomy of problems with fast parallel algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Hardest Context-Free Language / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198075 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Word Problems Solvable in Logspace / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bounds to Complexities of Networks for Sorting and for Switching / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3692896 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On uniform circuit complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Language recognition by marking automata / rank | |||
Normal rank |
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