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

DOI10.1007/s00453-011-9501-xzbMath1282.68140MaRDI 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

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Cost Register Automata for Nested Words

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