Counting paths in VPA is complete for \(\#\mathrm{NC}^1\)

DOI10.1007/s00453-011-9501-xzbMath1282.68140OpenAlexW2027925033MaRDI QIDQ1759656

Andreas Krebs, Meena Mahajan, Nutan Limaye

Publication date: 21 November 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9501-x

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Cost Register Automata for Nested Words ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Nondeterministic \(NC^1\) computation
• Division in logspace-uniformNC¹
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• Visibly pushdown languages
• Arithmetizing Classes Around NC 1 and L
• Computing Algebraic Formulas Using a Constant Number of Registers
• An Optimal Parallel Algorithm for Formula Evaluation
• The Parallel Evaluation of General Arithmetic Expressions

This page was built for publication: Counting paths in VPA is complete for \(\#\mathrm{NC}^1\)