Visibly counter languages and the structure of NC^1

DOI10.1007/978-3-662-48054-0_32MaRDI QIDQ2946409zbMATHOpenAlexFDO

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)

• Refining the hierarchy of blind multicounter languages and twist-closed trios.
• Visibly counter languages and constant depth circuits
• Input-driven multi-counter automata
• scientific article; zbMATH DE number 5155118 (Why is no real title available?)
• On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)
• Dual VP classes
• The regular languages of wire linear \(\mathrm{AC}^0\)

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)