Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$

DOI10.1007/978-3-662-48054-0_32zbMath1465.68078OpenAlexW2406079147MaRDI 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

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)

Related Items (3)

The regular languages of wire linear \(\mathrm{AC}^0\) ⋮ Dual VP classes ⋮ Input-driven multi-counter automata

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 ¹
• Extensional Uniformity for Boolean Circuits
• Regularity Problems for Visibly Pushdown Languages

This page was built for publication: Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$