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, Ramachandran ([9]). 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 automata.
|
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-14031-0_7 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
pushdown automaton,non-trivial adaptation,arithmetic formula evaluation algorithm,nondeterministic finite-state automaton,finite state automata,upper bound | #SAT,Discrete mathematics,Combinatorics,Nondeterministic algorithm,Upper and lower bounds,Automaton,#P-complete,Ramachandran plot,Pushdown automaton,Mathematics | Journal |
Volume | ISSN | ISBN |
17 | 0302-9743 | 3-642-14030-0 |
Citations | PageRank | References |
1 | 0.37 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas Krebs | 1 | 3 | 4.15 |
| Nutan Limaye | 2 | 134 | 20.59 |
| Meena Mahajan | 3 | 688 | 56.90 |