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
Michael Ludwig, Andreas Krebs, Michael Hahn, Klaus-Joern Lange
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
Related Items
Input-driven multi-counter automata, The regular languages of wire linear \(\mathrm{AC}^0\), Dual VP classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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