Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VISIBLY PUSHDOWN AUTOMATA:
Reports tagged with visibly pushdown automata:
TR10-103 | 28th June 2010
Andreas Krebs, Nutan Limaye, Meena Mahajan

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

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 ... more >>>




ISSN 1433-8092 | Imprint