Visibly counter languages and the structure of NC^1
DOI10.1007/978-3-662-48054-0_32zbMATH Open1465.68078OpenAlexW2406079147MaRDI QIDQ2946409FDOQ2946409
Authors: Michael Hahn, A. Krebs, Michael Ludwig, Klaus-Jörn 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
Recommendations
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)
Cites Work
- Visibly pushdown languages
- Parity, circuits, and the polynomial-time hierarchy
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Title not available (Why is that?)
- Regular languages in \(NC\)
- Title not available (Why is that?)
- Finite monoids and the fine structure of NC 1
- Title not available (Why is that?)
- Regularity Problems for Visibly Pushdown Languages
- Extensional Uniformity for Boolean Circuits
- Visibly counter languages and constant depth circuits
Cited In (7)
- Visibly counter languages and constant depth circuits
- Refining the hierarchy of blind multicounter languages and twist-closed trios.
- The regular languages of wire linear \(\mathrm{AC}^0\)
- On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)
- Dual VP classes
- Input-driven multi-counter automata
- Title not available (Why is that?)
This page was built for publication: Visibly counter languages and the structure of \(\mathrm {NC}^{1}\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946409)
