EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

RREF-Based, Sound Detection of Invariant-Coverage Violations in Petri Net-Based Concurrent Systems

Maxim Maliński, Marcin Wojnakowski

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →