Skip to Main content Skip to Navigation
Conference papers

On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems

Vincent Penelle 1 Sylvain Salvati 2 Grégoire Sutre 1
2 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : Karp and Miller's algorithm is a well-known decision procedure that solves the termination and boundedness problems for vector addition systems with states (VASS), or equivalently Petri nets. This procedure was later extended to a general class of models, well-structured transition systems, and, more recently, to pushdown VASS. In this paper, we extend pushdown VASS to higher-order pushdown VASS (called HOPVASS), and we investigate whether an approach à la Karp and Miller can still be used to solve termination and boundedness. We provide a decidable characterisation of runs that can be iterated arbitrarily many times, which is the main ingredient of Karp and Miller's approach. However, the resulting Karp and Miller procedure only gives a semi-algorithm for HOPVASS. In fact, we show that coverability, termination and boundedness are all undecidable for HOPVASS, even in the restricted subcase of one counter and an order 2 stack. On the bright side, we prove that this semi-algorithm is in fact an algorithm for higher-order pushdown automata.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-01962407
Contributor : Grégoire Sutre <>
Submitted on : Thursday, March 4, 2021 - 2:48:38 PM
Last modification on : Friday, March 5, 2021 - 3:27:01 AM

File

LIPIcs-FSTTCS-2018-44.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Vincent Penelle, Sylvain Salvati, Grégoire Sutre. On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems. FSTTCS 2018 - 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2018, Ahmedabad, India. pp.44:1-44:20, ⟨10.4230/LIPIcs.FSTTCS.2018.44⟩. ⟨hal-01962407⟩

Share

Metrics

Record views

136

Files downloads

8