Counting paths in VPA is complete for \#NC^1
DOI10.1007/S00453-011-9501-XzbMATH Open1282.68140OpenAlexW2027925033MaRDI QIDQ1759656FDOQ1759656
Authors: A. Krebs, Nutan Limaye, Meena Mahajan 
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
Recommendations
- Counting paths in VPA is complete for \#NC\(^{1}\)
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
- Arithmetizing Classes Around NC 1 and L
- On the complexity of membership and counting in height-deterministic pushdown automata
- On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Nondeterministic \(NC^1\) computation
- Visibly pushdown languages
- Computing Algebraic Formulas Using a Constant Number of Registers
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Title not available (Why is that?)
- An Optimal Parallel Algorithm for Formula Evaluation
- The Parallel Evaluation of General Arithmetic Expressions
- Arithmetizing Classes Around NC 1 and L
- Division in logspace-uniform NC
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
- Title not available (Why is that?)
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
Cited In (3)
This page was built for publication: Counting paths in VPA is complete for \(\#\mathrm{NC}^1\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759656)
