Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$
From MaRDI portal
Publication:2946409
DOI10.1007/978-3-662-48054-0_32zbMath1465.68078MaRDI QIDQ2946409
Andreas Krebs, Michael Ludwig, Klaus-Joern Lange, Michael Hahn
Publication date: 16 September 2015
Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_32
68Q45: Formal languages and automata
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q06: Networks and circuits as models of computation; circuit complexity
Cites Work
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Regular languages in \(NC\)
- Parity, circuits, and the polynomial-time hierarchy
- Visibly pushdown languages
- Finite monoids and the fine structure of NC 1
- Extensional Uniformity for Boolean Circuits
- Regularity Problems for Visibly Pushdown Languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item