Some subclasses of context-free languages in \(NC^ 1\)

DOI10.1016/0020-0190(88)90047-6zbMath0659.68073OpenAlexW2039393392MaRDI QIDQ1112610

Tao Jiang, Oscar H. Ibarra, Bala Ravikumar

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90047-6

zbMATH Keywords

parallel algorithmparallel computing modelparallel computationscomplexity classesalternating Turing machineDyck languagescontext- free languages

Mathematics Subject Classification ID

Related Items (13)

On the closure properties of linear conjunctive languages. ⋮ On the Transformation of LL(k)-linear Grammars to LL(1)-linear ⋮ On the relative complexity of some languages in \(NC^ 1\) ⋮ Streaming algorithms for language recognition problems ⋮ On linear languages recognized by deterministic biautomata ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On the transformation of LL\((k)\)-linear to LL(1)-linear grammars ⋮ On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata ⋮ Extensional Uniformity for Boolean Circuits ⋮ Unambiguity of circuits ⋮ First-order logics: some characterizations and closure properties ⋮ Some classes of languages in \(NC^ 1\) ⋮ Circuits and expressions with nonassociative gates

Cites Work

• Unnamed Item
• Unnamed Item
• On uniform circuit complexity
• A taxonomy of problems with fast parallel algorithms
• Alternation
• Bounds to Complexities of Networks for Sorting and for Switching
• Word Problems Solvable in Logspace
• The Hardest Context-Free Language
• Language recognition by marking automata

This page was built for publication: Some subclasses of context-free languages in \(NC^ 1\)