On distinguishing NC^1 and NL

DOI10.1007/978-3-319-21500-6_27MaRDI QIDQ3451114zbMATH OpenOpenAlexFDO

Authors A. Krebs, Michael Ludwig, Klaus-Jörn Lange

Publication date 10 November 2015

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-21500-6_27

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Dense completeness
• Visibly counter languages and the structure of \(\mathrm {NC}^{1}\)
• Some classes of languages in \(NC^ 1\)
• scientific article; zbMATH DE number 4080911
• Equivalence of deterministic one-counter automata is NL-complete

Cites work

• Analytic Properties and Rescattering Correction to the Born Approximation for Transition Matrix Elements
• Dense completeness
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 512990 (Why is no real title available?)
• Parity, circuits, and the polynomial-time hierarchy
• Regular languages in \(NC\)
• Regularity Problems for Visibly Pushdown Languages
• The membership question for ETOL-languages is polynomially complete
• Visibly counter languages and constant depth circuits
• Visibly pushdown languages

Cited in

(4)

• Visibly counter languages and the structure of \(\mathrm {NC}^{1}\)
• Visibly counter languages and constant depth circuits
• Dense completeness
• Equivalence of deterministic one-counter automata is NL-complete

This page was built for publication: On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3451114)