On Distinguishing NC $$^1$$ and NL

DOI10.1007/978-3-319-21500-6_27zbMath1434.68181OpenAlexW2294826056MaRDI QIDQ3451114

Michael Ludwig, Andreas Krebs, Klaus-Joern 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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regular languages in \(NC\)
• The membership question for ETOL-languages is polynomially complete
• Dense Completeness
• Analytic Properties and Rescattering Correction to the Born Approximation for Transition Matrix Elements
• Parity, circuits, and the polynomial-time hierarchy
• Visibly pushdown languages
• Regularity Problems for Visibly Pushdown Languages

This page was built for publication: On Distinguishing NC $$^1$$ and NL