Name
Abstract | ||
|---|---|---|
We give a #NC 1 upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta and Ramachandran (SIAM J. Comput. 21:755–780, 1992). We also show that the problem is #NC 1 hard. Our results show that the difference between #BWBP and #NC 1 is captured exactly by the addition of a visible stack to a nondeterministic finite-state automaton. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00453-011-9501-x | Algorithmica |
Keywords | Field | DocType |
pushdown automaton,non-trivial adaptation,siam j. comput,arithmetic formula evaluation algorithm,nondeterministic finite-state automaton | Discrete mathematics,Combinatorics,Boolean circuit,Nondeterministic algorithm,Upper and lower bounds,Automaton,#P-complete,Pushdown automaton,Ramachandran plot,Mathematics | Journal |
Volume | Issue | ISSN |
64 | 2 | 0178-4617 |
Citations | PageRank | References |
1 | 0.37 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas Krebs | 1 | 3 | 4.15 |
| Nutan Limaye | 2 | 134 | 20.59 |
| Meena Mahajan | 3 | 688 | 56.90 |