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

CREATORThomas 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],
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE235 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-02447

Browse the full library · About the Tower of Babel