Tata Institute of Fundamental Research
Counting paths in VPA is complete for #NC1
Seminar
Speaker:
Andreas Krebs
Universitat Tubingen
Wilhelm-Schickard-Inst. fur Informatik
Arbeitsbereich Theoretische
Informa
Date:
Thursday, 8 Jul 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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)
| Speaker: | Andreas Krebs Universitat Tubingen Wilhelm-Schickard-Inst. fur Informatik Arbeitsbereich Theoretische Informa |
| Date: | Thursday, 8 Jul 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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)
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)