Paper Info
Title
Hardness Results for Coverability Problem of Well-Structured Pushdown Systems.
Abstract
Well-Structured Pushdown Systems (WSPDSs) are push-down systems extended with states and stack alphabet to be vectors, for modeling (restricted) recursive concurrent programs. It has been considered to be "very close to the border of undecidability". In this paper, we prove some hardness results for the coverability problem of WSPDSs. We show that for WSPDS with three dimensional vectors as states and WSPDS with three dimensional vectors as stack alphabet, the coverability problem becomes Ackermann-hard.
Year
DOI
Venue
2017
10.1007/978-3-319-53733-7_32
Lecture Notes in Computer Science
Keywords
Field
DocType
Automata and logic,Coverability,Lower bounds
Discrete mathematics,Combinatorics,Computer science,Recursion,Alphabet
Conference
Volume
ISSN
Citations 
10168
0302-9743
0
PageRank 
References 
Authors
0.34
5
2
Name
Order
Citations
PageRank
Chunmiao Li100.34
Xiaojuan Cai2365.95