Deciding Reachability and the Covering Problem with Diagnostics for Sound Acyclic Free-Choice Workflow Nets Volume: 185 Issue: 1
Thomas M. Prinz Course Evaluation Service Friedrich Schiller University Jena Am Steiger 3, Haus 1, 07743 Jena, Germany [email protected], Christopher T. Schwanen Chair of Process and Data Science (PADS) RWTH Aachen University Ahornstraße 55, 52074 Aachen, Germany [email protected], · 2026
Read Deciding Reachability and the Covering Problem with Diagnostics for Sound Acyclic Free-Choice Workflow Nets Volume: 185 Issue: 1 by Thomas M. Prinz Course Evaluation Service Friedrich Schiller University Jena Am Steiger 3, Haus 1, 07743 Jena, Germany [email protected], Christopher T. Schwanen Chair of Process and Data Science (PADS) RWTH Aachen University Ahornstraße 55, 52074 Aachen, Germany [email protected], (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-02447.txt.
Description
Thomas M. Prinz and 2 co-authors sharpen the complexity of two classic questions for workflow nets, in a 2026 arXiv paper. Petri nets model processes as tokens moving through places and transitions. Reachability asks whether a given token pattern can occur, and covering asks whether a pattern containing at least those tokens can occur.
For sound, acyclic, free-choice workflow nets, the authors bring both problems down to a quadratic bound. They also explain answers, not just decide them. Three new concepts do the explaining: admissibility, requiring all marked places to be pairwise concurrent; maximum admissibility; and diverging transitions that originally produced the concurrent tokens. Algorithms borrow post-dominance frontiers from compiler construction. The result is a straightforward implementation that can say why a marking is or is not reachable.
Catalog record
| CREATOR | Thomas M. Prinz Course Evaluation Service Friedrich Schiller University Jena Am Steiger 3, Haus 1, 07743 Jena, Germany [email protected], Christopher T. Schwanen Chair of Process and Data Science (PADS) RWTH Aachen University Ahornstraße 55, 52074 Aachen, Germany [email protected], |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 235 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-02447