Hardness Results for Coverability Problem of Well-Structured Pushdown Systems
Language and Automata Theory and Applications: 11th International Conference …, 2017•Springer
Abstract Well-Structured Pushdown Systems (WSPDSs) are pushdown 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.
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.
Abstract
Well-Structured Pushdown Systems (WSPDSs) are pushdown 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.
Springer
Showing the best result for this search. See all results