Probabilistic Behavioural Acyclic Nets Nadiyah Almutairi1 1 School of Computing, Newcastle University, Science Square, Newcastle upon Tyne, NE4 5TG, United Kingdom In this paper, we extend our probabilistic framework in [1] to include behavioural abstraction relation which is so far lacked of such an extension. Behavioural abstraction is the mechanism where some part of a complex activity is related to another simplified system [2]. The hierarchy structure of behavioural abstraction involves two levels. The upper level represents an abstract view of the details regarding the evolution of the system at the lower level. Calculating probabilities in acyclic nets. In [1], we formally define how conflict between transitions is resolved probabilistically. More precisely, it is assumed that conflicting transitions are assigned positive numerical weights 𝜔 representing the likelihood of transitions and a zero weight for a transition is not allowed. Probabilities of concurrent transitions are given by the products of their weights over the sum of the weights of transitions in their conflict sets. 𝑝1 𝑎 𝑝3 7 𝑏 𝑝4 3 𝑝2 𝑝5 3 𝑐 Figure 1: Acyclic nets with with symmetric confusion. The overlapping between conflict and concurrency can cause a situation called confusion which interferes with the calculation of probabilities. In the literature, two types of confusion have been identified: symmetric confusion and asymmetric confusion. Figure 1 depicts an acyclic net with symmetric confusion. The scenario scenario({𝑎, 𝑐}) has three executions (𝜎1 = 𝑎𝑐, 𝜎2 = 𝑐𝑎, and 𝜎3 = {𝑎, 𝑐}). The probability of 𝜎1 is Pacnet (𝜎1 ) = (7/10) · 1 = 0.7. However, if 𝜎2 is executed, then the resulting probability is Pacnet (𝜎2 ) = (3/6) · 1 = .5 ̸= Pacnet (𝜎1 ). Also, in 𝜎3 = {𝑎, 𝑐} all the transitions are executed together with probability Pacnet (𝜎3 ) = (7 + 3)/(7 + 3 + 3) = 10/13 = 0.8 ̸= Pacnet (𝜎1 ) ̸= Pacnet (𝜎2 ). Hence one cannot assign a probability to this scenario. However, the symmetric confusion has no effect when {𝑎, 𝑐} are executed together as one step sequence (not their interleaving PNSE’23, International Workshop on Petri Nets and Software Engineering, June 26, 2023, Lisbon, Portugal " n.m.r.almutairi2@newcastle.ac.uk (N. Almutairi) © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) 1 execution). Note that there are classes of nets which exclude confusion by imposing structural restrictions, e.g., free-choice nets [3]. Behavioural abstraction acyclic nets and Confusion in behavioural abstraction, the low- level acyclic net provides full details of the process which is abstracted at the upper level. The high-level free-choice acyclic net hides the details of the behaviour of lower level. Hence, it is a bottom-up approach of abstraction such that it represents the states of an acylic net using one place [4]. Extending probabilities calculation to the behavioral relation requires that the probability of a transition at the high-level is the product of the weights all low-level transitions that are ascribed to it. 𝐴𝐶 𝑥 0.8 𝑠2 0.18 𝑝2 𝑠1 𝑝1 𝑦 𝑝3 0.42 𝐵 0.2 𝑠3 𝑧 𝑝4 0.4 𝑝1 𝑎 𝑝3 7 𝑏 𝑝4 3 6 3 𝑝2 𝑝5 𝑟1 𝑎 𝑟2 𝑐 𝑟3 3 𝑟4 7 𝑐 𝑏 𝑑 𝑟5 4 (a) (b) Figure 2: Probabilistic behavioural acyclic net (a) and with symmetric confusion (b) Figure 2 shows a behavioural acyclic net where the dash lines between the places of low-level and high-level acyclic nets represent the behavoiral relation, 𝛽. The low-level acyclic net in Figure 2(a) has three maximal scenarios as follow: maxscenario1 ({𝑎, 𝑐}), maxscenario2 ({𝑎, 𝑑}), maxscenario3 ({𝑏}) Therefore, the probability of each maximal scenario is presented at high-level as follows: 𝜔(𝑎) 𝜔(𝑐) 6 3 18 P(𝑥) = · = · = = 0.18 𝜔(𝑎) + 𝜔(𝑏) 𝜔(𝑐) + 𝜔(𝑑) 10 10 100 which means that 𝑥 is the high-level transition that is correspond for a scenario induced by the low-level transitions 𝑎 and 𝑐. Hence, its probability is calculated based on their weights. The probabilities for the rest high-level transitions are calculated similarly. We restrict the structure of upper level acyclic nets as being free-choice only. Therefore, any potential a/symmetric confusion within the upper acyclic net is excluded. In this section, we propose a new approach of handling confusion using behavioural relation. More precisely, the aim is to take an advantage of the structural constraint at the upper level such that the confused behaviour at the lower level is mapped to a probabilism confusion-free representation at the high level. In this case, the upper level net is seen as a controller of the low level confused behaviour. Figure 2(b) shows a low level acyclic net with symmetric confusion. It is the same confused acyclic net in Figure 1. However, here it is abstracted by a confusion-free (free-choice) high level acyclic net. Basically, all the maximal scenarios scenario({𝑎, 𝑐}) and scenario({𝑏}) of low-level are represented by scenario({𝐴𝐶}) and scenario({𝐵}) at the upper level respectively through the 𝛽 relation. Mapping both places of the lower acyclic net 𝑝3 ∈ 𝑎∙ and 𝑝5 ∈ 𝑐∙ to the same place 𝑠2 at the upper acyclic net captures the fact that 𝑎 and 𝑐 are executed together. Hence, the probability that {𝑎, 𝑐} are chosen over 𝑏 is reflected by executing 𝐴𝐶 at the upper level with probability 0.8 (based on their weights). More precisely, the probabilities of high-level transitions are calculated as follows: 𝜔(𝑎) + 𝜔(𝑐) 10 P(𝐴𝐶) = = = 0.8 𝜔(𝑎) + 𝜔(𝑐) + 𝜔(𝑏) 13 Similarly, 𝜔(𝑏) 3 P(𝐵) = = = 0.2 𝜔(𝑎) + 𝜔(𝑐) + 𝜔(𝑏) 13 Using behavioural relation to manage the occurring of confusion asserts the powerful aspect of abstraction based analysis. Intuitively, behavioural abstraction in this way not only delivers the simplified nature of complex behaviour, but also is capable to analyse it. That is because only the confusion-free step sequences are represented at the high-level. For example in symmetric confusion in Figure 1 (𝑎), the desirable execution is when {𝑎𝑐} are executed together. Such execution is reflected at the abstracted level. In another words, behavioural abstraction is filtering out the undesirable behaviour (the interleaving execution of 𝑎 and 𝑐 in the above example) without loosing significant information. In fact, this technique of excluding confusion targets the dynamic nature of confusion as it is purely behavioural. Only reachable markings where confusion is disappeared are considered in the 𝛽 relation. References [1] N. Almutairi, Probabilistic Communication Structured Acyclic Nets, in: PNSE@Petri Nets, vol. 3170 of CEUR Workshop Proceedings, CEUR-WS.org, 168–187, 2022. [2] P. Missier, B. Randell, M. Koutny, Modelling Provenance Using Structured Occurrence Networks, Springer, 183–197, 2012. [3] J. Desel, J. Esparza, Free Choice Petri Nets, vol. 40 of Cambridge Tracts in Theoretical Science, Springer, 1995. [4] B. Randell, M. Koutny, Failures: Their Definition, Modelling and Analysis, vol. 4711, ISBN 978-3-540-75290-5, 260–274, doi:\let\@tempa\bibinfo@X@doi10.1007/978-3-540-75292-9_ 18, 2007.