Paper Info
Title
Complexity analysis of the backward coverability algorithm for VASS
Abstract
By using the known lower and upper complexity bounds of the coverability problem for VASS, we characterize the complexity of the classical backward algorithm for VASS coverability, and provide optimal bounds on the size of the symbolic representation it computes.
Year
DOI
Venue
2011
10.1007/978-3-642-24288-5_10
RP
Keywords
Field
DocType
symbolic representation,complexity analysis,optimal bound,upper complexity bound,coverability algorithm,coverability problem,vass coverability
Forward algorithm,Algorithm,Maximal element,Membership problem,Mathematics
Conference
Volume
ISSN
Citations 
6945
0302-9743
14
PageRank 
References 
Authors
0.60
13
2
Name
Order
Citations
PageRank
Laura Bozzelli118326.47
Pierre Ganty224220.29