RREF-Based, Sound Detection of Invariant-Coverage Violations in Petri Net-Based Concurrent Systems
Applied Sciences · 31.10.2026 · 16 (21) · 10809
DOI: 10.3390/app162110809 ↗Kurz gefasst
Fachartikel in der Zeitschrift Applied Sciences, online erschienen am 31.10.2026. Verfasst von Maxim Maliński und 1 weiteren Autor:innen. Die Arbeit nennt 45 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Verifying a Petri net-based concurrent system is essential, since errors such as unbounded resource accumulation or deadlocks are costly after deployment. Invariant coverage is a diagnostic, but computing a minimal invariant basis can have exponential worst-case cost. Coverage can also be decided by linear-feasibility methods without basis enumeration, although diagnosis may require feasibility checks for places or transitions and an external optimization solver. This paper introduces Fast Verification Plus (FV+): two algorithms that use the reduced row echelon form of a Petri net incidence matrix to detect uncovered places and transitions in polynomial time. FV+ is sound: every reported element is genuinely uncovered. Its incompleteness is characterized. Evaluation on 386 Hippo repository models, against the Martínez-Silva algorithm, PIPE2, and GreatSPN, showed zero false positives among 752 P- and T-invariant coverage analyses. Although incomplete in general, FV+ achieved 100% agreement with coverage decisions on those analyses. This corpus level agreement does not establish completeness. It also returned results on models where other methods timed out. FV+ is thus a fast, solver-free structural filter that complements invariant-basis and LP-based coverage analysis.
Zitieren
APA
Maliński, M., & Wojnakowski, M. (2026). RREF-Based, Sound Detection of Invariant-Coverage Violations in Petri Net-Based Concurrent Systems. Applied Sciences, 16(21), 10809. https://doi.org/10.3390/app162110809
Vancouver
Maliński M, Wojnakowski M. RREF-Based, Sound Detection of Invariant-Coverage Violations in Petri Net-Based Concurrent Systems. Applied Sciences. 2026;16(21):10809. doi:10.3390/app162110809
BibTeX
@article{Maliski2026,
author = {Maliński, Maxim and Wojnakowski, Marcin},
title = {RREF-Based, Sound Detection of Invariant-Coverage Violations in Petri Net-Based Concurrent Systems},
journal = {Applied Sciences},
year = {2026},
volume = {16},
number = {21},
pages = {10809},
doi = {10.3390/app162110809}
}
EUVIMED