On Distinguishing NC $$^1$$ and NL
From MaRDI portal
Publication:3451114
DOI10.1007/978-3-319-21500-6_27zbMath1434.68181MaRDI QIDQ3451114
Andreas Krebs, Michael Ludwig, 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
68Q45: Formal languages and automata
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
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