Volume 190, issues 2-4: Petri Nets 2022

special issue of Petri Nets 2022


1. Waiting Nets: State Classes and Taxonomy

Loïc Hélouët ; Pranay Agrawal.
In time Petri nets (TPNs), time and control are tightly connected: timemeasurement for a transition starts only when all resources needed to fire itare available. Further, upper bounds on duration of enabledness can forcetransitions to fire (this is called urgency). For many systems, one wants todecouple control and time, i.e. start measuring time as soon as a part of thepreset of a transition is filled, and fire it after some delay \underline{and}when all needed resources are available. This paper considers an extension ofTPN called waiting nets that dissociates time measurement and control. Theirsemantics allows time measurement to start with incomplete presets, and canignore urgency when upper bounds of intervals are reached but all resourcesneeded to fire are not yet available. Firing of a transition is then allowed assoon as missing resources are available. It is known that extending boundedTPNs with stopwatches leads to undecidability. Our extension is weaker, and weshow how to compute a finite state class graph for bounded waiting nets,yielding decidability of reachability and coverability. We then compareexpressiveness of waiting nets with that of other models w.r.t. timed languageequivalence, and show that they are strictly more expressive than TPNs.

2. Discovering Process Models With Long-Term Dependencies While Providing Guarantees and Filtering Infrequent Behavior Patterns

Lisa Luise Mannel ; Wil M. P. van der Aalst.
In process discovery, the goal is to find, for a given event log, the modeldescribing the underlying process. While process models can be represented in avariety of ways, Petri nets form a theoretically well-explored descriptionlanguage and are therefore often used. In this paper, we extend the eST-Minerprocess discovery algorithm. The eST-Miner computes a set of Petri net placeswhich are considered to be fitting with respect to a certain fraction of thebehavior described by the given event log as indicated by a given noisethreshold. It evaluates all possible candidate places using token-based replay.The set of replayable traces is determined for each place in isolation, i.e.,these sets do not need to be consistent. This allows the algorithm to abstractfrom infrequent behavioral patterns occurring only in some traces. However,when combining places into a Petri net by connecting them to the correspondinguniquely labeled transitions, the resulting net can replay exactly those tracesfrom the event log that are allowed by the combination of all inserted places.Thus, inserting places one-by-one without considering their combined effect mayresult in deadlocks and low fitness of the Petri net. In this paper, we exploreadaptions of the eST-Miner, that aim to select a subset of places such that theresulting Petri net guarantees a definable minimal fitness while maintaininghigh precision with respect to the input event log. Furthermore, current placeevaluation techniques tend to block […]

3. Correctness Notions for Petri Nets with Identifiers

Jan Martijn E. M. van der Werf ; Andrey Rivkin ; Marco Montali ; Artem Polyvyanyy.
A model of an information system describes its processes and how resourcesare involved in these processes to manipulate data objects. This paper presentsan extension to the Petri nets formalism suitable for describing informationsystems in which states refer to object instances of predefined types andresources are identified as instances of special object types. Severalcorrectness criteria for resource- and object-aware information systems modelsare proposed, supplemented with discussions on their decidability forinteresting classes of systems. These new correctness criteria can be seen asgeneralizations of the classical soundness property of workflow modelsconcerned with process control flow correctness.