@article{Krebs:2012tv,
    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.},
    Author = {Krebs, Andreas and Limaye, Nutan and Mahajan, Meena},
    Date = {2012/10/01},
    File = {Counting Paths in VPA Is Complete for \#NC1 - s00453-011-9501-x - v.pdf},
    ISBN = {1432-0541},
    Journal = {Algorithmica},
    Number = {2},
    Pages = {279--294},
    Title = {{Counting Paths in VPA Is Complete for \#NC1}},
    URL = {https://doi.org/10.1007/s00453-011-9501-x},
    Volume = {64},
    Year = {2012},
    bdsk-url-1 = {https://doi.org/10.1007/s00453-011-9501-x},
    date-added = {2022-04-04 07:33:10 +0200},
    date-modified = {2022-04-04 07:33:10 +0200},
    id = {Krebs2012},
    doi = {10.1007/s00453-011-9501-x}
}

@article{Krebs:2012tv, 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.}, Author = {Krebs, Andreas and Limaye, Nutan and Mahajan, Meena}, Date = {2012/10/01}, File = {Counting Paths in VPA Is Complete for #NC1 - s00453-011-9501-x - v.pdf}, ISBN = {1432-0541}, Journal = {Algorithmica}, Number = {2}, Pages = {279--294}, Title = {{Counting Paths in VPA Is Complete for #NC1}}, URL = {https://doi.org/10.1007/s00453-011-9501-x}, Volume = {64}, Year = {2012}, bdsk-url-1 = {https://doi.org/10.1007/s00453-011-9501-x}, date-added = {2022-04-04 07:33:10 +0200}, date-modified = {2022-04-04 07:33:10 +0200}, id = {Krebs2012}, doi = {10.1007/s00453-011-9501-x} }