Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-103 | 28th June 2010 12:12

Counting paths in VPA is complete for \#NC$^1$

RSS-Feed




TR10-103
Authors: Andreas Krebs, Nutan Limaye, Meena Mahajan
Publication: 28th June 2010 12:33
Downloads: 1085
Keywords: 


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 (BCGR: SICOMP 21(4), 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 automata.



ISSN 1433-8092 | Imprint