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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• Visibly counter languages and constant depth circuits
• On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)
• Some classes of languages in \(NC^ 1\)
• On the relative complexity of some languages in \(NC^ 1\)
• Regular languages in \(NC\)

Cites Work

• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Extensional Uniformity for Boolean Circuits
• Finite monoids and the fine structure of NC ¹
• Parity, circuits, and the polynomial-time hierarchy
• Regular languages in \(NC\)
• Regularity Problems for Visibly Pushdown Languages
• Visibly counter languages and constant depth circuits
• Visibly pushdown languages

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 no real title available?)

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)