BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/100
DTSTAMP:20230914T125910Z
SUMMARY:Counting paths in VPA is complete for #NC1
DESCRIPTION:Speaker: Andreas Krebs\nUniversitat Tubingen\nWilhelm-Schickard
 -Inst. fur Informatik\nArbeitsbereich Theoretische\nInforma\n\nAbstract: \
 nWe prove a $\\\\#$NC$^1$ upper bound for the problem of counting acceptin
 g paths in any fixed visibly pushdown automaton. Our algorithm involves a 
 non-trivial adaptation of the arithmetic formula evaluation algorithm of B
 uss\, 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.\n\nTo appear in proceedings of th
 e 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)\n
URL:https://www.tcs.tifr.res.in/web/events/100
DTSTART;VALUE=DATE:20100708
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR