School of Technology and Computer Science Seminars
Counting paths in VPA is complete for #NC1
by Dr. Andreas Krebs (University of Tubingen, Germany)
Thursday, July 8, 2010
from
to
(Asia/Kolkata)
at Colaba Campus ( A-212 )
at Colaba Campus ( A-212 )
Description |
We prove 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. 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. To appear in proceedings of the 16th International Computing and Combinatorics Conference COCOON, 19-21 July, 2010, Vietnam. (Andreas Krebs (University of Tubingen, Germany), Nutan Limaye (TIFR, Mumbai), Meena Mahajan (Institute of mathematical sciences, Chennai) |
Organised by | John Barretto |