Fundamenta Informaticae - Volume 190, issue 2-4

Authors: Bernardinello, Luca | Kleijn, Jetty | Petrucci, Laure

Article Type: Other

DOI: 10.3233/FI-242166

Citation: Fundamenta Informaticae, vol. 190, no. 2-4, pp. i-ii, 2024

Authors: Hélouët, Loïc | Agrawal, Pranay

Article Type: Research Article

Abstract: In time Petri nets (TPNs), time and control are tightly connected: time measurement for a transition starts only when all resources needed to fire it are available. Further, upper bounds on duration of enabledness can force transitions to fire (this is called urgency ). For many systems, one wants to decouple control and time, i.e. start measuring time as soon as a part of the preset of a transition is filled, and fire it after some delay and when all needed resources are available. This paper considers an extension of TPN called waiting nets that dissociates time measurement …and control. Their semantics allows time measurement to start with incomplete presets, and can ignore urgency when upper bounds of intervals are reached but all resources needed to fire are not yet available. Firing of a transition is then allowed as soon as missing resources are available. It is known that extending bounded TPNs with stopwatches leads to undecidability. Our extension is weaker, and we show how to compute a finite state class graph for bounded waiting nets, yielding decidability of reachability and coverability. We then compare expressiveness of waiting nets with that of other models w.r.t. timed language equivalence, and show that they are strictly more expressive than TPNs. Show more

Keywords: Time, Petri nets, State Classes

DOI: 10.3233/FI-242167

Citation: Fundamenta Informaticae, vol. 190, no. 2-4, pp. 63-107, 2024

Authors: Mannel, Lisa L. | van der Aalst, Wil M. P.

Article Type: Research Article

Abstract: In process discovery, the goal is to find, for a given event log, the model describing the underlying process. While process models can be represented in a variety of ways, Petri nets form a theoretically well-explored description language and are therefore often used. In this paper, we extend the eST-Miner process discovery algorithm. The eST-Miner computes a set of Petri net places which are considered to be fitting with respect to a certain fraction of the behavior described by the given event log as indicated by a given noise threshold. 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 abstract from infrequent behavioral patterns occurring only in some traces. However, when combining places into a Petri net by connecting them to the corresponding uniquely labeled transitions, the resulting net can replay exactly those traces from the event log that are allowed by the combination of all inserted places. Thus, inserting places one-by-one without considering their combined effect may result in deadlocks and low fitness of the Petri net. In this paper, we explore adaptions of the eST-Miner, that aim to select a subset of places such that the resulting Petri net guarantees a definable minimal fitness while maintaining high precision with respect to the input event log. Furthermore, current place evaluation techniques tend to block the execution of infrequent activity labels. Thus, a refined place fitness metric is introduced and thoroughly investigated. In our experiments we use real and artificial event logs to evaluate and compare the impact of the various place selection strategies and place fitness evaluation metrics on the returned Petri net. Show more

Keywords: Process Discovery, Petri Nets, eST-Miner, long-term dependencies, non-free choice

DOI: 10.3233/FI-242168

Citation: Fundamenta Informaticae, vol. 190, no. 2-4, pp. 109-158, 2024

Authors: van der Werf, Jan Martijn E.M. | Rivkin, Andrey | Montali, Marco | Polyvyanyy, Artem

Article Type: Research Article

Abstract: A model of an information system describes its processes and how resources are involved in these processes to manipulate data objects. This paper presents an extension to the Petri nets formalism suitable for describing information systems in which states refer to object instances of predefined types and resources are identified as instances of special object types. Several correctness criteria for resource- and object-aware information systems models are proposed, supplemented with discussions on their decidability for interesting classes of systems. These new correctness criteria can be seen as generalizations of the classical soundness property of workflow models concerned with process control …flow correctness. Show more

Keywords: Information System, Verification, Data Correctness, Resource Correctness

DOI: 10.3233/FI-242169

Citation: Fundamenta Informaticae, vol. 190, no. 2-4, pp. 159-207, 2024