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

DOI10.4230/LIPIcs.FSTTCS.2018.44OpenAlexW2907292957MaRDI QIDQ5090985

Sylvain Salvati, Vincent Penelle, Grégoire Sutre

Publication date: 21 July 2022

Full work available at URL: https://hal.archives-ouvertes.fr/hal-01962407

zbMATH Keywords

termination problemvector addition systemshigher-order pushdown automataboundedness problemcoverability problem

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Petri nets and large finite sets
• The covering and boundedness problems for vector addition systems
• On boundedness problems for pushdown vector addition systems
• What makes Petri nets harder to verify: stack or data?
• Parallel program schemata
• Unboundedness and downward closures of higher-order pushdown automata
• On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension
• The Complexity of the Finite Containment Problem for Petri Nets
• Hyper-Ackermannian bounds for pushdown vector addition systems
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Mathematical Foundations of Computer Science 2005
• Nested Stack Automata
• Full AFLs and nested iterated substitution
• Well-structured transition systems everywhere!

This page was built for publication: On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems