Improved algorithm for reachability in d-VASS

DOI10.4230/LIPICS.ICALP.2024.136MaRDI QIDQ6875045zbMATH OpenFDO

Authors Yuxi Fu, Qizhe Yang, Yangluo Zheng

Publication date 14 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2024.136

zbMATH Keywords

Petri netreachabilityvector addition system

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A structure to decide reachability in Petri nets
• Complexity bounds for ordinal-based termination (invited talk)
• Complexity hierarchies beyond elementary
• CONCUR 2004 - Concurrency Theory
• Demystifying Reachability in Vector Addition Systems
• Flat Petri nets (invited talk)
• Minimal solutions of linear diophantine systems : bounds and algorithms
• New lower bounds for reachability in vector addition systems
• Ordinal recursive bounds for Higman's theorem
• Reachability in Succinct and Parametric One-Counter Automata
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• Reachability in vector addition systems is Ackermann-complete
• Reachability in vector addition systems is primitive-recursive in fixed dimension
• Set Theory
• The complexity of downward closure comparisons
• The covering and boundedness problems for vector addition systems
• The downward-closure of Petri net languages
• The reachability problem for Petri nets is not primitive recursive
• The Reachability Problem for Two-Dimensional Vector Addition Systems with States
• The taming of the semi-linear set

Cited in

(3)

• Challenges of the reachability problem in infinite-state systems (invited paper)
• Reachability in symmetric VASS
• Reachability in vector addition system with states parameterized by geometric dimension

This page was built for publication: Improved algorithm for reachability in \(d\)-VASS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875045)