Record Details

Counting Paths in VPA Is Complete for #NC

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Counting Paths in VPA Is Complete for #NC
 
Creator KREBS, A
LIMAYE, N
MAHAJAN, M
 
Subject LANGUAGES
DEPTH
 
Description 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 and Ramachandran (SIAM J. Comput. 21:755-780, 1992). 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 automaton.
 
Publisher SPRINGER
 
Date 2014-10-16T06:03:09Z
2014-10-16T06:03:09Z
2012
 
Type Article
 
Identifier ALGORITHMICA, 64(2)279-294
http://dx.doi.org/10.1007/s00453-011-9501-x
http://dspace.library.iitb.ac.in/jspui/handle/100/15406
 
Language en