Counting paths in VPA is complete for \#NC^1
From MaRDI portal
Publication:1759656
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
Cites work
- scientific article; zbMATH DE number 3696500 (Why is no real title available?)
- scientific article; zbMATH DE number 1161568 (Why is no real title available?)
- An Optimal Parallel Algorithm for Formula Evaluation
- Arithmetizing Classes Around NC 1 and L
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Computing Algebraic Formulas Using a Constant Number of Registers
- Division in logspace-uniform NC
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Nondeterministic \(NC^1\) computation
- On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
- The Parallel Evaluation of General Arithmetic Expressions
- Visibly pushdown languages
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)
