Krebs, Andreas ; Limaye, Nutan ; Mahajan, Meena (2012) Counting Paths in VPA Is Complete for #NC 1 Algorithmica, 64 (2). pp. 279-294. ISSN 0178-4617
Full text not available from this repository.
Official URL: http://doi.org/10.1007/s00453-011-9501-x
Related URL: http://dx.doi.org/10.1007/s00453-011-9501-x
Abstract
We give a #NC1 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 #NC1 hard. Our results show that the difference between #BWBP and #NC1 is captured exactly by the addition of a visible stack to a nondeterministic finite-state automaton.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier B.V. |
| ID Code: | 128047 |
| Deposited On: | 14 Oct 2022 11:24 |
| Last Modified: | 14 Oct 2022 11:24 |
Repository Staff Only: item control page
