The third variant of MSR we present here is the Parallel Probabilistic Multiset Rewriting (PPMSR), that is based on the same idea of PMSR. As in PMSR, in this model each rule has a speed that is translated into a probability for a small time interval ∆T . The difference between PMSR and PPMSR is that in the latter we do not divide ∆T by the number of rules for obtaining an interval
∆t in which at most one rule can be applied, but in ∆T we use probabilities for choosing a subset of the rules, and we apply all them simultaneously. This simultaneous application motivates the word “Parallel” in the name of the model, and it introduces some difficulties in the definition of the semantics. We will see in Section 2.5 that using the same time interval ∆T and the same initial multiset for both PMSR and PPMSR, the states of the transition system obtained from the latter are in general less that the states of the former. Moreover, PPMSR allows us to specify some special kinds of rules.
Now we introduce probabilistic rewrite rules for multisets. As in the previ-ous sections, we assume a (possibly) infinite set Σ of elements ranged over by A, B, C, D, . . .and a universe of multisets U.
Definition 9 (PPMSR Rule). A Parallel Probabilistic Multiset Rewrite Rule is a triple (M, f, M0) where:
– M and M0 are multisets of elements in Σ
– f : U 7→ [ 0, 1 ] is a probability function: given a multiset, it returns the probability of application of the rule to that multiset.
A PPMSR Rule can be denoted also as M →Pf M. We require that, given a multiset M00, if M * M00 then f (M00) = 0.
Now, a PPMSR System corresponds to a MSR System in which PPMSR Rules are used instead of standard rewrinting rules.
Definition 10 (PPMSR System). A Parallel Probabilistic Multiset Rewrit-ing System is a pair (M, R) where M is a multiset and R is a finite set of PPMSR rules.
The idea is that a subset of the rules is chosen by using their probabilities and all the ones that have been chosen are used (exactly once) to rewrite M . For instance, if we have the following rules1:
R = {R1: ({A},1
2,{C}), R2: ({B},1 3,{D})}
we have that R1has probability 12 of being chosen, while R2 has probability 13. This implies that the subset {R1, R2} will be applied with probability 12×13= 16,
1 With12 and 13as probability functions we mean that probabilities are those constants if the rule can be applied and they are 0 otherwise. This satisfies the requirement given in Def. 9.
the subset {R1} with probability12×(1−13) =26, the subset {R2} with probability (1 − 12) × 13 = 16, and the subset ∅ with probability (1 − 12) × (1 − 13) = 26. If the multiset to be rewritten is {A, A, B, B}, we obtain {A, B, C, D} with probability 16, {A, B, B, C} with probability 26, {A, A, B, D} with probability 16, and {A, A, B, B} with probability 26.
We will see that, in general, in order to compute the probability of a multiset M to be rewritten into another given one M0 we will have to face two problems.
The first problem is that more than one subsets of R may transform M into M0, hence we will have to sum up their probabilities. For instance, if we have:
R = {R1: ({A, B}, f1,{C}), R2: ({A, B}, f2,{B}), (ex1) R3: ({B}, f3,{C}, R4: ({B}, f4,{B})}
then the multiset M = {A, B, B} can be rewritten into M0 = {B, C} either by applying R1 and R3 or by applying R2 and R4. Moreover, we have that the same multiset M can be rewritten into itself either by applying only R4 or by applying none of the rules.
The second problem we have to face is that some rules of a set R may not be applied together to a multiset M . For instance, if we have:
R = {R1: ({A, B}, f1,{C}), R2: ({A}, f2,{D})} (ex2) and if the multiset to rewrite is M = {A, B}, we have that R1 and R2 cannot be applied at the same time because there are not enough A elements in M .
The semantics we are going to give takes care of these two problematic situa-tions, and it also guarantees that in the good cases (when the two problems don’t arise) the probability of a subset of rules to be applied is simply the product of the probabilities of the rules multiplied by the product of the opposites of the probabilities of the other rules.
Now, at each step every rule Ri = (Mi, fi, Mi0) in R can be applied to the multiset M with probability fi(M ) and, obviously, the probability of each rule Ri to be not applied is 1 − fi(M ). This fact allows us to define a set of special rules, called corules, that will be very useful in order to compute the overall probability of the multiset M to be rewritten into a particular multiset M0 by the application of the rules in R: a corule represents the non-application of a rule.
Definition 11 (Corule). Given a rule Ri= (Mi, fi, Mi0), the corule Ri is the following probabilistic rewriting rule:
Ri = (∅, fi,∅)
where fi(M ) = 1 − fi(M ) for all M in U. We denote with fRi a rule that could be either Ri or Ri and we denote with efi the probability function of fRi, that is fei= fi if fRi= Ri and efi= fi if fRi= Ri.
Moreover, we introduce another technical notation that we will use in the definition of the semantics. Let R0 = {Rj1, . . . , Rjk} be a subset of R, we define
the extension of R0 the set { fR1, . . . , fRn} where fRi = Ri if i ∈ j1, . . . , jk, and Rfi = Ri otherwise.
Now, let P(R) be the powerset of R, and let PM →M0(R) be the subset of P(R) containing all and only the sets of rules that rewrite M into M0. We denote with EPM →M0(R) the set of all the extensions of the elements in PM →M0(R), that is the set of all possible applications and non-applications of rules in R transforming M into M0. For instance, if R is as in (ex1), M = {A, B, B} and M0 = {B, C}, we obtain:
PM →M0(R) =
{R1, R3}, {R2, R4} and
EPM →M0(R) =
{R1, R2, R3, R4}, {R1, R2, R3, R4}
By now, we have given some definitions that will help us in solving the first of the two problems introduced above (example (ex1)): the fact that more than one subsets of R may rewrite M into M0. Now, in order to solve the second problem (example (ex2)), we have to introduce a sort of conditional probability that gives the probability of a rule to be applied if it is known that some other rules have to be applied at the same time.
Definition 12 (Conditional probability of application). Given a set of rules R = {R1, . . . , Rn} and k pairwise distinct indexes j1, . . . , jk chosen in 1, . . . , n, the conditional probability of application of rule Ri and of the corre-sponding corule Ri to the multiset M when gRj1, . . . , gRjk are known to be applied are:
PM(Ri|gRj1, . . . , gRjk) =
(fi(M ) if Mi⊆ M \ (Mj1∪ . . . ∪ Mjk)
0 otherwise
and
PM(Ri|gRj1, . . . , gRjk) =
(fi(M ) if Mi⊆ M \ (Mj1∪ . . . ∪ Mjk)
1 otherwise
We denote with PM(fRi) the conditional probability PM(fRi|∅) and it holds that PM(fRi) = efi(M ).
The conditional probability of application allows us to associate probability zero to the set of rules that cannot be applied together. For instance, if we take R as in (ex2) with M = {A, B}, we obtain PM(R2|R1) = 0, because {A} 6∈ {A, B} \ {A, B} and, similarly, PM(R2|R1) = 0. We will use these results in order to say that R1 and R2cannot be applied together.
Now we are ready to define the probability of a multiset M to be rewritten into a particular multiset M0 by applying some rules from a set R. In this defini-tion, for each element in EPM →M0(R) we consider all the possible permutations of its n rules. Then, for each permutation, we multiply the conditional probabil-ity of each rule and we divide the result by the number of possible permutations
in order to obtain the average of all of them. The final result is the sum of all the average probabilities of the elements in EPM →M0(R).
Definition 13 (Probability of a transition). Given a system (M, R), the probability of M to be rewritten into a given multiset M0 by the rules in R is the following:
If the system is in a state in which the problems shown by (ex1) and (ex2) do not occur, then we have that the probability of applying a particular combination of rules and corules is simply the product of their probabilistic functions. In particular, the following proposition holds.
Now we give the semantics of PPMSR as a probabilistic transition system.
Definition 14 (Semantics). The semantics of PPMSR is a probablistic tran-sition system in which states are PPMSR Systems and trantran-sitions are described by the following inference rule:
(M, R)−−−−−−−−→ (MP(M,M0,R) 0,R)
Obviously, the number of states in the semantics of PPMSR is infinite, but most of them are reachable with probability zero. The number of reachable states depends on the format of the rewriting rules: in many practical cases it is finite.