Stochastic Fragments

Jérôme Feret, Heinz Koepp, Tatjana Petrov

► To cite this version:

Jérôme Feret, Heinz Koepp, Tatjana Petrov. Stochastic Fragments. International Journal of Software and Informatics (IJSI), 2014, Special Issue on DCM09, 7 (4), pp.527-604. hal-01098561

HAL Id: hal-01098561

https://inria.hal.science/hal-01098561v1

Submitted on 15 Feb 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Stochastic fragments:
A framework for the exact reduction of the
stochastic semantics of rule-based models*

Jérôme Feret¹, Heinz Koepp¹, and Tatjana Petrov²

¹ LIENS (INRIA/ENS/CNRS)

² École Polytechnique Fédérale de Lausanne (EPFL)

**Abstract.** In this paper, we propose an abstract interpretation-based framework for reducing the state space of stochastic semantics for protein-protein interaction networks. Our approach consists in quotienting the state space of networks. Yet interestingly, we do not apply the widely-used strong lumpability criterion which imposes that two equivalent states behave similarly with respect to the quotient, but a weak version of it. More precisely, our framework detects and proves some invariants about the dynamics of the system: indeed the quotient of the state space is such that the probability of being in a given state knowing that this state is in a given equivalence class, is an invariant of the semantics. Then we introduce an individual-based stochastic semantics (where each agent is identified by a unique identifier) for the programs of a rule-based language (namely Kappa) and we use our abstraction framework for deriving a sound population-based semantics and a sound fragments-based semantics, which give the distribution of the traces respectively for the number of instances of molecular species and for the number of instances of partially defined molecular species. These partially defined species are chosen automatically thanks to a dependency analysis which is also described in the paper.

# 1 Introduction

Transient complex formation and mutual posttranslational modification of proteins [50] in the induction of a signaling pathway, or in protein-protein interaction networks in general, give rise to a combinatorial number of reachable molecular species [30]. For such bio-molecular systems, traditional chemical kinetics face fundamental limitations, that are related to the question how bio-molecular events are represented and translated into an executable quantitative description [36, 51]. More specifically, chemical reactions can only operate on a collection of

<footnote>* Jérôme Feret’s contribution was partially supported by the ABSTRACTCELL ANR-Chair of Excellence. Heinz Koeppl acknowledges the support from the Swiss National Science Foundation, grant no. 200020-117975/1. Tatjana Petrov acknowledges the support from SystemsX.ch, the Swiss Initiative in Systems Biology.</footnote>
fully specified molecular species and each molecular species results in one differ-
ential equation, describing the rate of change of its concentration. Many com-
binatorial systems do not permit the enumeration of all molecular species and
thus render their traditional differential description prohibitive. However, even if
one could enumerate them, it remains questionable whether chemical reactions
is the appropriate way to represent such systems.

The observation that signaling pathways are massively distributed systems
has led Regev et al. [44] to propose Milner’s π-calculus [37] for their description.
Since then, numerous variants of this calculus focusing on different modeling
situations have been developed [27, 43, 8, 21]. The execution or simulation of such
process algebra models is done by equipping them with a stochastic semantics
according to Gillespie’s algorithm [29]. Pathways for which such types of models
have been designed include MAPK (mitogen-activated-protein-kinase) cascades
[46], the EGFR (epidermal-growth-factor-receptor) pathway [2], the yeast mating
pathway [35, 48] (see also [31] and the references therein).

The particular variant considered in this work, are agent-based or rule-based
models [22, 3]. They address the representational challenge faced when model-
ing combinatorial signaling pathways. Agents are considered proteins and rules
explicitly encode binding and modification events among proteins. In practice,
events are conditioned only on a limited, local context. For instance, a binding
event between two proteins may be conditioned on the posttranslational mod-
ification of one particular protein-domain in one binding partner but may be
independent from the modification state of all other domains. Rule-based mod-
els exploit this limited context. They just enumerate that part of a molecular
species that is relevant for a rule to be applicable. Thus, in contrast to chem-
ical reactions, rules can operate on a collection of partially specified molecular
species. By an extension of Gillespie’s algorithm, stochastic simulations of rule-
based models can be done without ever enumerating molecular species [19].

However, stochastic simulations may become prohibitive in realistic scenarios,
where one encounters highly abundant proteins. Recently, efforts have been made
to overcome this limitation through translating rule sets into compact differential
descriptions [11, 28]. Exploiting the local context of rules, the resulting state
variables denote concentrations of partially defined species, rather than of single
molecular species. In [28] a general and scalable way is proposed to detect those
partially defined species or *fragments* and to derive their differential semantics
in a self-consistent manner. Case studies therein show a significant reduction in
the state-space dimension.

A natural question that arises in this context is whether we can use the same
*fragmentation* proposed for the differential semantics to compute the stochastic
semantics of a system. Following the work in [28], we develop an abstract in-
terpretation framework to address this question. Abstract interpretation [13, 14,
16] is a unifying theory of approximation of mathematical structures. One of its
application is the systematic design of efficient algorithms to compute approxi-
mate answers to complex (if not undecidable) questions about the semantics of
programs. These abstractions can be established by means of various mathemat-
ical construction including Galois connection, equivalence relations, or closure operators [13, 16]. Moreover, they can usually be combined in various ways (eg see composition [14], product [15], or complementation [12]). In this paper, we use abstract interpretation to formalize the relationships between species-based stochastic semantics and fragments-based stochastic semantics. Thus, we get a formal proof of the soundness of our approach.

We first illustrate the framework by arguing on a simple case study, and then offer the characterization of the fragments that allow sound and complete simulations in the abstract. We finally propose an efficient procedure for computing stochastically sound fragments by static analysis of the rule set and the accompanying initial conditions.

Alternative approaches to the sound abstraction of stochastic processes exist. As an extension of classic bisimulation, the notion of probabilistic bisimulation [34] was among the first such approaches. It is extended to continuous-state and continuous-time in [23] and, for the discrete-state case, to weak bisimulation [1]. For instance, in [23] authors use bisimulation of labeled Markov processes, the state space of which is not necessarily discrete, and they provide a logical characterization of probabilistic bisimulation. Recently, another notion of weak bisimulation was introduced [26]. Therein two labeled Markov chains are defined to be equivalent if every finite sequence of observations has the same probability to occur in the two chains. The authors offer a polynomial-time procedure to decide whether two labeled Markov chains are equivalent in that sense. In queueing theory [5] *lumpability* [32] is used to characterize a sound aggregation or lumping of finite Markov chains. According to it, a Markov chain is lumpable with respect to a given aggregation (quotienting) of its states, if the lumped chain preserves the Markovian property. A sound aggregation for *any* initial probability distribution is referred to as *strong* lumpability, while otherwise it is termed *weak* lumpability [7, 47]. To this extent, our framework is an instance of weak lumpability.

Abstract interpretation has also been used to analyze stochastic semantics. Abstract Monte Carlo methods [39, 25] mix testing and abstractions in order to estimate the probabilities that some outcomes occur in programs controlled by an environment with probabilistic behavior (with both probabilistic and non-probabilistic non-deterministic behavior in [39]). In [38], a generic framework has been introduced in order to lift numerical domains to probabilistic semantics featuring non-probabilistic non-determinism: this framework allows the abstraction of states by some of their properties of interest and the abstraction of probabilities by some intervals. This has inspired the work in [9] for the abstraction of Markov chains generated by systems of ground reactions into Interval Markov Chains: these Markov chain provide lower and upper bounds for the probabilities of temporal properties. In our framework, we only do abstractions that ensure that we can compute probabilities exactly. This allows us to analyze precisely bio-molecular systems despite the abundance of back-trackings in such systems.

While inspired by the work in [28] for reducing the dimension of differential semantics, the present work has several differences. In [28], dependencies analy-
ses are used to detect which correlations have no influence on system behavior; so the approximation forgets about some correlations. In the present paper, we use dependencies analyses to detect which parts of molecular species are uncorrelated (that is to say that we detect which correlations cannot be enforced by the system). As a consequence, we forget no information about states distributions (since the abstraction can be inverted since we know that there is no correlation). The counterpart of this is that the reduction factor is less impressive. Nevertheless, the choice for this trade-off was imposed by the fact that stochastic semantics are much harder to abstract than differential semantics.

The paper is organized as follows. In Section 2 we develop intuition for the proposed framework by considering a case study. We define a bio-molecular system with two types of interacting agents carrying one modifiable state each, resulting in eight reachable molecular species. We introduce the following three levels of granularity to describe the stochastic behavior of that system: (1) - a description with identified agents, where we record the binding and modification state of every single agent instance; (2) - a description with anonymous agents, where we only track the multiplicity of each type of molecular species within the reaction mixture and finally (3) - a fragment-based description, where we aggregate species that have the same stochastic behavior into fragments. Figure 1 illustrates the basic idea and show all three levels of granularity for an example discussed in Section 5. For the fragment-based description, we prove

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Three levels of granularity for the description of a bio-molecular reaction system and their respective transformations: a system with identified agents (left), a system of molecular species and anonymous agents (middle) and a system of abstract species or fragments (right). The depicted case corresponds to the example discussed in Section 5.</figcaption></figure>

that this abstraction satisfies the necessary properties of soundness and completeness. To this end, we discuss a simulation experiments showing the validity
$$ 
\begin{align*}
A_i^\epsilon \underset{k_{A-}}{\overset{k_{A+}}{\rightleftharpoons}} A_i^*
\\[1.5ex]
A_i^\epsilon B_j^\epsilon \underset{k_{A-}}{\overset{k_{A+}}{\rightleftharpoons}} A_i^* B_j^\epsilon
\\[1.5ex]
A_i^\epsilon B_j^* \underset{k_{A-}}{\overset{k_{A+}}{\rightleftharpoons}} A_i^* B_j^*
\end{align*}
$$

(a) A activation.

$$ 
\begin{align*}
B_j^\epsilon \underset{k_{B-}}{\overset{k_{B+}}{\rightleftharpoons}} B_j^*
\\[1.5ex]
A_i^\epsilon B_j^\epsilon \underset{k_{B-}}{\overset{k_{B+}}{\rightleftharpoons}} A_i^\epsilon B_j^*
\\[1.5ex]
A_i^* B_j^\epsilon \underset{k_{B-}}{\overset{k_{B+}}{\rightleftharpoons}} A_i^* B_j^*
\end{align*}
$$

(b) B activation.

$$ 
\begin{align*}
A_i^\epsilon + B_j^\epsilon \underset{k_{A..B}}{\overset{k_{A+B}}{\rightleftharpoons}} A_i^\epsilon B_j^\epsilon
\\[1.5ex]
A_i^* + B_j^\epsilon \underset{k_{A..B}}{\overset{k_{A+B}}{\rightleftharpoons}} A_i^* B_j^\epsilon
\\[1.5ex]
A_i^\epsilon + B_j^* \underset{k_{A..B}}{\overset{k_{A+B}}{\rightleftharpoons}} A_i^\epsilon B_j^*
\\[1.5ex]
A_i^* + B_j^* \underset{k_{A..B}}{\overset{k_{A\star+B\star}}{\rightleftharpoons}} A_i^* B_j^*
\end{align*}
$$

(c) AB complexation.

<caption>Fig. 2. Reactions among identified agents.</caption>

of the proposed fragment-based description. Section 3 lays out the general theory to describe arbitrary bio-molecular system in the three levels of granularity. We make use of weighted labeled transition systems to describe the system's stochastic semantics at all three levels. Abstraction and concretization functions for such transition systems are introduced and used to prove soundness and completeness of abstractions. In order to do so, we define measurable sets of traces of the continuous-time semantics and require that the probability of such a trace set in the abstract is the sum of probabilities of all corresponding trace sets in the concrete. Furthermore, we introduce admissible equivalence relations between concrete states that induce a sound abstraction. Moreover we show that abstractions can be composed and factorized and thus obey a particular abstraction algebra.

To derive a scalable way for constructing fragments of arbitrary bio-molecular systems, we utilize the rule-based modeling language Kappa [19]. We introduce the language in Section 4 and we discuss individual-based, population-based and fragments-based semantics in terms of Kappa. Of particular importance in this context is the individual-based semantics as it coincides with the implementation of the rule-based simulator, described in [19]. Based on the notion of the *contact map* of a rule set we finally propose in Section 5 a general procedure to compute stochastic fragments. To this end, we provide results for the achieved dimensionality reduction for a collection of rule-based models of well-known signaling pathways and relate the results to the reduction obtained using the self-consistent fragments of [28].

## 2 Case study

We consider a molecular stochastic system in three different granularities of observation. We will notice that the first two levels of observation always match, whereas the third and the first level of observation match only when some necessary conditions are satisfied.

The system is made of particles of type A and particles of type B. These particles can be in two levels of energy. The particles which are in the low
level of energy are called *deactivated*, whereas the particles which are in the high level of energy are called *activated*. The dynamics of the system includes modification of the level of energy of some particles (in both ways), and complexation/dissociation of particles of type A with particles of type B.

At initial state, no particle is activated and there is no complex yet. We consider $m+n$ particles $A_1, \dots, A_m$ and $B_1, \dots, B_n$. Since there is no birth or deletion of particles, at any point in time, the total number of particles $A$ stays $m$ and we have always $n$ particles of type $B$. In the rest of the paper, we use the variable $X$ for denoting either the symbol $A$ or the symbol $B$. The variables $i$ and $j$ denote some integers between 1 and $\max(m,n)$. Each particle $X_i$ can be either in its deactivated form $X_i^\epsilon$, or in its activated form $X_i^*$. We use the variables $\diamond$ and $\diamond$ for denoting either the symbol $\epsilon$ or $*$. Finally, a particle $A_i^\diamond$ and $B_j^\diamond$ can form a complex that is denoted by $A_i^\diamond B_j^\diamond$. We consider the reactions that are given in Fig. 2. The reactions in Fig. 2(a) describe the activation/deactivation of particles $A_i$. We shall notice that the rates of activation $k_{A+}$ and deactivation $k_{A-}$ are the same when $A_i$ is not bound, when $A_i$ is bound to a deactivated $B_j$, and when $A_i$ is bound to an activated $B_j$. Moreover, these rates do depend on neither the index $i$ of the particle $A_i$, nor the index $j$ of the potential particle $B_j$ which may be bound to the particle $A_i$. The reactions in Fig. 2(b) describes the activation/deactivation of particles $B_j$. We shall notice that the rates of activation $k_{B+}$ and deactivation $k_{B-}$ are the same when $B_j$ is not bound, when $B_j$ is bound to a deactivated $A_i$, and when $B_j$ is bound to an activated $A_i$. Moreover, these rates do depend on neither the index $j$ of the particle $B_j$, nor the index $i$ of the potential particle $A_i$ which may be bound to the particle $B_j$. The reactions in Fig. 2(c) describe the complex formation/dissociation of two particles $A_i$ and $B_j$. We have associated a different rate to complex formation when both $A_i$ and $B_j$ are activated. This way, in the case when the rate $k_{A^*+B^*}$ is greater than the rate $k_{A+B}$, the complex formation is privileged when both $A_i$ and $B_j$ are activated. Nevertheless, these rates do not depend on the indexes $i$ and $j$ of the particles $A_i$ and $B_j$.

We will show three abstraction levels of observation of this system: (1) a model with identified particles, described in Fig. 2; (2) a model with anonymous particles (Fig. 3), where we identify all particles of same type, and (3) a model with anonymous fragments (Fig. 5), where we identify the complexes with the activation state of only one of participating particles specified. We have initially $m$ particles of inactivated free $A$, and $n$ particles of inactivated free $B$'s, and this is conserved during the evolution of the system's dynamics. When abstracting the system, the additional conservation laws appear, and the dimension of a state vector decreases: the dimensions of the three levels of observation decreases from $2 \cdot m + 2 \cdot n + 4 \cdot m \cdot n - 2$ to 6 and 5 dimensions. The reduction of the state space motivates to question when we may analyze the abstract system rather than the concrete one, since we might abstract too much information and get incorrect results. For our case study, we argue that we can not always use the model with anonymous fragments to deduce the correct stochastic semantics. More precisely, we show in Sect. 2.2 that deriving the stochastic semantics on
the abstract states is sound if and only if the parameters for associations $k_{A+B}$ and $k_{A^*+B^*}$ are equal. In other words, if they are equal, the information lost in the abstraction still makes it possible to reproduce the stochastic behavior in a sound way. If they are not equal, wrong computations occur. Intuitively, this is due to the fact that making all kinetic rates for association and dissociation to be equal makes all four combinations of activation levels of particles within complexes to have identical dynamics. On the other hand, once we prioritize one complex type, this does not hold any more.

The further analysis of the case study is organized as following: In Sect. 2.1, 2.2, and 2.3, we compute the cardinality of the reachable configuration sets depending on $m$ and $n$ and discuss the dynamic behaviors of each of the three abstraction levels. We analyze in more detail the system with anonymous fragments: we prove soundness in case $k_{A+B} = k_{A^*+B^*}$ by case analysis on the rule set (Sect. 2.3.1), and to prove the non-soundness, we give a counter-example (Sect. 2.3.2). Finally, we confirm (Sect. 2.3.3) the theoretical results experimentally. Since the fragments that we consider are equivalent to the differential fragments of [28], our result also indicates that, differential fragments may lead to inconsistent stochastic semantics.

## 2.1 A model with identified particles

We first observe the model of this system where each particle is fully identified by an index. The number of states of this system is given by the following expression:

$$2^m \cdot 2^n \cdot \sum_k (k! \cdot C_k^m \cdot C_k^n \mid k \in \mathbb{N}).$$

Indeed, any particle $A_i$ can be activated, or not, which gives the factor $2^m$. Moreover, any particle $B_j$ can be activated, or not, which gives the factor $2^n$. The index $k$ in the sum denotes the number of complexes in the system. Whenever there are exactly $k$ complexes (containing both a particle $A$ and a particle $B$) in the system, one has to choose the $k$ particles $A_i$ that are bound (as many possibilities as the number $C_k^m$ of parts of $k$ elements in a set of $m$ elements), and the $k$ particles $B_j$ that are bound ($C_k^n$ possibilities), and a bijection from the particles $A_i$ that are bound into the particles $B_j$ that are bound ($k!$ possibilities).

This way, if we assume that $m = n$, there are respectively 1, 8, 112, 2176, and 53504 standard states when $m$ and $n$ are both equal to, respectively, 0, 1, 2, 3, and 4. We can observe a combinatorial blow-up in the number of states, making the hand-made computation (and even the automatic computation) of the distribution of traces) not tractable.

## 2.2 A model with anonymous particles

Yet, the previous granularity of observation keeps some useless information: indeed we can abstract away agent indexes and assimilate two states that can be obtained by re-indexing particles. Doing so, we get only 8 kinds of molecular species: $A^\epsilon$, $A^*$, $B^\epsilon$, $B^*$, $A^\epsilon B^\epsilon$, $A^\epsilon B^*$, $A^* B^\epsilon$, and $A^* B^*$. Moreover a state can
now be denoted as the number of instances $[S]$ of each of these species $S$. Furthermore, we shall notice that in a state the following mass preservation equalities hold:

$$[A^\epsilon] + [A^*] + [A^\epsilon B^\epsilon] + [A^* B^\epsilon] + [A^\epsilon B^*] + [A^* B^*] = m$$

$$[B^\epsilon] + [B^*] + [A^\epsilon B^\epsilon] + [A^* B^\epsilon] + [A^\epsilon B^*] + [A^* B^*] = n.$$

More formally, we call the states of the system where particles are identified (see Sect. 2.1) the non standard states, and the states of the new system the standard states. The set of the non standard states is denoted by $\mathcal{Q}^b$ whereas the set of the standard states is denoted by $\mathcal{Q}$. Non standard states and standard states are related by an abstraction function $\beta_1$ that maps non standard state $q^b$ to the standard state $q = \beta_1(q^b)$ mapping each molecular species to its number of occurrences in $q^b$. For instance (with $m = 3$ and $n = 1$), the non standard state $A_1^\epsilon, A_2^*, A_3^\epsilon B_1^\epsilon$ is mapped to the standard state $\beta_1(A_1^\epsilon, A_2^*, A_3^\epsilon B_1^\epsilon) = [A^\epsilon \mapsto 1, A^* \mapsto 1, A^\epsilon B^\epsilon \mapsto 1, \_ \mapsto 0]$ (the underscore pattern ‘_’ matches any molecular species which is not already in the assignment).

Conversely, a standard state $q \in \mathcal{Q}$ can be concretized into a set $\gamma_1(q)$ of non standard states, which is defined as $\gamma_1(q) = \{q^b | \beta_1(q^b) = q\}$.

The number of standard states is given by the following expression:

$$\sum_k (C_1^{m-k+1} \cdot C_1^{n-k+1} \cdot C_3^{k+3} \mid k \in \mathbb{N}).$$

Indeed, the index $k$ in the sum denotes the number of complexes. There are 4 kinds of complexes, the number of combinations of $k$ complexes is given by $C_3^{k+3}$. Then there are $C_1^{m-k+1}$ possibilities for the number of activated $A$ and $C_1^{n-k+1}$ possibilities for the number of activated $B$. For instance, if we assume that $m = n$, there are respectively 1, 8, 35, 112, and 294 standard states when $m$ and $n$ are both equal to, respectively, 0, 1, 2, 3, and 4.

Two non standard states $q_1^b$ and $q_2^b$ having the same abstraction (ie such that $\beta_1(q_1^b) = \beta_1(q_2^b)$) are called equivalent. In such a case, we write $q_1^b \sim_b q_2^b$. The binary relation $\sim_b$ is indeed a binary equivalence over non standard states, moreover the equivalence class $[q^b]_{\sim_b}$ of a given non standard state $q^b$ is exactly the set $\gamma_1(\beta_1(q^b))$. We shall notice that $[q^b]_{\sim_b}$ can be seen as the image of $q^b$ by the group (with functional composition) of the pairs $(\sigma, \sigma') \in S_m \times S_n$ of index permutations that leave the standard state unchanged (ie. if we denote $q_1^b$ as a sequence of particles $A_1^{\diamond_1}, \dots, A_m^{\diamond_m}, B_1^{\diamond_1}, \dots, B_n^{\diamond_n}$ and a pairing relation $\mathcal{R} \subseteq [1, m] \times [1, n]$, then the pair $(\sigma, \sigma')$ of index permutations leaves the standard state of $q_1^b$ unchanged if, and only if, the non standard state $q_2^b$ that is defined as the sequence $A_{\sigma_1}^{\diamond_1}, \dots, A_{\sigma_m}^{\diamond_m}, B_{\sigma_1}^{\diamond_1}, \dots, B_{\sigma_n}^{\diamond_n}$ of particles and the pairing relation $\{(\sigma_i, \sigma'_j) | (i, j) \in \mathcal{R}\}$ satisfies $q_1^b \sim_b q_2^b$).

We claim<fnref n="1" /> that equivalent non standard states are equi-probable, which means that given a sequence $u$ of standard computation reactions (such as firstly activate one $A$, secondly activate one $B$, and thirdly form a complex between

<footnote n="1">¹ This claim is a consequence of Th. 5 on page 54 and Th. 3.(2) on page 27.</footnote>
one activated A and one deactivated B) and consider the set $X^b$ of sequences $u^b$ of non standard reactions which match the sequence $u$ (such as firstly activate $A_1$, secondly activate $B_2$, thirdly form a complex with $A_1$ and $B_1$), the probability $P(q_1^b | X^b)$ that the system takes a state $q_1^b$ in the non standard system knowing that we have computed a sequence of non standard reactions in $X^b$, is equal to the probability $P(q_2^b | X^b)$ that the system takes a state $q_2^b$ knowing that we have computed a sequence of non standard reactions in $X^b$, for any non standard state $q_2^b$ such that $q_1^b \sim^b q_2^b$.

As a consequence we can express the dynamic of the standard model directly by a set of reactions. These reactions are given in Fig. 3. The standard model is a sound abstraction of the non standard one, which can be formalized in the following way. Firstly we lift the abstraction $\beta_1$ to discrete traces by defining the mapping $\beta_1^\tau$ as the mapping between the set $Q^b$ of finite not empty sequences of non standard steps and the set $Q^+$ of finite not empty sequences of standard steps that is defined by $\beta_1^\tau(q_0^b, \dots, q_p^b) = \beta_1(q_0^b), \dots, \beta_1(q_p^b)$. The concretization $\gamma_1^\tau(q_0, \dots, q_p)$ of a trace $q_0, \dots, q_p$ of standard computation steps is then the set $\gamma_1(q_0) \times \dots \times \gamma_1(q_p)$ of traces of non standard computation steps (it is the unique mapping between $Q^+$ and $\wp(Q^b)$ that satisfies the property: $\beta_1^\tau(\tau^b) \in X$ if, and only if, $\tau^b \in \gamma_1^\tau(X)$, for any trace $\tau^b$ of non standard discrete computation steps and any set $X$ of traces of standard discrete computation steps).

We can now state the soundness of the standard model as follows: let us fix $p$ a number of computation steps and $q_0$ a standard state. We denotes by $\mathcal{D}(\{q_0\}, p)$ the distribution (in $Q^{p+1} \to [0, 1]$) of the discrete traces that start with the standard state $q_0$ and that contain $p$ standard computation steps. We denote by $\mathcal{D}^b(\gamma_1(q_0), p)$ the distribution (in $Q^{p+1} \to [0, 1]$) of the discrete traces that start with an initial non standard state uniformly chosen among $\gamma_1(q_0)$ and that contain $p$ non standard computation steps.

**Theorem 1.** The two distributions $\mathcal{D}^b(\gamma_1(q_0), p)$ and $\mathcal{D}(\{q_0\}, p)$ are related by the following relationship:

$$ \mathcal{D}(\{q_0\}, p)(\tau) = \sum_{\tau^b} \left( \mathcal{D}^b(\gamma_1(q_0), p)(\tau^b) \mid \tau^b \in \gamma_1^\tau(\tau) \right), $$

for any discrete trace $\tau$ that starts with the standard state $q_0$ and that contain $p$ standard computation steps.

The 1 is indeed a particular case of The. 5 which is stated and proved on page 54.

## 2.3 A model with anonymous fragments

We may wonder whether we have achieved the best granularity level. Maybe the computation of the distribution of traces can be abstracted while keeping interesting properties (such as, for instance, the number of instances of some particular molecular species).

If we were using a differential model, it would be possible to abstract away the correlation between the activation level of the particles of type A and the
$$
\begin{align*}
A^{\epsilon} \underset{k_{A-}}{\overset{k_{A+}}{\rightleftharpoons}} A^{*} \\
A^{\epsilon} B^{\epsilon} \underset{k_{A-}}{\overset{k_{A+}}{\rightleftharpoons}} A^{*} B^{\epsilon} \\
A^{\epsilon} B^{*} \underset{k_{A-}}{\overset{k_{A+}}{\rightleftharpoons}} A^{*} B^{*}
\end{align*}
$$

(a) A activation.

$$
\begin{align*}
B^{\epsilon} \underset{k_{B-}}{\overset{k_{B+}}{\rightleftharpoons}} B^{*} \\
A^{\epsilon} B^{\epsilon} \underset{k_{B-}}{\overset{k_{B+}}{\rightleftharpoons}} A^{\epsilon} B^{*} \\
A^{*} B^{\epsilon} \underset{k_{B-}}{\overset{k_{B+}}{\rightleftharpoons}} A^{*} B^{*}
\end{align*}
$$

(b) B activation.

$$
\begin{align*}
A^{\epsilon} + B^{\epsilon} \underset{k_{A..B}}{\overset{k_{A+B}}{\rightleftharpoons}} A^{\epsilon} B^{\epsilon} \\
A^{*} + B^{*} \underset{k_{A..B}}{\overset{k_{A+B}}{\rightleftharpoons}} A^{*} B^{*} \\
A^{\epsilon} + B^{*} \underset{k_{A..B}}{\overset{k_{A..B}}{\rightleftharpoons}} A^{\epsilon} B^{*} \\
A^{*} + B^{*} \underset{k_{A..B}}{\overset{k_{A*B}}{\rightleftharpoons}} A^{*} B^{*}
\end{align*}
$$

(c) AB complexation.

<caption>Fig. 3. Reactions among anonymous agents.</caption>

$$
\begin{align*}
[A'] &= k_{A-}[A^+] + k_{A..B}[A^*B^\dagger] - (k_{A+} + k_{AB}([B^+] + [B^*]))[A^*], \\
[A^*'] &= k_{A+}[A^+] + k_{A..B}[A^*B^\dagger] - (k_{A-} + k_{AB}^*[B^+] + k_{A^*,B^*}[B^*])[A^*], \\
[A^*B^\dagger'] &= k_{A-}[A^*B^\dagger] + k_{AB}^*[A^*]([B^+] + [B^*]) - (k_{A+} + k_{A..B})[A^*B^\dagger], \\
[B'] &= k_{B-}[B^+] + k_{A..B}[A^\circ B^\dagger] - (k_{B+} + k_{AB}^*[A^*] + [A^*])[B^*], \\
[B^\dagger'] &= k_{B+}[B^\epsilon] + k_{A..B}[A^\circ B^\dagger] - (k_{B-} + k_{AB}^*[A^+] + k_{A^*,B^*}[A^*])[B^*], \\
[A^\circ B^\dagger'] &= k_{B-}[A^\circ B^\dagger] + k_{AB}^*([A^+] + [A^*])[B^+] - (k_{B+} + k_{A..B})[A^\circ B^\dagger], \\
[A^\circ B^*'] &= k_{B+}[A^\circ B^\dagger] + k_{AB}^*[A^*][B^+] + k_{A^*,B^*}[A^*][B^*] - (k_{B-} + k_{A..B})[A^\circ B^*].
\end{align*}
\begin{align*}
(a) \quad & [A'] = k_{A-}[A^+] + k_{A..B}[A^*B^\dagger] - (k_{A+} + k_{AB}([B^+] + [B^*]))[A^*], \\
(b) \quad & [A^*'] = k_{A+}[A^+] + k_{A..B}[A^*B^\dagger] - (k_{A-} + k_{AB}^*[B^+] + k_{A^*,B^*}[B^*])[A^*], \\
[A^*B^\dagger'] = k_{A-}[A^*B^\dagger] + k_{AB}^*([A^+] + [A^*])[B^+] - (k_{A+} + k_{A..B})[A^*B^\dagger], \\
[B'] = k_{B-}[B^+] + k_{A..B}[A^\circ B^\dagger] - (k_{B+} + k_{AB}^*[A^*] + [A^*])[B^*], \\
[B^\dagger'] = k_{B+}[B^\epsilon] + k_{A..B}[A^\circ B^\dagger] - (k_{B-} + k_{AB}^*[A^+] + k_{A^*,B^*}[A^*])[B^*], \\
[A^\circ B^\dagger'] = k_{B-}[A^\circ B^\dagger] + k_{AB}^*([A^+] + [A^*])[B^+] - (k_{B+} + k_{A..B})[A^\circ B^\dagger], \\
[A^\circ B^*'] = k_{B+}[A^\circ B^\dagger] + k_{AB}^*[A^*][B^+] + k_{A^*,B^*}[A^*][B^*] - (k_{B-} + k_{A..B})[A^\circ B^*].
\end{align*}
$$

<figure><img src="image_3.png" /><figcaption>Fig. 4. (a) The set of differential equations. (b) The superposition of the (fragment-based) differential trajectory and one stochastic trajectory. All rates have been set to 1, except $k_{A^*B^*}$ that has been set to 2. Initial concentrations/number of instances of both $A^\epsilon$ and $B^\epsilon$ has been set to 100,000. The volume is equal to 1. The volume unit and time unit (which are also used in rates) are arbitrary. The curves display the concentration (differential trajectory) and the number of instances (stochastic trajectory) of the molecular species of the form $A^*B^\dagger$ (which is also denoted by $A(x\sim p_-)$) in Kappa [22].</figcaption></figure>

activation level of the particles of type *B* within complexes. The main reason
is that the dissociation rate does depend on neither the activation level of the
particle *A*, nor the one of the particle *B*. As a consequence the evolution of
the concentration *A*<sup>ε</sup>, *A*<sup>ε</sup>*B*<sup>δ</sup>, *A*<sup>*</sup>, *A*<sup>*</sup>*B*<sup>δ</sup>, *B*<sup>ε</sup>, *A*<sup>◇</sup>*B*<sup>ε</sup>, *B*<sup>*</sup>, *A*<sup>◇</sup>*B*<sup>*</sup> in a differential
model can be described in the self-consistent way<sup>2</sup> by the system of differential
equations that is given Fig. 4(a). In Fig. 4(b), we show the superposition of the
trajectory of the concentration (steady curve) of *A*<sup>*</sup>*B*<sup>δ</sup> in the differential model
and of the sum (wiggly curve) between the number of instances of the molec-
ular species *A*<sup>*</sup>*B*<sup>ε</sup> and the molecular species *A*<sup>*</sup>*B*<sup>*</sup> in one stochastic trajectory
obtained thanks to the stochastic simulator that is described in [19].

Doing so, we get 8 kinds of fragments: $A^\epsilon$, $A^\epsilon B^\dagger$, $A^*$, $A^* B^\dagger$, $B^\epsilon$, $A^\diamond B^\epsilon$, $B^*$, $A^\diamond B^*$ in a differential model can be described in the self-consistent way<fnref n="2" /> by the system of differential equations that is given Fig. 4(a). In Fig. 4(b), we show the superposition of the trajectory of the concentration (steady curve) of $A^*B^\dagger$ in the differential model and of the sum (wiggly curve) between the number of instances of the molecular species $A^*B^\epsilon$ and the molecular species $A^*B^*$ in one stochastic trajectory obtained thanks to the stochastic simulator that is described in [19].

<footnote n="2">² A generic framework of automatic reduction for the differential systems for the molec-
ular systems that are written in Kappa [22], is described in [28].</footnote>
each of these fragment F. Moreover, we shall notice that in a state the following equalities hold:

$$[A^\epsilon] + [A^*] + [A^\epsilon B^\diamond] + [A^* B^\diamond] = m$$

$$[B^\epsilon] + [B^*] + [A^\diamond B^\epsilon] + [A^\diamond B^*] = n$$

$$[A^\epsilon B^\diamond] + [A^* B^\diamond] = [A^\diamond B^\epsilon] + [A^\diamond B^*].$$

The first two equalities encode mass preservation laws. The third equality denotes the fact that the number of complexes $([A^\epsilon B^\epsilon] + [A^* B^\epsilon] + [A^\epsilon B^*] + [A^* B^*])$ can be written either as the number of the particles A that are bound, or equivalently as the number of the particles B that are bound.

We call abstract state of the system a function mapping all fragments F to the number $[F]$ of instances of the fragment F. The set of abstract states is denoted by $Q^\sharp$. Standard states and abstract states are related by an abstraction function $\beta_2$ that maps standard state $q$ to the standard state $q^\sharp = \beta_2(q)$ that is defined as follows:

$$\beta_2(q)(A^\epsilon) = q(A^\epsilon)$$

$$\beta_2(q)(A^\epsilon B^\diamond) = q(A^\epsilon B^\epsilon) + q(A^\epsilon B^*)$$

$$\beta_2(q)(A^*) = q(A^*)$$

$$\beta_2(q)(A^* B^\diamond) = q(A^* B^\epsilon) + q(A^* B^*)$$

$$\beta_2(q)(B^\epsilon) = q(B^\epsilon)$$

$$\beta_2(q)(A^\diamond B^\epsilon) = q(A^\epsilon B^\epsilon) + q(A^* B^\epsilon)$$

$$\beta_2(q)(B^*) = q(B^*)$$

$$\beta_2(q)(A^\diamond B^*) = q(A^\epsilon B^*) + q(A^* B^*)$$

For instance (with $m = 3$ and $n = 1$), the standard state $[A^\epsilon \mapsto 1, A^* \mapsto 1, A^\epsilon B^\epsilon \mapsto 1, \dots \mapsto 0]$ is mapped to the abstract state $[A^\epsilon \mapsto 1, A^* \mapsto 1, A^\epsilon B^\diamond \mapsto 1, A^\diamond B^\epsilon \mapsto 1, \dots \mapsto 0]$.

Conversely, an abstract state $q^\sharp \in Q^\sharp$ can be concretized into a set $\gamma_2(q^\sharp)$ of non standard states that is defined as $\gamma_2(q^\sharp) = \{q \mid \beta_2(q) = q^\sharp\}$. Two standard states $q_1$ and $q_2$ having the same abstraction (ie such that $\beta_2(q_1) = \beta_2(q_2)$) are called equivalent. In such a case, we write $q_1 \sim q_2$. The binary relation $\sim$ is indeed a binary equivalence over standard states, moreover the equivalence class $[q]_\sim$ of a given standard state $q$ is exactly the set $\gamma_2(\beta_2(q))$.

The number of abstract states is given by the following expression:

$$\sum_k ((k+1)^2 \cdot C_1^{m-k-1} \cdot C_1^{n-k-1} \mid k \in \mathbb{N}).$$

Indeed, the index $k$ in the sum denotes the number of complexes. We notice that $k$ is also both the number of particles A that are bound and the number of particles B that are bound. The number of choices for the number of the particles A that are both bound and activated is $k+1$, the number of choices for the number of the particles B that are both bound and activated is $k+1$,
the number of choices for the number of the particles A that are both free and activated is $C_1^{m-k-1}$ and the number of choices for the number of the particles B that are both free and activated is $C_1^{n-k-1}$. For instance, if we assume that $m=n$, there are respectively 1, 8, 34, 104, and 259 standard states when $m$ and $n$ are both equal to, respectively, 0, 1, 2, 3, and 4.

Now we consider two cases according to the fact that the equality $k_{A+B} = k_{A^*+B^*}$ holds, or not.

### 2.3.1 Whenever $k_{A+B} = k_{A^*+B^*}$

In the case when $k_{A+B} = k_{A^*+B^*}$, we claim<fnref n="3" /> that given two equivalent standard states $q_1$ and $q_2$, and a sequence $u^\#$ of abstract reactions (such as firstly activate one A, secondly activate one B, and thirdly form a complex between one A and one B) and considering the set $X$ of sequences $u$ of standard reactions which match the sequence $u^\#$ (such as firstly activate one A, secondly activate one B, and thirdly form a complex between one activated A and one deactivated B), then the probability $P(q_1 | X)$ that the system takes a state $q_1$ in the standard system knowing that we have computed a sequence of standard reactions in $X$ and the probability $P(q_2 | X)$ that the system takes a state $q_2$ knowing that we have computed a sequence of non standard reactions in $X$, are related by the following equation:

$$P(q_1 | X) \cdot \text{card}(\gamma_1(q_2)) = P(q_2 | X) \cdot \text{card}(\gamma_1(q_1)),$$

which amounts to say that:

$$P(q | X) = \frac{\text{card}(\gamma_1(q))}{\sum_{q'} (\text{card}(\gamma_1(q')) | q' \in \gamma_2(q^*))},$$

for any standard state $q$ such that $\beta_2(q) = q^\#$.

Now we can give a numerical example. Let us assume that $m=n$ and that $n$ is strictly greater than 1. We can compute the distribution of the standard states $q$ knowing the fact that $\beta_2(q)$ is equal to the abstract state $[A^\epsilon B^\diamond \mapsto m-1, A^*B^\diamond \mapsto 1, A^\diamond B^\epsilon \mapsto m-1, A^\diamond B^* \mapsto 1, \dots \mapsto 0]$ (we denote this later abstract state by $q^\#$). Indeed we have $\gamma_2(q^\#) = \{q_1, q_2\}$ where:

$$\begin{aligned} q_1 &= [A^\epsilon B^\epsilon \mapsto m-1, A^*B^* \mapsto 1, \dots \mapsto 0], \\ q_2 &= [A^\epsilon B^\epsilon \mapsto m-2, A^*B^\epsilon \mapsto 1, A^\epsilon B^* \mapsto 1, \dots \mapsto 0]. \end{aligned}$$

The standard state $q_1$ matches the case when the two activated particles are bound together, whereas the standard state $q_2$ matches the other case. Then, the set $\gamma_1(q_1)$ has $m^2 \cdot (m-1)! = m \cdot m!$ elements (there are $m$ choices for the particle A that is activated, $m$ choices for the particle B that is activated, and $(m-1)!$ choices for the pairing relation between deactivated A and deactivated

<footnote n="3">³ This claim is a consequence of Th. 6 on page 68 and Th. 3.(2) on page 27.</footnote>
B), whereas $\gamma_1(q_2)$ has $m^2 \cdot (m-1)^2 \cdot (m-2)! = m \cdot (m-1) \cdot m!$ elements (there are $m$ choices for the particle A that is activated, $m$ choices for the particle B that is activated, $(m-1)$ choices for the A that is both deactivated and bound to an activated B, $(m-1)$ choices for the B that is both deactivated and bound to an activated A, then there are $(m-2)!$ choices for the pairing relation between deactivated A and deactivated B). So the probability $P(q_1 | q^*)$ of being in the standard state $q_1$ knowing that we are in the abstract state $q^*$ is $\frac{1}{m}$ and the probability $P(q_2 | q^*)$ of being in the standard state $q_2$ knowing that we are in the abstract state $q^*$ is $\frac{m-1}{m}$.

We can do the same computation in the general case. Let us consider $q^\sharp$ an arbitrary abstract state and $q_1, q_2$ two standard states such that $q_1 \in \gamma_2(q^\sharp)$ and $q_2 \in \gamma_2(q^\sharp)$. The cardinal of the set $\gamma_1(q_1)$ can be factored as the product $X_A(q^\sharp) \cdot X_B(q^\sharp) \cdot X_{AB}(q_1, q^\sharp)$, where $X_A(q^\sharp)$ is the number of choices for the dispatching of the particles A along the four distinct states $A^\epsilon, A^*, A^\epsilon B^\diamond$, and $A^* B^\diamond$, $X_B(q^\sharp)$ is the number of choices for the dispatching of the particles B along the four distinct states $B^\epsilon, B^*, A^\diamond B^\epsilon$, and $A^\diamond B^*, A^* B^\diamond$, and $X_{AB}(q_1, q^\sharp)$ is the number of pairing relations between particles A in the state $A^\epsilon B^\diamond$ or $A^* B^\diamond$, and the particles B in the state $A^\diamond B^\epsilon$ or $A^\diamond B^*$. More precisely, the number $X_A(q^\sharp)$ of choices for the state of the particles A is obtained by counting the number of ways $C_3^{q^\sharp(A^\epsilon)+q^\sharp(A^*)+q^\sharp(A^\epsilon B^\diamond)+q^\sharp(A^* B^\diamond)+3}$ of dispatching the $q^\sharp(A^\epsilon) + q^\sharp(A^*) + q^\sharp(A^\epsilon B^\diamond) + q^\sharp(A^* B^\diamond)$ available particles A into the fourth instantiations $A^\epsilon, A^*, A^\epsilon B^\diamond$, and $A^* B^\diamond$. The same way, the number $X_B(q^\sharp)$ is equal to: $C_3^{q^\sharp(B^\epsilon)+q^\sharp(B^*)+q^\sharp(A^\diamond B^\epsilon)+q^\sharp(A^\diamond B^*)+3}$. Then, a pairing relation between the particles A that are bound, and the particles B that are bound is obtained by choosing: (i) within the particles A in the state $A^\epsilon B^\diamond$ the $q_1(A^\epsilon B^\epsilon)$ particles which are bound to a particle B in the state $A^\diamond B^\epsilon$ (there are $C_{q_1(A^\epsilon B^\epsilon)}^{q^\sharp(A^\epsilon B^\diamond)}$ possibilities); (ii) within the particles A in the state $A^* B^\diamond$ the $q_1(A^* B^*)$ particles which are bound to a particle B in the state $A^\diamond B^*$ (there are $C_{q_1(A^* B^*)}^{q^\sharp(A^* B^\diamond)}$ possibilities); (iii) within the particles B in the state $A^\diamond B^\epsilon$ the $q_1(A^\epsilon B^\epsilon)$ particles which are bound to a particle A in the state $A^\epsilon B^\diamond$ (there are $C_{q_1(A^\epsilon B^\epsilon)}^{q^\sharp(A^\diamond B^\epsilon)}$ possibilities); (iv) within the particles B in the state $A^\diamond B^*$ the $q_1(A^* B^*)$ particles which are bound to a particle A in the state $A^* B^\diamond$ (there are $C_{q_1(A^* B^*)}^{q^\sharp(A^* B^\diamond)}$ possibilities); (v) the pairing relation to form the complexes $A^\epsilon B^\epsilon$ (there are $(q_1(A^\epsilon.B^\epsilon))!$ possibilities); (vi) the pairing relation to form the complexes $A^* B^\epsilon$ (there are $(q_1(A^*.B^\epsilon))!$ possibilities); (vii) the pairing relation to form the complexes $A^\epsilon B^*$ (there are $(q_1(A^*.B^*))!$ possibilities); (viii) the pairing relation to form the complexes $A^* B^*$ (there are $(q_1(A^*.B^*))!$ possibilities).

By using the following equalities,

$$q^\sharp(A^\diamond B^\epsilon) = q_1(A^\epsilon B^\epsilon) + q_1(A^* B^\epsilon),$$

$$q^\sharp(A^\epsilon B^\diamond) = q_1(A^\epsilon B^\epsilon) + q_1(A^* B^\epsilon),$$

$$q^\sharp(A^\diamond B^*) = q_1(A^\epsilon B^*) + q_1(A^* B^*),$$

$$q^\sharp(A^* B^\diamond) = q_1(A^* B^\epsilon) + q_1(A^* B^*),$$
$$ \begin{gathered} A^{\epsilon} \underset{k_{A-}}{\overset{k_{A+}}{\rightleftharpoons}} A^{*} \\ A^{\epsilon} B^{\diamond} \underset{k_{A-}}{\overset{k_{A+}}{\rightleftharpoons}} A^{*} B^{\diamond} \end{gathered} $$

(a) A activation.

$$ \begin{gathered} B^{\epsilon} \underset{k_{B-}}{\overset{k_{B+}}{\rightleftharpoons}} B^{*} \\ A^{\diamond} B^{\epsilon} \underset{k_{B-}}{\overset{k_{B+}}{\rightleftharpoons}} A^{\diamond} B^{*} \end{gathered} $$

(b) B activation.

$$ \begin{gathered} A^{\epsilon} + B^{\epsilon} \underset{k_{A+B}}{\overset{k_{A+B}}{\rightleftharpoons}} A^{\epsilon} B^{\diamond} + A^{\diamond} B^{\epsilon} \\ A^{*} + B^{\epsilon} \underset{k_{A+B}}{\overset{k_{A+B}}{\rightleftharpoons}} A^{*} B^{\diamond} + A^{\diamond} B^{\epsilon} \\ A^{\epsilon} + B^{*} \underset{k_{A+B}}{\overset{k_{A+B}}{\rightleftharpoons}} A^{\epsilon} B^{\diamond} + A^{\diamond} B^{*} \\ A^{*} + B^{*} \underset{k_{A^{*}+B^{*}}}{\overset{k_{A^{*}+B^{*}}}{\rightleftharpoons}} A^{*} B^{\diamond} + A^{\diamond} B^{*} \end{gathered} $$

(c) AB complexation.

$$ \begin{gathered} A^{\epsilon} B^{\diamond} + A^{\diamond} B^{\epsilon} \underset{k_{A..B}/[A^{\diamond} B^{\diamond}]}{\overset{k_{A..B}/[A^{\diamond} B^{\diamond}]}{\rightleftharpoons}} A^{\epsilon} + B^{\epsilon} \\ A^{*} B^{\diamond} + A^{\diamond} B^{\epsilon} \underset{k_{A..B}/[A^{\diamond} B^{\diamond}]}{\overset{k_{A..B}/[A^{\diamond} B^{\diamond}]}{\rightleftharpoons}} A^{*} + B^{\epsilon} \\ A^{\epsilon} B^{\diamond} + A^{\diamond} B^{*} \underset{k_{A..B}/[A^{\diamond} B^{\diamond}]}{\overset{k_{A..B}/[A^{\diamond} B^{\diamond}]}{\rightleftharpoons}} A^{\epsilon} + B^{*} \\ A^{*} B^{\diamond} + A^{\diamond} B^{*} \underset{k_{A..B}/[A^{\diamond} B^{\diamond}]}{\overset{k_{A..B}/[A^{\diamond} B^{\diamond}]}{\rightleftharpoons}} A^{*} + B^{*} \end{gathered} $$

(d) AB dissociation.

<caption>Fig. 5. Reactions among anonymous fragments.</caption>

we get:

$$ \mathcal{X}_{AB}(q_1, q^\sharp) = \frac{(q^\sharp(A^{\diamond B^\epsilon}))! \cdot (q^\sharp(A^{\diamond B^*}))! \cdot (q^\sharp(A^\epsilon B^\diamond))! \cdot (q^\sharp(A^* B^\diamond))!}{(q_1(A^* B^\epsilon))! \cdot (q_1(A^\epsilon B^\epsilon))! \cdot (q_1(A^* B^\epsilon))! \cdot (q_1(A^\epsilon B^\epsilon))!} $$

Thus, after simplification, we can conclude that:

$$ \begin{aligned} & \text{card}(\gamma_1(q_1)) \cdot (q_1(A^\epsilon B^\epsilon))! \cdot (q_1(A^* B^*))! \cdot (q_1(A^* B^\epsilon))! \cdot (q_1(A^* B^*))! \\ & = \text{card}(\gamma_1(q_2)) \cdot (q_2(A^\epsilon B^\epsilon))! \cdot (q_2(A^* B^*))! \cdot (q_2(A^* B^\epsilon))! \cdot (q_2(A^* B^*))!. \end{aligned} $$

We can check with our previous example. We recall that we have taken $q_1(A^\epsilon B^\epsilon) = m - 1$, $q_1(A^* B^*) = 1$ and $q_1(A^\epsilon B^*) = q_1(A^* B^\epsilon) = 0$; moreover, we have $q_2(A^\epsilon B^\epsilon) = m - 2$, $q_2(A^* B^\epsilon) = q_2(A^* B^*) = 1$, and $q_2(A^* B^*) = 0$. Last, we have card $(\gamma_1(q_1)) = m \cdot m!$ and card $(\gamma_1(q_2)) = m \cdot (m - 1) \cdot m!$. Thus we can compute that:

$$ \begin{aligned} & \text{card}(\gamma_1(q_1)) \cdot (q_1(A^\epsilon B^\epsilon))! \cdot (q_1(A^* B^*))! \cdot (q_1(A^* B^\epsilon))! \cdot (q_1(A^* B^*))! \\ & = (m \cdot m!) \cdot (m - 1)! \cdot 0! \cdot 0! \cdot 1! \\ & = (m \cdot (m - 1) \cdot m!) \cdot (m - 2)! \cdot 1! \cdot 1! \cdot 0! \\ & = \text{card}(\gamma_1(q_2)) \cdot (q_2(A^\epsilon B^\epsilon))! \cdot (q_2(A^* B^*))! \cdot (q_2(A^* B^\epsilon))! \cdot (q_2(A^* B^*))!. \end{aligned} $$

This invariant allows us to express the dynamic of the system at the level of fragments (in the case where $k_{A+B} = k_{A^*+B^*}$): the dynamic of the abstract system is given by the reactions in Fig. 5. Activation, deactivation, and complexation reactions are quite straight-forward. The interesting reactions are the one for dissociation (see Fig. 5(d)). The notation $[A^{\diamond} B^{\diamond}]$ denote the number of complexes (whatever the energy levels are).

Now we justify the reactions in Fig. 5(d). Let us assume that the system is in a given abstract state $q^\sharp$. We consider the distribution of the standard states
$q \in \gamma_2(q^\sharp)$ that is given as follows:

$$P(q | \beta_2(q) = q^\sharp) = \frac{\mathrm{card}(\gamma_1(q))}{\sum_{q'} (\mathrm{card}(\gamma_1(q')) | q' \in \gamma_2(q^\sharp))}.$$

Whatever the state $q \in \gamma_2(q^\sharp)$, the overall activity of dissociation reactions when the system is in the standard state $q$ is given by $k_{A..B} \cdot (q(A^e B^e) + q(A^e B^*) + q(A^* B^e) + q(A^* B^*))$. This activity can also be written as $k_{A..B} \cdot (q^\sharp(A^e B^\diamond) + q^\sharp(A^* B^\diamond))$. So we can faithfully compute the probability that the next reaction is a dissociation knowing that the system is in the abstract state $q^\sharp$.

Yet computing a dissociation reaction modifies both a particle A and a particle B. Given the facts that the abstract state of the system is $q^\sharp$ and that the next reaction is a dissociation, the probability $\mathcal{P}$ that this reaction modifies two activated particles is given as follows:

$$\mathcal{P} = \sum_q \left( \frac{q(A^*B^*) \cdot P(q | \beta_2(q) = q^\sharp)}{q(A^e B^e) + q(A^e B^*) + q(A^* B^e) + q(A^* B^*)} \middle| q \in \gamma_2(q^\sharp) \right).$$

Since, for any $q \in \gamma_2(q^\sharp)$, the expression $q(A^e B^e) + q(A^e B^*) + q(A^* B^e) + q(A^* B^*)$ is equal to the expression $q^\sharp(A^e B^\diamond) + q^\sharp(A^* B^\diamond)$, it follows that:

$$\mathcal{P} = \sum_q \left( \frac{q(A^*B^*) \cdot P(q | \beta_2(q) = q^\sharp)}{q^\sharp(A^e B^\diamond) + q^\sharp(A^* B^\diamond)} \middle| q \in \gamma_2(q^\sharp) \right).$$

Then:

$$\mathcal{P} = \frac{\sum_q (q(A^*B^*) \cdot \mathrm{card}(\gamma_1(q)) | q \in \gamma_2(q^\sharp))}{(q^\sharp(A^e B^\diamond) + q^\sharp(A^* B^\diamond)) \cdot \sum_{q'} (\mathrm{card}(\gamma_1(q')) | q' \in \gamma_2(q^\sharp))}.$$

Given $q^b$ a non standard state and $i, j$ two indexes (such that $1 \le i \le m$ and $1 \le j \le n$), we define $f(i, j, q^b)$ as 1 if the state $q^b$ contains a complex $A_i^* B_j^*$, and 0 otherwise; we also define $g(i, j, q^b)$ as 1 if the particle $A_i$ and the particle $B_j$ are bound together in the non standard state $q^b$. By scanning the set $\gamma_1(q)$ and the combinations $A_i/B_j$ of particles, we have:

$$\mathcal{P} = \frac{\sum_{q^b} \sum_i \sum_j (f(i, j, q^b) \mid q^b \in \gamma_1(\gamma_2(q^\sharp)), 1 \le i \le m, 1 \le j \le n)}{\sum_{q^b} \sum_i \sum_j (g(i, j, q^b) \mid q^b \in \gamma_1(\gamma_2(q^\sharp)), 1 \le i \le m, 1 \le j \le n)}.$$

Having fixed $i$ and $j$, the sum

$$N(i, j) = \sum_{q^b} (f(i, j, q^b) \mid q^b \in \gamma_1(\gamma_2(q^\sharp)))$$

is exactly the number of non standard states $q^b$ such that $q^b \in \gamma_1(\gamma_2(q^\sharp))$ and the complex $A_i^* B_j^*$ belongs to $q^b$; moreover, the sum

$$D(i, j) = \sum_{q^b} (g(i, j, q^b) \mid q^b \in \gamma_1(\gamma_2(q^\sharp)))$$
is exactly the number of non standard states $q^b$ such that $q^b \in \gamma_1(\gamma_2(q^\sharp))$ and the particle $A_i$ and the particle $B_j$ are bound together in the non standard state $q^b$. Thus, we have:

$$N(i, j) = \alpha \cdot C_{q^\sharp(A^*B^\diamond)}^{q^\sharp(A^\epsilon B^\diamond)+q^\sharp(A^*B^\diamond)-1} \cdot C_{q^\sharp(A^\diamond B^\star)-1}^{q^\sharp(A^\diamond B^\epsilon)+q^\sharp(A^\diamond B^\star)-1}$$

and:

$$D(i, j) = \alpha \cdot C_{q^\sharp(A^*B^\diamond)}^{q^\sharp(A^\epsilon B^\diamond)+q^\sharp(A^*B^\diamond)} \cdot C_{q^\sharp(A^\diamond B^\star)}^{q^\sharp(A^\diamond B^\epsilon)+q^\sharp(A^\diamond B^\star)},$$

where:

$$\alpha = C_{q^\sharp(A^\epsilon)}^{m-1} \cdot C_{q^\sharp(A^*)}^{m-1-q^\sharp(A^\epsilon)} \cdot C_{q^\sharp(B^\epsilon)}^{n-1} \cdot C_{q^\sharp(B^\star)}^{n-1-q^\sharp(B^\epsilon)} \cdot (q^\sharp(A^\epsilon B^\diamond) + q^\sharp(A^*B^\diamond) - 1)!$$

Let us first explain the computation of $N(i, j)$: knowing that $A_i$ is activated, $B_j$ is activated, and that $A_i$ and $B_j$ are bound together, it remains $C_{q^\sharp(A^\epsilon)}^{m-1}$ possibilities for the particles $A$ that are deactivated and not bound, then it remains $C_{q^\sharp(A^*)}^{m-1-q^\sharp(A^\epsilon)}$ possibilities for the particles $A$ that are activated and not bound; we obtain the factors $C_{q^\sharp(B^\epsilon)}^{n-1}$ and $C_{q^\sharp(B^\star)}^{n-1-q^\sharp(B^\epsilon)}$ as the number of possibilities for the particles $B$ that are not bound; then we have $C_{q^\sharp(A^*B^\diamond)-1}^{q^\sharp(A^\epsilon B^\diamond)+q^\sharp(A^*B^\diamond)-1}$ possibilities for the particle $A$ that are both bound and activated (since we already know that the particle $A_i$ is necessarily bound and activated) and $C_{q^\sharp(A^\diamond B^\star)-1}^{q^\sharp(A^\diamond B^\epsilon)+q^\sharp(A^\diamond B^\star)-1}$ possibilities for the particle $B$ that are both bound and activated; last, the factor $(q^\sharp(A^\epsilon B^\diamond)+q^\sharp(A^*B^\diamond)-1)!$ denotes the number of potential pairing relations (since we already know that the particle $A_i$ is bound to the particle $B_j$).

Let us then explain the computation of $D(i, j)$: knowing that $A_i$ and $B_j$ are bound together, it remains $C_{q^\sharp(A^\epsilon)}^{m-1}$ possibilities for the particles $A$ that are deactivated and not bound, then it remains $C_{q^\sharp(A^*)}^{m-1-q^\sharp(A^\epsilon)}$ possibilities for the particles $A$ that are activated and not bound; we obtain the factors $C_{q^\sharp(B^\epsilon)}^{n-1}$ and $C_{q^\sharp(B^\star)}^{n-1-q^\sharp(B^\epsilon)}$ as the number of possibilities for the particles $B$ that are not bound; then we have $C_{q^\sharp(A^*B^\diamond)+q^\sharp(A^*B^\diamond)}^{q^\sharp(A^\epsilon B^\diamond)+q^\sharp(A^*B^\diamond)}$ possibilities for the particle $A$ that are both bound and activated and $C_{q^\sharp(A^\diamond B^\star)+q^\sharp(A^\diamond B^\star)}^{q^\sharp(A^\diamond B^\epsilon)+q^\sharp(A^\diamond B^\star)}$ possibilities for the particle $B$ that are both bound and activated; last, the factor $(q^\sharp(A^\epsilon B^\diamond)+q^\sharp(A^*B^\diamond)-1)!$ denotes the number of potential pairing relations (since we already know that the particle $A_i$ is bound to the particle $B_j$).

Thus, the probability $\mathcal{P}$ is equal to the following expression:

$$\frac{\sum_i \sum_j \left( \alpha \cdot C_{q^\sharp(A^*B^\diamond)}^{q^\sharp(A^\epsilon B^\diamond)+q^\sharp(A^*B^\diamond)-1} \cdot C_{q^\sharp(A^\diamond B^\star)-1}^{q^\sharp(A^\diamond B^\epsilon)+q^\sharp(A^\diamond B^\star)-1} \middle| \begin{array}{l} 1 \le i \le m, \\ 1 \le j \le n \end{array} \right)}{\sum_i \sum_j \left( \alpha \cdot C_{q^\sharp(A^*B^\diamond)}^{q^\sharp(A^\epsilon B^\diamond)+q^\sharp(A^*B^\diamond)} \cdot C_{q^\sharp(A^\diamond B^\star)}^{q^\sharp(A^\diamond B^\epsilon)+q^\sharp(A^\diamond B^\star)} \middle| \begin{array}{l} 1 \le i \le m, \\ 1 \le j \le n \end{array} \right)}$$

We can simplify by $m \cdot n \cdot \alpha$ and get:

$$\mathcal{P} = \frac{q^{\sharp}(A^{*}B^{\diamond}) \cdot q^{\sharp}(A^{\diamond B^{*}})}{(q^{\sharp}(A^{\epsilon}B^{\diamond}) + q^{\sharp}(A^{*}B^{\diamond})) \cdot (q^{\sharp}(A^{\diamond B^{\epsilon}}) + q^{\sharp}(A^{\diamond B^{*})))}.$$
Then the activity of the dissociation of activated A and activated B is equal to:

$$ \frac{k_{A..B} \cdot q^{\#}(A^{\star}B^{\diamond}) \cdot q^{\#}(A^{\diamond}B^{\star})}{(q^{\#}(A^{\diamond}B^{\epsilon}) + q^{\#}(A^{\diamond}B^{\star}))} $$

We can easily do the same computation for the three other dissociation cases.

The abstract model is a sound abstraction of the standard one, which can be formalized in the following way. Firstly we lift the abstraction $\beta_2$ to discrete traces by defining the mapping $\beta_2^\tau$ as the mapping between the set $Q^+$ of finite not empty sequences of standard computation steps and the set $Q^{\#+}$ of finite not empty sequences of abstract computation steps that is defined by:

$$ \beta_2^{\tau}(q_0, \dots, q_p) = \beta_2(q_0), \dots, \beta_p(q_p). $$

The concretization $\gamma_2^\tau(q_0^\# , \dots, q_p^\#)$ of a trace $q_0^\# , \dots, q_p^\#$ of abstract computation steps is then the set $\gamma_2(q_0^\#) \times \dots \times \gamma_2(q_p^\#)$ of traces of standard computation steps (it is the unique mapping between $Q^{\#+}$ and $\wp(Q^+)$ that satisfies the property: $\beta_2^\tau(\tau) \in X^\#$ if, and only if, $\tau \in \gamma_2^\tau(X^\#)$, for any trace $\tau$ of standard discrete computation steps and any set $X^\#$ of traces of abstract discrete computation steps).

We can now state the soundness of the abstract model: let us fix $p$ a number of computation steps and $q_0^\#$ an abstract state. We denotes by $D^\#(\{q_0^\#\}, p)$ the distribution (in $Q^{\#p+1} \to [0, 1]$) of the traces that start with the abstract state $q_0^\#$ and that contain $p$ abstract discrete computation steps. We denote by $D(\gamma_2(q_0^\#), p)$ the distribution (in $Q^{p+1} \to [0, 1]$) of the traces that start with an initial standard state according to the following distribution:

$$ P(q_0 | t = 0) = \begin{cases} \frac{\text{card}(\gamma_1(q_0))}{\sum_{q'} (\text{card}(\gamma_1(q')) | q' \in \gamma_2(q_0))} & \text{if } q_0 \in \gamma_2(q_0^\#) \\ 0 & \text{otherwise;} \end{cases} $$

and that contain $p$ non standard discrete computation steps.

**Theorem 2.** The two distributions $D(\gamma_1(q_0^\#), p)$ and $D^\#(\{q_0^\#\}, p)$ are related by the following relationship:

$$ D^\#(\{q_0^\#\}, p)(\tau^\#) = \sum_{\tau} \left( D(\gamma_2(q_0^\#), p)(q_0, \dots, q_p) \mid \tau \in \gamma_2^\tau(\tau^\#) \right), $$

for any discrete trace $\tau^\#$ that starts with the abstract state $q_0^\#$ and that contains $p$ abstract discrete computation steps.

The. 2 is indeed a particular case of The. 6 which is stated and proved on page 68.

**Remark 1.** We shall remark that the strong lumpability criterion that is described in [7] cannot be applied here. Indeed there exist some equivalent standard states $q_1, q_2$ such that $q_1 \sim q_2$ and one abstract state $q^\#$ such that the
by the system. That is to say, the conditional expectation of the number of complexes A\*B\* knowing the abstract final state q\# and the sequence of abstract reactions that have been computed starting from the initial state should not depend on the sequence of abstract reactions.

We show that this is impossible whenever $k_{A+B} \neq k_{A^*+B^*}$. For that purpose, we provide an abstract state $q^\#$, two sets $X^\#$ and $X^{\#'}$ of sequences of abstract reactions (we assume that the sequences in $X^\#$ have the same size $k$ and the sequences in $X^{\#'}$ have the same size $k'$) such that the conditional expectation $E(A^*B^* | X^\# \wedge q^\#)$ of the number of complexes of the form $A^*B^*$ after having computed a sequence $u$ of standard reactions, that matches with one element $u^\#$ in $X^\#$ (starting from the initial state), and the conditional expectation $E(A^*B^* | X^{\#'} \wedge q^\#)$ of the number of complexes of the form $A^*B^*$ after having computed a sequence $u'$ of standard reactions, that matches with one element $u^{\#'}$ in $X^{\#'}$ (starting from the initial state) satisfy:

$$E(A^*B^* | X^\# \wedge q^\#) \neq E(A^*B^* | X^{\#'} \wedge q^\#).$$

For instance, let us take:

- $m = n = 2$;

- $X^\#$ is the set of sequences of abstract reactions that apply first an activation of a particle of type A, then an activation of a particle of type B, then two consecutive complexations;

- $X^{\#'}$ is the set of sequences of abstract reactions that apply first a complexation, then an activation of a particle of type A, then an activation of a particle of type B, then a complexation.

After having computed a sequence $u$ of standard reactions, that matches an element in $X^\#$ or in $X^{\#'}$, the system can take the following two standard states:

- $q_1 = [A^\epsilon B^\epsilon \mapsto 1, A^*B^* \mapsto 1, \dots \mapsto 0]$;

- $q_2 = [A^\epsilon B^* \mapsto 1, A^*B^\epsilon \mapsto 1, \dots \mapsto 0]$.

The states $q_1$ and $q_2$ have the same abstraction $q^\# = [A^\epsilon B^\bullet \mapsto 1, A^*B^\bullet \mapsto 1, A^\diamond B^* \mapsto 1, A^\diamond B^\epsilon \mapsto 1, \dots \mapsto 0]$. Moreover, the distribution of the standard states after having computed a sequence $u$ of standard reactions, that matches with an element in $X^\#$ is given in Fig. 6(a), whereas the distribution of the standard states after having computed a sequence $u$ of standard reactions, that matches with an element in $X^{\#'}$ is given in Fig. 6(b).

Thus we have:

$$E(A^*B^* | X^\# \wedge q^\#) = \frac{k_{A^*+B^*} + k_{A+B}}{k_{A^*+B^*} + 3 \cdot k_{A+B}} \neq \frac{1}{2} = E(A^*B^* | X^{\#'} \wedge q^\#)$$

which prevents us from faithfully lifting the stochastic semantics in the abstract.
<figure><img src="image_4.png" /><figcaption>**Fig. 7.** In Fig. 7(a), for $m = n = 2$ and parameter setup $k_{A+} = 2, k_{A-} = 2, k_{B+} = 2, k_{B-} = 2, k_{A+B} = 2, k_{A*B} = 2, k_{A..B} = 2$, we plot the probability distribution over all standard states $\mathcal{D}(\{q_0\}, q)$ (first from the top), the correct probability distribution over the abstract states: $\sum_q \{\mathcal{D}(\{q_0\}, q) \mid q \in \mathcal{Q} \text{ s.t. } \beta_2(q) = q^\sharp\}$ (second from the top), the probability distribution over abstract states computed directly on the fragments: $\mathcal{D}^\sharp(\{q_0\}, q^\sharp)$ (third from the top), and the difference between the latter two: $\mathcal{D}^\sharp(\{q_0\}, q^\sharp) - \sum_q \{\mathcal{D}(\{q_0\}, q) \mid q \in \mathcal{Q} \text{ s.t. } \beta_2(q) = q^\sharp\}$ (forth from the top). In practice, the error in Fig. 7(a) is in order of the applied absolute error tolerance of the numerical integration, chosen to be the precision of floating point arithmetic in this case (i.e., $10^{-16}$). In Fig. 7(b), we plot the same functions, with a change of value of parameter $k_{A*B}$ to 5.</figcaption></figure>

### 2.3.3 Experiment

We confirm the theoretical findings by an experiment: we discuss whether simulating the system on standard and abstract states will give us sound results, depending whether $k_{A+B} = k_{A*B}$ is satisfied or not. The soundness is checked as the property that the transient probability distribution of each abstract state equals the sum of probabilities of the corresponding standard states. The experiment is performed as following: (1) we compute the reachable configurations (states) of the process, build the infinitesimal generator matrix, and solve the Markov chain for the rule set defined on standard states. This gives us the transient probability profile of each of the reachable *standard* states; (2) Analogously, we compute the reachable abstract configurations, derive the generator matrix from the rule set given on the fragments, and compute the probability profile of each of the reachable *abstract* states. (3) Finally, for any abstract state $q^\sharp$, we find all its concretization states, and we compare the distributions of $q^\sharp$ computed directly on fragments, with the sum of distributions of all concrete states $q, \beta_2(q) = q^\sharp$. We plot the difference of these two distributions over time.

In Fig. 7(a), we observe no error when computing the distributions directly in the abstract. On the other hand, in Figure 7(b), we see that change of parameter $k_{A+B}$ to be different than $k_{A+B}$ causes the violation of soundness of the stochastic fragmentation: for some abstract states, the probability distribution computed on fragments will not be correct.
# 3 Abstraction of weighted labeled transition systems

As we have noticed in Sect. 2, it is sometimes possible to abstract the stochastic semantics of a given set of reactions, by tuning the level of granularity in the observation of the system behavior. Before explaining how do make these abstractions in the context of rule-based models, we introduce a generic framework for designing and combining abstractions for the semantics of stochastic systems.

## 3.1 Syntax

We first introduce the notion of weighted labeled transition system.

Roughly speaking, a weighted labeled transition system is given by a set of states and by some transition steps. Some particular states are considered as initial. Moreover, each transition step is annotated by a label and a weight. The label is used for identifying the computation step. The weight denotes the rate of the transition; this rate allows the definition of both the relative probability of triggering the computation step and the date when the transition step is going to occur.

More formally, a weighted labeled transition system is defined as follows:

**Definition 1.** A weighted labeled transition system is a tuple $(Q, \mathcal{L}, \rightarrow, w, \mathcal{I}, \pi_0)$ where:

- $Q$ is a set of states,

- $\mathcal{L}$ is a set of labels,

- $\rightarrow \subseteq Q \times \mathcal{L} \times Q$ is a relation,

- $w$ is a mapping between $Q \times \mathcal{L}$ and $\mathbb{R}^+$,

- $\mathcal{I} \subseteq Q$ is a finite subset of states,

- $\pi_0 : \mathcal{I} \rightarrow [0, 1]$ is discrete probability distribution.

Let us now consider $(Q, \mathcal{L}, \rightarrow, w, \mathcal{I}, \pi_0)$ a weighted labeled transition system. A state $q \in \mathcal{I}$ is called an initial state. Moreover, the probability that the system is in the state $q \in \mathcal{I}$ at time $t = 0$ is equal to $\pi_0(q)$. An element $(q, \lambda, q') \in \rightarrow$ denotes a transition from state $q$ to state $q'$; the symbol $\lambda$ is the label of the transition. We denote by $q \xrightarrow{\lambda} q'$ the fact that the tuple $(q, \lambda, q')$ belongs to $\rightarrow$. In the following we will assume that a label fully identifies$^4$ a transition step. That is to say that given a label $\lambda \in \mathcal{L}$, and four states $q_1, q_2, q'_1, q'_2 \in Q$ such that $q_1 \xrightarrow{\lambda} q'_1$ and $q_2 \xrightarrow{\lambda} q'_2$, then we have $q_1 = q_2$ and $q'_1 = q'_2$ (this is always possible even if it means to put more information within the label). We denote by $\mathcal{L}(q) \subseteq \mathcal{L}$ the set of labels for which there exists $q' \in Q$ such that $q \xrightarrow{\lambda} q'$. Moreover, we also assume that the system is finitely branching, that is to say that given a state $q$, the set $\mathcal{L}(q)$ is finite. The function $w$ associates each transition $q \xrightarrow{\lambda} q'$ to its weight (or rate) $w(q, \lambda) \in \mathbb{R}^+$.

<footnote>$^4$ We use labels as a proof that a transition occurs rather than an observation about the computation of the system [4].</footnote>
## 3.2 Semantics

Now we define a continuous-time semantics for weighted labeled transition system. This semantics is defined as a probability density distribution of the traces with $k$ steps, for any natural number $k \in \mathbb{N}$.

Before defining the notion of a trace, we define the activity of the system.

**Definition 2 (activity).** Given a state $q \in \mathcal{Q}$, we define the activity $a(q)$ of the system at state $q$ by:

$$a(q) = \sum_{\lambda} (w(q, \lambda) | \lambda \in \mathcal{L}(q)).$$

**Definition 3 (trace).** A finite trace is given by an initial state $q_0 \in \mathcal{I}$ and a finite sequence $(\lambda_i, t_i, q_i)_{1 \le i \le k} \in (\mathcal{L} \times \mathbb{R}^+ \times \mathcal{Q})^k$ of triples such that: for any $i$ such that $1 \le i \le k$, we have $q_{i-1} \xrightarrow{\lambda_i} q_i$.

Such a trace is denoted as:

$$q_0 \xrightarrow{\lambda_1, t_1} q_1 \cdots q_{k-1} \xrightarrow{\lambda_k, t_k} q_k.$$

The non negative real number $t_i$ denotes the amount of time between the i-th transition of the system and the previous one (whenever $i > 1$), or between the i-th transition and time $t = 0$ (whenever $i = 1$). Moreover, the number of transitions (here $k$) is called the size of the trace.

Now we define the probability density distribution of the traces of size $k$, for any natural number $k \in \mathbb{N}$. For that purpose, we introduce as follows a generative family of measurable sets that we call the basic sets of traces. A basic set of traces is obtained by selecting an initial state and successive transitions, and by restricting the waiting times between each transition within some given intervals. For that purpose, we introduce $\mathbb{R}^+$ as the set of intervals of positive real numbers. Thus we get the following definition:

**Definition 4 (basic set of traces).** Given a natural number $k \in \mathbb{N}$, an initial state $q_0 \in \mathcal{I}$ and a sequence $(\lambda_i, I_i, q_i)_{1 \le i \le k} \in (\mathcal{L} \times \mathbb{R}^+ \times \mathcal{Q})^k$ of tuples, the set of traces that is defined as follows:

$$q_0 \xrightarrow{\lambda_1, I_1} q_1 \cdots q_{k-1} \xrightarrow{\lambda_k, I_k} q_k := \{ q_0 \xrightarrow{\lambda_1, t_1} q_1 \cdots q_{k-1} \xrightarrow{\lambda_k, t_k} q_k \mid t_i \in I_i \}.$$

is called a basic set of traces.

We denote by $\mathcal{T}_{\mathbb{R}^+}$ the set of all basic sets $\tau$ of traces. With an abuse of notation, for any natural number $k \in \mathbb{N}$ and any basic set of traces $\tau := q_0 \xrightarrow{\lambda_1, I_1} q_1 \cdots q_{k-1} \xrightarrow{\lambda_k, I_k} q_k$ in $\mathcal{T}_{\mathbb{R}^+}$ of size $k$, we denote by $\text{state}_l(\tau)$ the state $q_l \in \mathcal{Q}$ and $\text{pref}_l(\tau)$ the basic set of traces $q_0 \xrightarrow{\lambda_1, I_1} q_1 \cdots q_{l-1} \xrightarrow{\lambda_l, I_l} q_l$ of size $l$ for any integer $l$ such that $0 \le l \le k$.

Now we define the probability of such a set of traces. For that purpose, we consider that initial states are selected according to the distribution $\pi_0$. Moreover, whenever the system is in the state $q$, the next state is selected by computing the transition labeled with $\lambda \in \mathcal{L}(q)$ with probability $\frac{w(q, \lambda)}{a(q)}$ and the waiting
time until a next reaction happens is chosen according an exponential probability distribution with the parameter that is equal to the activity a(q) of the system.

**Definition 5 (trace density distribution).** Let k be a natural number in $\mathbb{N}$. The probability that a trace of size k lies in the following basic set of traces:

$$q_0 \xrightarrow{\lambda_1, I_1} q_1 \dots q_{k-1} \xrightarrow{\lambda_k, I_k} q_k$$

is given as follows:

$$\pi_0(q_0) \cdot \prod_i \left( \frac{w(q_{i-1}, \lambda_i) \cdot (e^{-a(q_{i-1}) \cdot \inf(I_i)} - e^{-a(q_{i-1}) \cdot \sup(I_i)})}{a(q_{i-1})} \middle| 1 \le i \le k \right).$$

For any natural number $k \in \mathbb{N}$, the set of measurable sets of traces of size k is obtained as the closure of basic measurable sets of traces of size k by countable union<fnref n="5" /> and complementing. This set is also closed with respect to finite meet. Moreover, it is also possible to express the distribution of states at a given time t as the limit of a well chosen sequence of linear combinations of probabilities of measurable sets of traces (of different sizes).

## 3.3 Abstraction

The description of a system can be less or more fine grained, which leads to the notion of abstraction.

### 3.3.1 Definition

We formalize the notion of abstraction between weighted labeled transition systems.

**Definition 6 (abstraction).** An abstraction is a tuple $(S, S^{\sharp}, \beta^{\mathcal{L}}, \beta^{\mathcal{Q}}, \gamma^{\mathcal{Q}})$ where $S = (Q, \mathcal{L}, \rightarrow, w, \mathcal{I}, \pi_0)$ and $S^{\sharp} = (Q^{\sharp}, \mathcal{L}^{\sharp}, \rightsquigarrow, w^{\sharp}, \mathcal{I}^{\sharp}, \pi_0^{\sharp})$ are two weighted transition systems, and $\beta^{\mathcal{L}} : \mathcal{L} \rightarrow \mathcal{L}^{\sharp}, \beta^{\mathcal{Q}} : Q \rightarrow Q^{\sharp}$, and $\gamma^{\mathcal{Q}} : Q^{\sharp} \rightarrow (Q \rightarrow [0, 1])$ are three mappings such that:

1. Both mappings $\beta^{\mathcal{L}}$ and $\beta^{\mathcal{Q}}$ are onto.

2. For any concrete state $q \in Q$ and any abstract state $q^{\sharp} \in Q^{\sharp}$, if $\gamma^{\mathcal{Q}}(q^{\sharp})(q) > 0$, then $\beta^{\mathcal{Q}}(q) = q^{\sharp}$. Moreover, for any abstract state $q^{\sharp} \in Q^{\sharp}$, the restriction of the mapping $\gamma^{\mathcal{Q}}(q^{\sharp})$ to the concrete state $q \in Q$ such that $\beta^{\mathcal{Q}}(q) = q^{\sharp}$ is a finite probability distribution.

3. For any two concrete states $q_1, q_2 \in Q$ such that $\beta^{\mathcal{Q}}(q_1) = \beta^{\mathcal{Q}}(q_2)$, we have $a(q_1) = a(q_2)$.

4. For any concrete state $q_1 \in Q$, we have $q_1 \in \mathcal{I}$ if, and only if, $\beta^{\mathcal{Q}}(q_1) \in \mathcal{I}^{\sharp}$.

<footnote n="5">5 Unions can be computed over countable set of sets of traces involving different computation transition labels.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 8. An abstraction between two transition systems.</figcaption></figure>

5. We have $q^{\#} \stackrel{\lambda^{\#}}{\rightsquigarrow} q'^{\#}$, if and only if there exists a transition $q \stackrel{\lambda}{\rightarrow} q'$ such that $\beta^{Q}(q) = q^{\#}$, $\beta^{Q}(q') = q'^{\#}$, $\beta^{L}(\lambda) = \lambda^{\#}$.

6. For any concrete state $q \in \mathcal{I}$, we have: $\pi_0(q) = \gamma^Q(\beta^Q(q))(q) \cdot \pi_0^\#(\beta^Q(q))$.

7. For any abstract transition $q^{\#} \stackrel{\lambda^{\#}}{\rightsquigarrow} q'^{\#}$ and any concrete state $q^{\#}$ such that $\beta^{Q}(q^{\#}) = q'^{\#}$, we have:

$$ \sum_q \sum_{\lambda} \left( \gamma^Q(q^{\#})(q) \cdot w(q, \lambda) \mid \begin{array}{l} q \in \mathcal{Q}, \lambda \in \mathcal{L} \text{ s.t. } q \stackrel{\lambda}{\rightarrow} q^{\#}, \\ \beta^Q(q) = q^{\#}, \beta^L(\lambda) = \lambda^{\#} \end{array} \right) \\ = \gamma^Q(q'^{\#})(q^{\#}) \cdot w^\#(q^{\#}, \lambda^{\#}). $$

In this definition, the system $\mathcal{S}$ is called the concrete system, whereas the system $\mathcal{S}^{\#}$ is called the abstract system. Moreover, we often say that the tuple $(\mathcal{S}, \mathcal{S}^{\#}, \beta^{\mathcal{Q}}, \gamma^{\mathcal{Q}})$ is an abstraction between the concrete system $\mathcal{S}$ and the abstract system $\mathcal{S}^{\#}$ (eg see<fnref n="6" /> Fig. 8). The mappings $\beta^{\mathcal{Q}}$ and $\gamma^{\mathcal{Q}}$ relate concrete and abstract states, whereas the mapping $\beta^{\mathcal{L}}$ relates concrete and abstract labels. The first property ensures that any abstract transition label (resp. any abstract state) is actually the abstraction of a concrete transition label (resp. a concrete state). The second property entails that an abstract state $q^{\#}$ denotes a finite set of concrete states $\{q \mid \beta^{\mathcal{Q}}(q) = q^{\#}\}$, moreover $\gamma(q^{\#})$ denotes a probability distribution of the concrete states $q$ such that $\beta^{\mathcal{Q}}(q) = q^{\#}$. The third property requires that two states having the same abstraction, also have the same activity. The fourth property ensures that when two concrete states have the same abstraction, then the first one is an initial state if, and only if the second one is initial. In such a case, their abstraction is an abstract initial state. The fifth property ensures that the set of abstract transitions is obtained by applying the

<footnote n="6">⁶ Notice that, unlike in the continuous-time Markov chains, our formalism of weighted transition systems allows for self-loops, ie identity transitions. To obtain a Markov chain, residence times need to be adjusted according to the rates of the identity transitions. A similar problem is considered in [19] (Section 2.3).</footnote>
abstraction function $\beta^Q$ to initial and final states and the abstraction function $\beta^L$ to the label of each concrete transition.

The last two properties may seem uncommon. Usually we require that two concrete states having the same abstract state behave similarly in the abstract: more precisely given three concrete states $q_1, q'_1$, and $q_2$ in $\mathcal{Q}$ such that there is a transition between $q_1$ and $q'_1$, and such that $\beta^Q(q_1) = \beta^Q(q_2)$, it would entail the existence of a fourth state $q'_2 \in \mathcal{Q}$ such that there is a transition between $q_2$ and $q'_2$, and such that $\beta^Q(q'_1) = \beta^Q(q'_2)$. But we have seen in Sect. 2.3.1 an example of abstract transition system in which this property does not hold. Instead of quotienting the set of transitions, we only assume that the abstract transition system preserves the distributions of concrete state that are given by the family of finite distributions $(\gamma(q^\sharp) | q^\sharp \in \mathcal{Q}^\sharp)$. More precisely, the sixth property states that the probability that an initial state is $q$ knowing the fact that the abstraction of this state is $\beta^Q(q)$ is given by $\gamma^Q(\beta^Q(q))(q)$. The seventh property has two consequences. On the first hand, it ensures a relation between the concrete weight function to the abstract one (eg. see Lemma 2). On the other hand, it ensures the fact that the probability that the system is in the concrete state $q$ knowing that it is in the abstract state $\beta^Q(q)$ is equal to $\gamma^Q(\beta^Q(q))(q)$ is preserved by computation step: if we fix an abstract state $q^\sharp \in \mathcal{Q}^\sharp$ and an abstract transition $q^\sharp \stackrel{\lambda^\sharp}{\rightsquigarrow} q'^\sharp$ and if we take two concrete states $q'_1$ and $q'_2$ such that $\beta^Q(q'_1) = \beta^Q(q'_2) = q'^\sharp$, thanks to Def. 6.(3) and Def. 6.(7), we have:

$$ \gamma(q^{\sharp'})(q_2^*) \cdot \sum_q \sum_{\lambda} \left( \gamma^Q(q^\sharp)(q) \cdot \frac{w(q, \lambda)}{a(q)} \middle| \begin{array}{l} q \in \mathcal{Q}, \lambda \in \mathcal{L} \text{ s.t. } q \stackrel{\lambda}{\rightarrow} q_1^*, \\ \beta^Q(q) = q^\sharp, \beta^L(\lambda) = \lambda^\sharp \end{array} \right) \\ = \gamma(q^{\sharp'})(q_1^*) \cdot \sum_q \sum_{\lambda} \left( \gamma^Q(q^\sharp)(q) \cdot \frac{w(q, \lambda)}{a(q)} \middle| \begin{array}{l} q \in \mathcal{Q}, \lambda \in \mathcal{L} \text{ s.t. } q \stackrel{\lambda}{\rightarrow} q_2^*, \\ \beta^Q(q) = q^\sharp, \beta^L(\lambda) = \lambda^\sharp \end{array} \right). $$

Moreover, we know by Def. 6.(5) that whenever there exists a transition $q \stackrel{\lambda}{\rightarrow} q'$ such that $\beta^Q(q) = q^\sharp$ and $\beta^L(\lambda) = \lambda^\sharp$, then we have $\beta^Q(q') = q'^\sharp$. So the distribution $\gamma(q^{\sharp'})$ is also equal to the distribution of the states $q'_0$ that can be reached after one step of computation $q_0 \stackrel{\lambda_0}{\rightarrow} q'_0$, knowing that the concrete state $q_0$ is chosen according to the distribution $\gamma(q^\sharp)$. The transition step is chosen according to the rate $w(q_0, \lambda_0)$ among all the transitions $q_0 \stackrel{\lambda}{\rightarrow} q'$ between the state $q_0$ and a state $q'$ such that $\beta^\sharp(q') = q'^\sharp$ and such that $\beta^\sharp(\lambda) = \lambda^\sharp$.

### 3.3.2 Correspondence

Let us consider an abstraction $(S, S^\sharp, \beta^Q, \beta^Q, \gamma^Q)$ between a concrete system $S = (\mathcal{Q}, \mathcal{L}, \rightarrow, w, \mathcal{I}, \pi_0)$ and an abstract system $S^\sharp = (\mathcal{Q}^\sharp, \mathcal{L}^\sharp, \rightsquigarrow, w^\sharp, \mathcal{I}^\sharp, \pi_0^\sharp)$. We want to state the correspondence between trace density distribution in these two systems. Let us first prove three lemmas. The following lemma states that the distribution $i^\sharp$ of abstract initial state is an exact abstraction of the distribution $i$ of concrete initial states.
**Lemma 1.** For any abstract state $q^{\#} \in \mathcal{I}^{\#}$, we have:

$$ \pi_0^{\#}(q^{\#}) = \sum_q (\pi_0(q) | q \in \mathcal{Q} \text{ s.t. } \beta_{\mathcal{Q}}(q) = q^{\#}) . $$

*Proof.* Let $q^{\#} \in \mathcal{I}^{\#}$. First, thanks to Def. 6.(4), we know that for any concrete state $q$ such that $\beta^{\mathcal{Q}}(q) = q^{\#}$, we have $q \in \mathcal{I}$. Then the function $\gamma(q^{\#})$ is a finite probability distribution. So, we have $\sum (\gamma^{\mathcal{Q}}(q^{\#})(q) | q \in \mathcal{Q} \text{ s.t. } \beta^{\mathcal{Q}}(q) = q^{\#})$ is equal to 1.

Then we get that:

$$ \pi_0^{\#}(q^{\#}) = \pi_0^{\#}(q^{\#}) \cdot \sum_q (\gamma^{\mathcal{Q}}(q^{\#})(q) | q \in \mathcal{Q} \text{ s.t. } \beta^{\mathcal{Q}}(q) = q^{\#}) $$

$$ \pi_0^{\#}(q^{\#}) = \sum_q (\gamma^{\mathcal{Q}}(q^{\#})(q) \cdot \pi_0^{\#}(q^{\#}) | q \in \mathcal{Q} \text{ s.t. } \beta^{\mathcal{Q}}(q) = q^{\#}) $$

$$ \pi_0^{\#}(q^{\#}) = \sum_q (\gamma^{\mathcal{Q}}(\beta^{\mathcal{Q}}(q))(q) \cdot \pi_0^{\#}(\beta^{\mathcal{Q}}(q)) | q \in \mathcal{Q} \text{ s.t. } \beta^{\mathcal{Q}}(q) = q^{\#}) . $$

By Def. 6(6), we get that:

$$ \pi_0^{\#}(q^{\#}) = \sum_q (\pi_0(q) | q \in \mathcal{Q} \text{ s.t. } \beta^{\mathcal{Q}}(q) = q^{\#}) . $$

<figure><img src="image_6.png" /></figure>

The following lemma expresses the soundness relation between the abstract weight function $w^{\#}$ and the concrete one $w$:

**Lemma 2.** For any abstract state $q^{\#} \in \mathcal{Q}^{\#}$ and any abstract label $\lambda^{\#} \in \mathcal{L}^{\#}(q^{\#})$, we have:

$$ w^{\#}(q^{\#}, \lambda^{\#}) = \sum_q \sum_{\lambda} \left( \gamma^{\mathcal{Q}}(q^{\#})(q) \cdot w(q, \lambda) \middle| \substack{q \in \mathcal{Q}, \lambda \in \mathcal{L} \text{ s.t.} \\ \lambda \in \mathcal{L}(q), \beta^{\mathcal{L}}(\lambda) = \lambda^{\#}} \right) . $$

*Proof.* Since, $\lambda^{\#} \in \mathcal{L}^{\#}(q^{\#})$, there exists a unique abstract state $q^{\#'}$ such that $q^{\#} \xrightarrow{\lambda^{\#}} q^{\#'}$. By Def. 6.(2), $\gamma(q^{\#'})$ is a finite distribution. It follows that:

$$ w^{\#}(q^{\#}, \lambda^{\#}) = \sum_{q'} (\gamma(q^{\#'})(q') \cdot w^{\#}(q^{\#}, \lambda^{\#}) | q' \in \mathcal{Q}, \text{ s.t. } \beta^{\mathcal{Q}}(q') = q^{\#'}) . $$

So, by Def. 6.(7), we have:

$$ w^{\#}(q^{\#}, \lambda^{\#}) = \sum_q \sum_{\lambda} \left( \gamma^{\mathcal{Q}}(q^{\#})(q) \cdot w(q, \lambda) \middle| \substack{q \in \mathcal{Q}, \lambda \in \mathcal{L}, \text{ s.t. } \exists q' \in \mathcal{Q}, \\ q \xrightarrow{\lambda} q', \beta^{\mathcal{Q}}(q) = q^{\#}, \\ \beta^{\mathcal{Q}}(q') = q^{\#'}, \beta^{\mathcal{L}}(\lambda) = \lambda^{\#}} \right) . $$

But whenever $q \xrightarrow{\lambda} q'$ is a concrete transition, then we know that $\beta^{\mathcal{Q}}(q) \xrightarrow{\beta^{\mathcal{L}}(\lambda)} \beta^{\mathcal{Q}}(q')$ is an abstract transition (by Def. 6.(5)). Then, since $\beta^{\mathcal{Q}}(q) \xrightarrow{\beta^{\mathcal{L}}(\lambda)} q^{\#'}$, it follows that $q^{\#'} = \beta^{\mathcal{Q}}(q')$ (because we have assumed that ingoing and outgoing states are fully determined by the transition label). We can conclude that:

$$ w^{\#}(q^{\#}, \lambda^{\#}) = \sum_q \sum_{\lambda} \left( \gamma^{\mathcal{Q}}(q^{\#})(q) \cdot w(q, \lambda) \middle| \substack{q \in \mathcal{Q}, \lambda \in \mathcal{L} \text{ s.t.} \\ \lambda \in \mathcal{L}(q), \beta^{\mathcal{L}}(\lambda) = \lambda^{\#}} \right) . $$

<figure><img src="image_7.png" /></figure>
The following lemma ensures that abstraction preserves activity:

**Lemma 3.** For any concrete state $q \in \mathcal{Q}$ and any abstract state $q^\sharp \in \mathcal{Q}^\sharp$ such that $\beta^Q(q) = q^\sharp$, we have $a(q) = a(q^\sharp)$.

*Proof.* By Def. 2, we have: $a(q^\sharp) = \sum(w^\sharp(q^\sharp, \lambda^\sharp) | \lambda^\sharp \in \mathcal{L}^\sharp(q^\sharp))$. Then, by Lemma 2, we have:

$$a(q^\sharp) = \sum_q \sum_\lambda \left( \gamma^Q(q^\sharp)(q) \cdot w(q, \lambda) \mid q \in \mathcal{Q}, \lambda \in \mathcal{L} \text{ s.t. } q \xrightarrow{\lambda} q', \beta^Q(q) = q^\sharp \right).$$

By Def. 2, it follows that:

$$a(q^\sharp) = \sum_q (\gamma(q^\sharp)(q) \cdot a(q) \mid q \in \mathcal{Q}).$$

By Def. 6.(2), $\gamma(q^\sharp)$ is a finite probability distribution and by Def. 6.(3), $a(q_1) = a(q_2)$ for any $q_1, q_2 \in \mathcal{Q}$ such that $\beta^Q(q_1) = q^\sharp = \beta^Q(q_2)$. Thus we can conclude that $a(q^\sharp) = a(q)$.

<figure><img src="image_8.png" /></figure>

Now we relate basic set of traces in the concrete semantics and basic set of traces in the abstract semantics: we introduce the function $\beta^T$ which maps any basic set $q_0 \xrightarrow{\lambda_0, I_1} q_1 \cdots q_{k-1} \xrightarrow{\lambda_k, I_k} q_k$ of concrete traces to the basic set $\beta^Q(q_0) \xrightarrow{\beta^L(\lambda_0), I_1} \beta^Q(q_1) \cdots \beta^Q(q_{k-1}) \xrightarrow{\beta^L(\lambda_k), I_k} \beta^Q(q_k)$ of abstract traces. Thus, $\beta^T$ applies $\beta^Q$ to each state and $\beta^L$ to each transition label, whereas time intervals are all preserved.

**Theorem 3.** For any basic set $\tau^\sharp = q_0^\sharp \xrightarrow{\lambda_1^\sharp, I_1} q_1^\sharp \cdots q_{k-1}^\sharp \xrightarrow{\lambda_k^\sharp, I_k} q_k^\sharp$ of abstract traces of any length $k$ and any sequence of steps, the following holds.

1. **soundness.** the probability $P(\tau^\sharp)$ of the basic set $\tau^\sharp$ of abstract traces is equal to the sum of the probabilities of the basic sets $\tau$ of traces such that $\beta^T(\tau) = \tau^\sharp$. That is to say:

$$P(\tau^\sharp) = \sum_{\tau} (P(\tau) | \tau \in \mathcal{T}_{\mathbb{R}^+} \text{ s.t. } \beta^T(\tau) = \tau^\sharp).$$

2. **completeness.** we have:

$$\sum_{\tau} (P(\tau) | \tau \in \mathcal{T}_{\mathbb{R}^+} \text{ s.t. } \beta^T(\tau) = \tau^\sharp, \text{state}_k(\tau) = q_k^*) = \gamma(q_k^*)(q_k^*) \cdot P(\tau^\sharp).$$

The soundness of the abstraction is stated in a classic way: it ensures that we can perform the computation of the probability that an abstract trace lies in a given basic set $\tau^\sharp$ of abstract traces (of size $k$) either in the abstract, or in the concrete by summing the probabilities that a concrete trace lies in the basic set $\tau \in \mathcal{T}_{\mathbb{R}^+}$ for any $\tau \in \mathcal{T}_{\mathbb{R}^+}$ such that $\beta^T(\tau) = \tau^\sharp$. Both ways will give the same result. The completeness states that, even if the computation was made in the abstract, we can recover the distribution over the concrete states that are
abstracted by the final abstract state. Indeed, the distribution of the final states is given by $\gamma^Q(\text{state}_k(\tau^\sharp))$. We can get the same result for the distribution of the i-th state by applying the completeness property to $\text{pref}_i(\tau^\sharp)$. Then one can wonder which information have been lost by the abstraction. Indeed we have lost some information about the correlation between the distinct concrete states in concrete traces. For instance, if we fix the i-th state $q_i^*$ (according to the finite distribution $\gamma^Q(q_i^*)$), it discloses some information about previous states and future states: the probability that the j-th state of a trace in a basic set $\tau$ of concrete traces such that $\beta^T(\tau) = \tau^\sharp$, knowing that the i-th state is $q_i^*$, may not be given by $\gamma^Q(\text{state}_j(\tau^\sharp))$.

We now give the proof of The. 3.

*Proof (of The. 3).* First we prove the completeness, by induction over $k$, the size of the trace $\tau^\sharp$.

We assume that $k = 0$ and we consider a state $q_0^* \in \mathcal{Q}$ (notice that by definition of traces, we have $q_0^* \in \mathcal{I}$).

We have:

$$ \pi_0(q_0^*) = \sum_{q_0} (P(q_0) \mid q_0 \in \mathcal{Q} \text{ s.t. } \beta^Q(q_0) = q_0^\sharp, q_0 = q_0^*) . $$

Then, by Def. 6.(6), $\pi_0(q_0^*) = \gamma(q_0^\sharp)(q_0^*) \cdot \pi_0^\sharp(\beta^Q(q_0^*))$.

It follows that $\pi_0(q_0^*) = \gamma(q_0^\sharp)(q_0^*) \cdot P(q_0^\sharp)$.

Now we assume that we are given $k_0 \in \mathbb{N}$ such that The. 3.(b) holds for $k = k_0$, and we prove that it also holds for $k = k_0 + 1$:

We denote:

$$ P = \sum_{\tau} (P(\tau) \mid \tau \in \mathcal{T}_{\mathbb{R}^+} \text{ s.t. } \beta^T(\tau) = \tau^\sharp, \text{state}_k(\tau) = q_k^*). $$

We split the latter sum according to the last transition step. We get:

$$ P = \sum_{q_{k-1}^*} \sum_{\lambda_k^*} \left( a(q_{k-1}^*, \lambda_k^*) \cdot b(q_{k-1}^*) \mid \begin{array}{l} q_{k-1}^* \in \mathcal{Q}, \lambda_k^* \in \mathcal{L} \text{ s.t. } q_{k-1}^* \xrightarrow{\lambda_k^*} q_k^* \\ \beta^Q(q_{k-1}^*) = q_{k-1}^\sharp, \beta^\mathcal{L}(\lambda_k^*) = \lambda_k^\sharp \end{array} \right), $$

where (by Def. 5):

$$ a(q_{k-1}^*, \lambda_k^*) := \frac{w(q_{k-1}^*, \lambda_k^*) \cdot \left( e^{-a(q_{k-1}^*) \cdot \inf(I_k)} - e^{-a(q_{k-1}^*) \cdot \sup(I_k)} \right)}{a(q_{k-1}^*)}; $$

$$ b(q_{k-1}^*) := \sum_{\tau} \left( P(\tau) \mid \begin{array}{l} \tau \in \mathcal{T}_{\mathbb{R}^+} \text{ s.t. } \beta^T(\tau) = \text{pref}_{k-1}(\tau^\sharp), \\ \text{and state}_{k-1}(\tau) = q_{k-1}^* \end{array} \right). $$

Then by induction hypothesis, we have:

$$ b(q_{k-1}^*) = \gamma(q_{k-1}^\sharp)(q_{k-1}^*) \cdot P(\text{pref}_{k-1}(\tau^\sharp)). $$

Moreover, by Def. 6.(7), we know that:

$$ \sum_{q_{k-1}^*} \sum_{\lambda_k^*} \left( \gamma(q_{k-1}^\sharp)(q_{k-1}^*) \cdot w(q_{k-1}^*, \lambda_k^*) \mid \begin{array}{l} q_{k-1}^* \in \mathcal{Q}, \lambda_k^* \in \mathcal{L} \text{ s.t. } q_{k-1}^* \xrightarrow{\lambda_k^*} q_k^* \\ \beta^Q(q_{k-1}^*) = q_{k-1}^\sharp, \beta^\mathcal{L}(\lambda_k^*) = \lambda_k^\sharp \end{array} \right) = \gamma^Q(q_k^\sharp)(q) \cdot w^\sharp(q_{k-1}^*, \lambda_{k-1}^\sharp). $$
So $P$ is equal to:

$$ \gamma^{\mathcal{Q}}(q_k^{\mathcal{h}})(q) \cdot P(\mathrm{pref}_{k-1}(\tau^{\mathcal{h}})) \cdot \frac{w^{\mathcal{h}}(q_{k-1}^{\mathcal{h}}, \lambda_{k-1}^{\mathcal{h}}) \cdot (e^{-a(q_{k-1}^{\mathcal{h}}) \cdot \inf(I_k)} - e^{-a(q_{k-1}^{\mathcal{h}}) \cdot \sup(I_k)})}{a(q_{k-1}^{\mathcal{h}})} $$

By definition (of $P(\tau^{\mathcal{h}})$), it follows that $P = \gamma^{\mathcal{Q}}(q_k^{\mathcal{h}})(q) \cdot P(\tau^{\mathcal{h}})$.

Thus, we have proved The. 3.(2). Now we can prove the soundness part (The. 3.(1)) by summing the equality of The. 3.(2) for any $q_k^*$ such that $\beta^{\mathcal{Q}}(q_k^*) = q_k^*$ and by using the fact that $\gamma^{\mathcal{Q}}(q_k^*)$ is a finite probability distribution (by Def. 6.(1)).

□

### 3.3.3 Abstraction induced by an admissible pair of binary equivalence relations

In this section, we introduce a method for deriving an abstract system from a concrete one. We focus our study to the abstractions in which the concretization function $\gamma^{\mathcal{Q}}$ maps each abstract state to a finite uniform probability distribution. One way to define such an abstraction consists in using an *admissible pair of binary equivalence relations* that is given by two binary equivalence relations (respectively over concrete states and concrete transition labels) which satisfy some additional properties so as to ensure that, at any time, two equivalent concrete states have the same probability to occur (eg see Def. 7).

Let us consider a weighted labeled transition system $S = (\mathcal{Q}, \mathcal{L}, \to, w, \mathcal{I}, \pi_0)$, that we call the concrete system. We introduce two binary equivalence relations, namely $\sim_{\mathcal{Q}}$ and $\sim_{\mathcal{L}}$, so as to abstract the concrete states and the concrete transition labels by quotienting the set $\mathcal{Q}$ and $\mathcal{L}$ by $\sim_{\mathcal{Q}}$ and $\sim_{\mathcal{L}}$. We define as follows the properties that are required for the pair $(\sim_{\mathcal{Q}}, \sim_{\mathcal{L}})$ of relations to be admissible:

**Definition 7 (admissible pair of binary equivalence relations).** The pair $(\sim_{\mathcal{Q}}, \sim_{\mathcal{L}})$ of binary equivalence relations is said to be admissible for abstracting the system $S$ if, and only if, for any states $q_1, q'_1, q_2, q'_2 \in \mathcal{Q}$, and any transition labels $\lambda_1, \lambda_2 \in \mathcal{L}$, the following properties are satisfied:

1. the equivalence class $[q_1]_{\sim_{\mathcal{Q}}}$ is finite;

2. $q_1 \sim_{\mathcal{Q}} q_2 \implies a(q_1) = a(q_2)$;

3. $q_1 \sim_{\mathcal{Q}} q_2 \wedge q_1 \in \mathcal{I} \implies q_2 \in \mathcal{I} \wedge \pi_0(q_1) = \pi_0(q_2)$;

4. $\lambda_1 \sim_{\mathcal{L}} \lambda_2 \wedge q_1 \xrightarrow{\lambda_1} q'_1 \wedge q_2 \xrightarrow{\lambda_2} q'_2 \implies \begin{cases} q_1 \sim_{\mathcal{Q}} q_2 \wedge q'_1 \sim_{\mathcal{Q}} q'_2 \\ \text{and } w(q_1, \lambda_1) = w(q_2, \lambda_2); \end{cases}$

5. if $q'_1 \sim_{\mathcal{Q}} q'_2$, then the set $\{(q, \lambda) \mid q \sim_{\mathcal{Q}} q_1, \lambda \sim_{\mathcal{L}} \lambda_1, q \xrightarrow{\lambda} q'_1\}$ and the set $\{(q, \lambda) \mid q \sim_{\mathcal{Q}} q_1, \lambda \sim_{\mathcal{L}} \lambda_1, q \xrightarrow{\lambda} q'_2\}$ are in bijection.

Roughly speaking, the first property ensures that we can associate each equivalence class of concrete states with a finite distribution (as required by
Def. 6.(2)). The second property ensures that equivalent concrete states have the same activity. This way, the same system in two equivalent concrete states will behave with the same time scale. The fact that a class of transition labels fully identifies a class of ingoing concrete states and a class of outgoing concrete states comes from the fourth property. It is worth noticing that we do not assume that equivalent concrete states have the same behavior (up to ~Q and ~L) since the fourth property is only an implication. Moreover, the last three properties ensure that at any time, the probability that the system is in a given concrete state $q \in Q$ is the same for any ~Q-equivalent concrete state $q' \in [q]_{\sim_Q}$. This fairness property holds at time $t = 0$ thanks to the third property, and is an invariant of the dynamics of the system thanks to the last two properties. More precisely, the fifth property ensures that, if we fix the class of ingoing states and the class of transition labels, there are equally many transitions that lead to any equivalent outgoing state. The fourth property ensures that these transition steps have all the same rate.

In the following, we assume that the pair (~Q, ~L) is admissible for abstracting the system S. We use the binary equivalence relations ~Q and ~L to define the tuple $S^\# := (Q^\#, L^\#, \rightsquigarrow, w^\#, I^\#, \pi_0^\#)$, where: the set $Q^\#$ of abstract states is defined as the set of equivalence classes of the relation ~Q; the set of $L^\#$ of abstract transition labels is defined as the set of equivalence classes of the relation ~L; the abstract transition relation ~\rightsquigarrow is defined by: for any $q^\#, q'^\in Q^\#$ and any $\lambda^\# \in L^\#$, $q^\# \rightsquigarrow q'^\#$, if, and only if, there exists$^7$ $q \in q^\#$, $\lambda \in \lambda^\#$, and $q' \in q'^\#$ such that $q \stackrel{\lambda}{\to} q'$ (notice that the property Def. 7.(4) ensures that an abstract transition label fully defines the ingoing and outgoing states); the weight function $w^\#$ is defined as follows:

$$w^\#(q^\#, \lambda^\#) = \sum_q \sum_\lambda \left( \frac{w(q, \lambda)}{\mathrm{card}(q^\#)} \middle| \begin{array}{l} q \in q^\#, \lambda \in \lambda^\# \text{ s.t.} \\ \exists q'^\# \in Q^\#, q' \in q'^\#, q \stackrel{\lambda}{\to} q' \end{array} \right);$$

the set $I^\#$ of abstract initial states is defined as the set of the classes $\{[q_0]_{\sim_Q} | q_0 \in I\}$ of concrete initial states and the distribution of abstract initial states is defined by:

$$\pi_0^\#(q^\#) = \sum_q (\pi_0(q) | q \in q^\#),$$

which comes down to collect the initial probability of any initial state that is compatible with a given abstract initial state.

The tuple $S^\#$ is indeed a weighted labeled transition system and the pair (~Q, ~L) induces an abstraction between the systems S and $S^\#$, as stated by the following proposition:

**Proposition 1 (induced abstraction).** The tuple $S^\#$ is a weighted labeled transition system. Moreover the tuple $A = (S, S^\#, [\cdot]_{\sim_L}, [\cdot]_{\sim_Q}, \gamma^Q)$, where $\gamma^Q \in$

<footnote>$^7$ Since each abstract state $q^\# \in Q^\#$ and each abstract transition label $\lambda^\# \in L^\#$ is an equivalence class of respectively concrete states and concrete transition labels, we write $q \in q^\#$ and $\lambda \in \lambda^\#$ to say that $q^\#$ and $\lambda^\#$ are the abstraction of $q$ and $\lambda$.</footnote>
$\mathcal{Q}^{\#} \to (\mathcal{Q} \to [0, 1])$ is defined as:

$$ \gamma^{\mathcal{Q}}([q_1]_{\sim_{\mathcal{Q}}})(q_2) = \begin{cases} \frac{1}{\text{card}([q_1]_{\sim_{\mathcal{Q}}})} & \text{whenever } q_1 \sim_{\mathcal{Q}} q_2, \\ 0 & \text{otherwise;} \end{cases} $$

is an abstraction.

This abstraction is called the abstraction induced by the pair $(\sim_{\mathcal{Q}}, \sim_{\mathcal{L}})$ of binary equivalence relations.

*Proof.* Let us prove that the seven properties in Def. 6 are satisfied.

1. Both mappings $[\cdot]_{\sim_{\mathcal{L}}}$ and $[\cdot]_{\sim_{\mathcal{Q}}}$ are onto, since, by definition, an equivalence class is not empty.

2. Let $q_1, q_2$ be two concrete states in $\mathcal{Q}$ such that $\gamma^{\mathcal{Q}}([q_1]_{\sim_{\mathcal{Q}}})(q_2) > 0$. By definition of $\gamma^{\mathcal{Q}}$, we have $q_2 \in [q_1]_{\sim_{\mathcal{Q}}}$. Moreover, for any concrete state $q_1 \in \mathcal{Q}$, by Def. 7.(1), the class $[q_1]_{\sim_{\mathcal{Q}}}$ is finite and:

$$ \begin{aligned} \sum_{q_2} (\gamma([q_1]_{\sim_{\mathcal{Q}}})(q_2) \mid q_2 \in \mathcal{Q}) &= \sum_{q_2} (\gamma([q_1]_{\sim_{\mathcal{Q}}})(q_2) \mid q_2 \in [q_1]_{\sim_{\mathcal{Q}}}) \\ &= \sum_{q_2} \left( \frac{1}{\text{card}([q_1]_{\sim_{\mathcal{Q}}})} \mid q_2 \in [q_1]_{\sim_{\mathcal{Q}}} \right) \\ &= 1, \end{aligned} $$

which proves Def. 6.(2).

3. The property Def. 6.(3) comes directly from Def. 7.(2).

4. Let $q$ be a concrete state in $\mathcal{Q}$.

By definition of $\mathcal{I}^{\#}$, if $q \in \mathcal{I}$, then $[q]_{\sim_{\mathcal{Q}}} \in \mathcal{I}^{\#}$.

Conversely, let us assume that $[q]_{\sim_{\mathcal{Q}}} \in \mathcal{I}^{\#}$. Then, by definition of $\mathcal{I}^{\#}$, there exists a concrete state $q' \in \mathcal{Q}$ such that $q' \in [q]_{\sim_{\mathcal{Q}}}$ and $q' \in \mathcal{I}$. Then, since $q' \in [q]_{\sim_{\mathcal{Q}}}$, we also have: $q \sim_{\mathcal{Q}} q'$. So by Def. 7.(3), it follows that $q \in \mathcal{I}$.

5. The property Def. 6.(5) comes directly from the definition of $\rightsquigarrow$.

6. Let $q_{\star}$ be a concrete state in $\mathcal{I}$.

We have, by definition of $\pi_0^{\#}$:

$$ \pi_0^{\#}([q_{\star}]_{\sim_{\mathcal{Q}}}) = \sum_q (\pi_0(q) \mid q \in [q_{\star}]_{\sim_{\mathcal{Q}}}). $$

By Def. 7.(3), it follows that:

$$ \pi_0^{\#}([q_{\star}]_{\sim_{\mathcal{Q}}}) = \pi_0(q_{\star}) \cdot \text{card}([q_{\star}]_{\sim_{\mathcal{Q}}}). $$

Since the set $[q_{\star}]_{\sim_{\mathcal{Q}}}$ is not empty (it contains the element $q_{\star}$), it follows that:

$$ \pi_0(q_{\star}) = \frac{\pi_0^{\#}([q_{\star}]_{\sim_{\mathcal{Q}}})}{\text{card}([q_{\star}]_{\sim_{\mathcal{Q}}})}. $$

As a consequence, by definition of $\gamma^{\mathcal{Q}}$, we have:

$$ \pi_0(q_{\star}) = \pi_0^{\#}([q_{\star}]_{\sim_{\mathcal{Q}}}) \cdot \gamma^{\mathcal{Q}}([q_{\star}]_{\sim_{\mathcal{Q}}})(q_{\star}). $$
7. Let $q^{\sharp} \stackrel{\lambda^{\sharp}}{\rightsquigarrow} q^{\sharp'}$ be an abstract transition and $q^*$ be a concrete element in $\mathcal{Q}$ such that $q^* \in q^{\sharp'}$.
By definition of $w^{\sharp}$, we have:

$$w^{\sharp}(q^{\sharp}, \lambda^{\sharp}) = \sum_q \sum_{\lambda} \left( \frac{w(q, \lambda)}{\text{card}(q^{\sharp})} \middle| q \in q^{\sharp}, \lambda \in \lambda^{\sharp} \text{ s.t. } \exists q' \in q^{\sharp'}, q \stackrel{\lambda}{\to} q' \right).$$

Then, by partitioning the sums according to the outgoing state of transition steps, it follows that:

$$w^{\sharp}(q^{\sharp}, \lambda^{\sharp}) = \frac{\sum_{q'} \sum_q \sum_{\lambda} \left( w(q, \lambda) \middle| q' \in q^{\sharp'}, q \in q^{\sharp}, \lambda \in \lambda^{\sharp} \text{ s.t. } q \stackrel{\lambda}{\to} q' \right)}{\text{card}(q^{\sharp})}.$$

By Def. 7.(4) and Def. 7.(5), we have:

$$w^{\sharp}(q^{\sharp}, \lambda^{\sharp}) = \frac{\sum_{q'} \sum_q \sum_{\lambda} \left( w(q, \lambda) \middle| q' \in q^{\sharp'}, q \in q^{\sharp}, \lambda \in \lambda^{\sharp} \text{ s.t. } q \stackrel{\lambda}{\to} q^{\star} \right)}{\text{card}(q^{\sharp})}.$$

It follows that:

$$w^{\sharp}(q^{\sharp}, \lambda^{\sharp}) = \frac{\text{card}(q^{\sharp'})}{\text{card}(q^{\sharp})} \cdot \sum_q \sum_{\lambda} \left( w(q, \lambda) \middle| q \in q^{\sharp}, \lambda \in \lambda^{\sharp} \text{ s.t. } q \stackrel{\lambda}{\to} q^{\star} \right).$$

Then,

$$\frac{w^{\sharp}(q^{\sharp}, \lambda^{\sharp})}{\text{card}(q^{\sharp'})} = \sum_q \sum_{\lambda} \left( \frac{w(q, \lambda)}{\text{card}(q^{\sharp})} \middle| q \in q^{\sharp}, \lambda \in \lambda^{\sharp} \text{ s.t. } q \stackrel{\lambda}{\to} q^{\star} \right).$$

By definition of $\gamma^{\mathcal{Q}}$, we get that:

$$\gamma^{\mathcal{Q}}(q^{\sharp'})(q^*) \cdot w^{\sharp}(q^{\sharp}, \lambda^{\sharp}) = \sum_q \sum_{\lambda} \left( \gamma^{\mathcal{Q}}(q^{\sharp})(q) \cdot w(q, \lambda) \middle| \substack{q \in q^{\sharp}, \lambda \in \lambda^{\sharp} \\ \text{s.t. } q \stackrel{\lambda}{\to} q^*} \right).$$

<figure><img src="image_9.png" /></figure>

### 3.3.4 Abstraction algebra

In this section, we investigate two binary operators over abstractions, namely, the composition and the factorization of abstractions.

Let us consider three weighted transition systems $S^b$, $S$, and $S^\sharp$.

Two abstractions between the systems $S^b$ and $S$, and between the systems $S$ and $S^\sharp$ can be composed in order to form an abstraction between the systems $S^b$ and $S^\sharp$. More precisely, let us consider six mappings $\beta_1^L, \beta_1^Q, \gamma_1^Q, \beta_2^L, \beta_2^Q$, and $\gamma_2^Q$ such that $A_1 := (S^b, S, \beta_1^L, \beta_1^Q, \gamma_1^Q)$ and $A_2 := (S, S^\sharp, \beta_2^L, \beta_2^Q, \gamma_2^Q)$ are two abstractions.
**Proposition 2 (composition).** The tuple $A_3 := (S^b, S^\sharp, \beta_3^L, \beta_3^Q, \gamma_3^Q)$ where:
$\beta_3^L = \beta_2^L \circ \beta_1^L$, $\beta_3^Q = \beta_2^Q \circ \beta_1^Q$, and $\gamma_3^Q(q^\sharp)(q^b) = \gamma_2^Q(q^\sharp)(\beta_1^Q(q^b)) \cdot \gamma_1^Q(\beta_1^Q(q^b))(q^b)$,
is also an abstraction.

Moreover, $A_3$ is called the composition of $A_1$ and $A_2$, which is denoted by $A_3 = A_2 \circ A_1$.

*Proof.* Let us write $S^b = (Q^b, \mathcal{L}^b, \rightarrow_b, w^b, \mathcal{I}^b, \pi_0^b)$, $S = (Q, \mathcal{L}, \rightarrow, w, \mathcal{I}, \pi_0)$ and $S^\sharp = (Q^\sharp, \mathcal{L}^\sharp, \rightsquigarrow, w^\sharp, \mathcal{I}^\sharp, \pi_0^\sharp)$. We want to prove that the tuple $A_3$ satisfies the seven requirements of Def. 6:

1. The mapping $\beta_3^L$ and $\beta_3^Q$ are onto, because $A_1$ and $A_2$ are two abstractions, by Def. 6.(1), and as compositions of onto mappings.

2. Let $q^b$ be an element in the set $Q^b$ and $q^\sharp$ be an element in the set $Q^\sharp$ such that $\gamma_3^Q(q^\sharp)(q^b) > 0$. By definition, we have $\gamma_3^Q(q^\sharp)(q^b) = \gamma_2^Q(q^\sharp)(\beta_1^Q(q^b)) \cdot \gamma_1^Q(\beta_1^Q(q^b))(q^b)$. As a consequence, we have: $\gamma_2^Q(q^\sharp)(\beta_1^Q(q^b)) > 0$. Since $A_2$ is an abstraction, it follows by Def. 6.(2) that $\beta_2^Q(\beta_1^Q(q^b)) = q^\sharp$. By definition of $\beta_3^Q$, we have: $\beta_3^Q(q^b) = q^\sharp$.

Let $q^b$ be an element in the set $Q^b$ and $q^\sharp$ be an element in the set $Q^\sharp$ such that $\beta_3^Q(q^b) = q^\sharp$. By definition of $\beta_3^Q$, we have: $\beta_2^Q(\beta_1^Q(q^b)) = q^\sharp$. Thus, the element $q^b$ belongs to the set:

$$ \bigcup_q \left( \left\{ q^b \in Q^b \mid \beta_1^Q(q^b) \right\} \middle| q \in Q \text{ s.t. } \beta_2(q) = q^\sharp \right) $$

which is finite as a finite (since $A_2$ is an abstraction and by Def. 6.(2)) union of finite (since $A_3$ is an abstraction and by Def. 6.(2)) sets.

Let $q^\sharp$ be an element in the set $Q^\sharp$. We have:

$$
\begin{align*}
& \sum_{q^b} \left( \gamma_3^Q(q^\sharp)(q^b) \mid q^b \in Q^b \text{ s.t. } \beta_3^Q(q^b) = q^\sharp \right) \\
&= \sum_{q^b} \left( \gamma_2^Q(q^\sharp)(\beta_1^Q(q^b)) \cdot \gamma_1^Q(\beta_1^Q(q^b))(q^b) \mid q^b \in Q^b \text{ s.t. } \beta_2^Q(\beta_1^Q(q^b)) = q^\sharp \right) \\
&= \sum_q \sum_{q^b} \left( \gamma_2^Q(q^\sharp)(q) \cdot \gamma_1^Q(q)(q^b) \mid \begin{array}{c} q \in Q, q^b \in Q^b \text{ s.t.} \\ \beta_1(q^b) = q, \beta_2(q) = q^\sharp \end{array} \right) \\
&= \sum_q \left( \gamma_2^Q(q^\sharp)(q) \cdot \left( \sum_{q^b} \left( \gamma_1^Q(q)(q^b) \mid \begin{array}{c} q^b \in Q^b \text{ s.t.} \\ \beta_1^Q(q^b) = q \end{array} \right) \right) \mid \begin{array}{c} q \in Q \text{ s.t.} \\ \beta_2^Q(q) = q^\sharp \end{array} \right) \\
&= \sum_q (\gamma_2^Q(q^\sharp)(q) \cdot 1 \mid q \in Q \text{ s.t. } \beta_2^Q(q) = q^\sharp) \\
&= 1
\end{align*}
$$

3. Given two elements $q_1^b$ and $q_2^b$ in $Q^b$ such that $\beta_3^Q(q_1^b) = \beta_3^Q(q_2^b)$, we have, by definition of $\beta_3^Q$, $\beta_2^Q(\beta_1^Q(q_1^b)) = \beta_2^Q(\beta_1^Q(q_2^b))$. Since $A_2$ is an abstraction, and by Def. 6.(3), it follows that $a(\beta_1^Q(q_1^b)) = a(\beta_1^Q(q_2^b))$. Then, by Lem. 3, it follows that: $a(q_1^b) = a(\beta_1^Q(q_1^b)) = a(\beta_1^Q(q_2^b)) = a(q_2^b)$.
4. Let $q^b$ be an element in $Q^b$. Since $A_1$ is an abstraction and by Def. 6.(4), it follows that: $q^b \in \mathcal{I}^b \iff \beta_1^Q(q^b) \in \mathcal{I}$. Then since $A_2$ is an abstraction and by Def. 6.(4), we have: $\beta_1^Q(q^b) \in \mathcal{I} \iff \beta_2^Q(\beta_1^Q(q^b)) \in \mathcal{I}^\sharp$. Then by definition, we have $\beta_2^Q(\beta_1^Q(q^b)) = \beta_3^Q(q^b)$. So: $q^b \in \mathcal{I}^b \iff \beta_3^Q(q^b) \in \mathcal{I}^\sharp$.

5. Let $q^\sharp, q^{\sharp'}$ be two elements in $Q^\sharp$ and $\lambda^\sharp$ be an element in $\mathcal{L}^\sharp$.

Let us assume that: $q^\sharp \stackrel{\lambda^\sharp}{\rightsquigarrow} q^{\sharp'}$. Since $A_2$ is an abstraction and by Def. 6.(5), there exists $q, q' \in Q$ and $\lambda \in \mathcal{L}$, such that $q \stackrel{\lambda}{\to} q'$, $\beta_2^Q(q) = q^\sharp$, $\beta_2^Q(q') = q^{\sharp'}$, and $\beta_2^L(\lambda) = \lambda^\sharp$. Then, since $A_1$ is an abstraction and by Def. 6.(5), there exists $q^b, q^{b'} \in Q^b$ and $\lambda^b \in \mathcal{L}^b$, such that $q^b \stackrel{\lambda^b}{\to} q^{b'}$, $\beta_1^Q(q^b) = q$, $\beta_1^Q(q^{b'}) = q'$, and $\beta_1^L(\lambda^b) = \lambda$. Then we have: $\beta_2^Q(\beta_1^Q(q^b)) = \beta_2^Q(q) = q^\sharp$, $\beta_2^Q(\beta_1^Q(q^{b'})) = \beta_2^Q(q') = q^{\sharp'}$, $\beta_2^L(\beta_1^L(\lambda^b)) = \beta_2^L(\lambda) = \lambda^\sharp$. By definition of $\beta_3^Q$ and $\beta_3^L$, it follows that: $\beta_3^Q(q^b) = q^\sharp$, $\beta_3^Q(q^{b'}) = q'$, and $\beta_3^L(\lambda^b) = \lambda$.

Conversely, let $q^b, q^{b'}$ be two elements in $Q^b$ and $\lambda^b$ be an element in $\mathcal{L}^b$ such that $q^b \stackrel{\lambda^b}{\to} q^{b'}$, $\beta_3^Q(q^b) = q^\sharp$, $\beta_3^Q(q^{b'}) = q'$, and $\beta_3^L(\lambda^b) = \lambda$. Thus, we have: $\beta_2^Q(\beta_1^Q(q^b)) = q^\sharp$, $\beta_2^Q(\beta_1^Q(q^{b'})) = q^{\sharp'}$, and $\beta_2^L(\beta_1^L(\lambda^b)) = \lambda^\sharp$. Then, since $A_2$ is an abstraction and by Def. 6.(5), we get that: $\beta_1^Q(q^b) \stackrel{\beta_1^L(\lambda^b)}{\to} \beta_1^Q(q^{b'})$. Then, since $A_3$ is an abstraction and by Def. 6.(5), we get that: $q^\sharp \stackrel{\lambda^\sharp}{\rightsquigarrow} q^{\sharp'}$.

6. Let $q^b$ be an element in $\mathcal{I}^b$. Since $A_1$ is an abstraction and by Def. 6.(6), we have:

$$ \pi_0^b(q^b) = \gamma_1^Q(\beta_1^Q(q^b))(q^b) \cdot \pi_0(\beta_1^Q(q^b)). $$

Then, since $A_2$ is an abstraction and by Def. 6.(6), we have:

$$ \pi_0^b(q^b) = \gamma_1^Q(\beta_1^Q(q^b))(q^b) \cdot \gamma_2^Q(\beta_2^Q(\beta_1^Q(q^b)))(\beta_1^Q(q^b)) \cdot \pi_0^\sharp(\beta_2^Q(\beta_1^Q(q^b))). $$

Then, by definition of $\gamma_3^Q$, we have:

$$ \pi_0^b(q^b) = \gamma_3^Q(\beta_2^Q(\beta_1^Q(q^b)))(q^b) \cdot \pi_0^\sharp(\beta_2^Q(\beta_1^Q(q^b))). $$

Then, by definition of $\beta_3^Q$, it follows that:

$$ \pi_0^b(q^b) = \gamma_3^Q(\beta_3^Q(q^b))(q^b) \cdot \pi_0^\sharp(\beta_3^Q(q^b)). $$
7. Let $q^{\sharp}, q^{\sharp'}$ be two elements in $Q^{\sharp}$ and $\lambda^{\sharp}$ be an element in $\mathcal{L}^{\sharp}$, such that $q^{\sharp} \xrightarrow{\lambda^{\sharp}} q^{\sharp'}$. Let $q^{\flat} \star$ be an element in $Q^{\flat}$ such that $\beta_3^{\mathcal{Q}}(q^{\flat} \star) = q^{\sharp'}$. Then:

$$
\begin{align*}
& \gamma_3(q^{\sharp'})(q^{\flat \star}) \cdot w^{\sharp}(q^{\sharp}, \lambda^{\sharp}) \\
&= \gamma_1(\beta_1^{\mathcal{Q}}(q^{\flat \star}))(q^{\flat \star}) \cdot \gamma_2(q^{\sharp'})(\beta_1^{\mathcal{Q}}(q^{\flat \star})) \cdot w^{\sharp}(q^{\sharp}, \lambda^{\sharp}) \\
&= \gamma_1(\beta_1^{\mathcal{Q}}(q^{\flat \star}))(q^{\flat \star}) \cdot \sum_q \sum_{\lambda} \left( \gamma_2^{\mathcal{Q}}(q^{\sharp})(q) \cdot w(q, \lambda) \middle| \begin{array}{l} q \in Q, \lambda \in \mathcal{L} \text{ s.t.} \\ q \xrightarrow{\lambda} \beta_1^{\mathcal{Q}}(q^{\flat \star}), \\ \beta_2^{\mathcal{Q}}(q) = q^{\sharp}, \\ \beta_2^{\mathcal{L}}(\lambda) = \lambda^{\sharp} \end{array} \right) \\
&= \sum_q \sum_{\lambda} \left( \gamma_2^{\mathcal{Q}}(q^{\sharp})(q) \cdot \gamma_1(\beta_1^{\mathcal{Q}}(q^{\flat \star}))(q^{\flat \star}) \cdot w(q, \lambda) \middle| \begin{array}{l} q \in Q, \lambda \in \mathcal{L} \text{ s.t.} \\ q \xrightarrow{\lambda} \beta_1^{\mathcal{Q}}(q^{\star}), \\ \beta_2^{\mathcal{Q}}(q) = q^{\sharp}, \\ \beta_2^{\mathcal{L}}(\lambda) = \lambda^{\sharp} \end{array} \right) \\
&= \sum_q \sum_{\lambda} \sum_{q^{\flat}} \sum_{\lambda^{\flat}} \left( \gamma_2^{\mathcal{Q}}(q^{\sharp})(q) \cdot \gamma_1(q)(q^{\flat}) \cdot w^{\flat}(q^{\flat}, \lambda^{\flat}) \middle| \begin{array}{l} q \in Q, \lambda \in \mathcal{L}, \\ q^{\flat} \in Q^{\flat}, \\ \lambda^{\flat} \in \mathcal{L}^{\flat} \text{ s.t.} \\ q \xrightarrow{\lambda} \beta_1^{\mathcal{Q}}(q^{\star}), \\ \beta_2^{\mathcal{Q}}(q) = q^{\sharp}, \\ \beta_2^{\mathcal{L}}(\lambda) = \lambda^{\sharp}, \\ q^{\flat} \xrightarrow{\lambda} \beta_1^{\mathcal{Q}}(q^{\star}), \\ \beta_1^{\mathcal{Q}}(q^{\flat \star}) = q, \\ \beta_1^{\mathcal{L}}(\lambda^{\flat}) = \lambda \end{array} \right) \\
&= \sum_{q^{\flat}} \sum_{\lambda^{\flat}} \left( \gamma_2^{\mathcal{Q}}(q^{\sharp})(\beta_1^{\mathcal{Q}}(q^{\flat})) \cdot \gamma_1(\beta_1^{\mathcal{Q}}(q))(q^{\flat}) \cdot w^{\flat}(q^{\flat}, \lambda^{\flat}) \middle| \begin{array}{l} q^{\flat} \in Q^{\flat}, \\ \lambda^{\flat} \in \mathcal{L}^{\flat} \text{ s.t.} \\ \beta_1^{\mathcal{Q}} \xrightarrow{\beta_1^{\mathcal{L}}(\lambda)} \beta_1^{\mathcal{Q}}(q^{\star}), \\ q^{\flat} \xrightarrow{\lambda} q^{\flat \star} \end{array} \right) \\
&= \sum_{q^{\flat}} \sum_{\lambda^{\flat}} (\gamma_3^{\mathcal{Q}}(q^{\sharp})(q^{\flat}) \cdot w^{\flat}(q^{\flat}, \lambda^{\flat}) \middle| q^{\flat} \in Q^{\flat}, \lambda^{\flat} \in \mathcal{L}^{\flat} \text{ s.t. } q^{\flat} \xrightarrow{\lambda} q^{\flat \star})
\end{align*}
$$

In this computation, we have used (i) the definition of $\gamma_3^{\mathcal{Q}}$; then (ii) the fact that $A_2$ is an abstraction and Def. 6.(7); then (iii) factorization; then (iv) the fact that $A_1$ is an abstraction and Def. 6.(7); then (v) quantification elimination over $q \in Q$ and $\lambda \in \mathcal{L}$; then (vi) the fact that $A_1$ is an abstraction and Def. 6.(5), and the definition of $\gamma_3^{\mathcal{Q}}$.

<figure><img src="image_10.png" /></figure>

As an example one can compose the abstraction that is described in Sect. 2.2 between the model with identified particles and the model with anonymous particles, and the abstraction that is described in Sect. 2.3 between the model with anonymous particles and anonymous fragments so as to get an abstrac-
tion between the model with identified particles and the model with anonymous
fragments.

Conversely, provided some compatibility requirements, one can decompose an
abstraction between the systems $S^b$ and $S^\sharp$, by providing an abstraction between
the systems $S^b$ and $S$. More precisely, let us denote $S^b = (Q^b, \mathcal{L}^b, \to_b, w, \mathcal{I}, \pi_0)$,
$S = (Q, \mathcal{L}, \to, w, \mathcal{I}, \pi_0)$, and $S^\sharp = (Q^\sharp, \mathcal{L}^\sharp, \rightsquigarrow, w^\sharp, \mathcal{I}^\sharp, \pi_0^\sharp)$, and let us consider six
mappings $\beta_1^\mathcal{L}, \beta_1^Q, \gamma_1^Q, \beta_2^\mathcal{L}, \beta_2^Q$, and $\gamma_2^Q$ such that $A_1 := (S^b, S^\sharp, \beta_1^\mathcal{L}, \beta_1^Q, \gamma_1^Q)$ and
$A_2 := (S^b, S, \beta_2^\mathcal{L}, \beta_2^Q, \gamma_2^Q)$ are two abstractions which satisfy:

1. for any $q_1^b, q_2^b \in Q^b$ such that $\beta_2^Q(q_1^b) = \beta_2^Q(q_2^b)$, we have: $\beta_1^Q(q_1^b) = \beta_1^Q(q_2^b)$;

2. for any $\lambda_1^b, \lambda_2^b \in Q^b$ such that $\beta_2^\mathcal{L}(\lambda_1^b) = \beta_2^\mathcal{L}(\lambda_2^b)$, we have: $\beta_1^\mathcal{L}(\lambda_1^b) = \beta_1^\mathcal{L}(\lambda_2^b)$;

3. for any $q_1^b, q_2^b \in Q^b$ such that $\beta_2^Q(q_1^b) = \beta_2^Q(q_2^b)$, we have:

$$
\gamma_1^Q(\beta_1^Q(q_1^b))(q_1^b) \cdot \gamma_2^Q(\beta_2^Q(q_2^b))(q_2^b) = \gamma_1^Q(\beta_1^Q(q_2^b))(q_2^b) \cdot \gamma_2^Q(\beta_2^Q(q_1^b))(q_1^b).
$$

**Proposition 3 (factorization).** The tuple $A_3 := (S, S^\sharp, \beta_3^\mathcal{L}, \beta_3^Q, \gamma_3^Q)$ where:
$\beta_3^\mathcal{L}(\lambda)$ is defined as $\beta_1^\mathcal{L}(\lambda^b)$ for a given $\lambda^b \in \mathcal{L}^b$ such that $\beta_2^\mathcal{L}(\lambda^b) = \lambda$; $\beta_3^Q(q)$ is
defined as $\beta_1^Q(q^b)$ for a given $q^b \in \mathcal{Q}^b$ such that $\beta_2^Q(q^b) = q$; and $\gamma_3^Q(q^\sharp)(q)$ is
defined by:

$$
\gamma_3^Q(q^\sharp)(q) = \sum_{q^b} \left( \gamma_1(q^\sharp)(q^b) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^b) = q \right);
$$

is also an abstraction.

Moreover, $A_3$ is called the factorization of $A_1$ by $A_2$, which is denoted by $A_1 \setminus A_2$.

Intuitively, the abstraction $A_1$ can be factorized by the abstraction $A_2$ only if
the abstraction $A_1$ is coarser than $A_2$, that is to say that each pair of states (or
transition labels) which cannot be distinguished in the abstraction $A_2$, cannot
be distinguished in the abstraction $A_1$ either. Moreover, the property about $\gamma_1^Q$
and $\gamma_2^Q$ is another necessary condition for an abstraction $A_3$ such that $A_1 =$
$A_3 \circ A_2$ to exists (by definition of the concretization function of a composition
of abstraction).

Now we give the proof for Prop. 3.

Proof. Let us prove first that $\beta_3^Q$ and $\beta_3^\mathcal{L}$ are well-defined. Let $q \in \mathcal{Q}$ and $q_1^b, q_2^b \in \mathcal{Q}^b$ be such that: $\beta_2^Q(q_1^b) = q = \beta_2^Q(q_2^b)$. Then by assumption, we have: $\beta_1^Q(q_1^b) = \beta_1^Q(q_2^b)$. Moreover, since $A_2$ is an abstraction and by Def. 6.(1), $\beta_2^Q$ is onto: it follows that there exists $q^b$ such that $\beta_2^Q(q^b) = q$. So $\beta_3^Q$ is well-defined. In the same way, we can prove that $\beta_3^\mathcal{L}$ is well-defined.

Let us now prove that $A_3$ is an abstraction:

1. Let $q^\sharp$ be an element in $Q^\sharp$.

By Def. 6.(1) and since $A_1$ is an abstraction, there exists an element $q^b$ in
$Q^b$ such that $\beta_1^Q(q^b) = q^\sharp$. Then by definition of $\beta_3^Q$ and because $\beta_2^Q(q^b) =$
$\beta_2^Q(q^b)$, we have: $\beta_3^Q(\beta_2^Q(q^b)) = q^\sharp$. As a consequence, the mapping $\beta_3^Q$ is
onto. The same way, the mapping $\beta_3^\mathcal{L}$ is onto as well.
2. Let $q^\sharp$ be an element in $\mathcal{Q}^\sharp$.

Let $q \in \mathcal{Q}$ be such that: $\gamma_3^Q(q^\sharp)(q) > 0$.
We have, by definition of $\gamma_3^Q$:

$$ \sum_{q^b} (\gamma_1^Q(q^\sharp)(q^b) \mid q^b \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^b) = q) > 0. $$

So there exists $q^b \in \mathcal{Q}^b$ such that $\beta_2^Q(q^b) = q$ and $\gamma_1^Q(q^\sharp)(q^b) > 0$. It follows, since $A_1$ is an abstraction and by Def. 6.(2), that: $\beta_1^Q(q^b) = q^\sharp$. Then, by definition of $\beta_3^Q$, we have: $\beta_3^Q(q) = \beta_1^Q(q^b) = q^\sharp$.

Moreover, for any element $q \in \mathcal{Q}$ such that $\beta_3(q) = q^\sharp$, there exists an element $q^b \in \mathcal{Q}^b$ such that $\beta_2(q^b) = q$ and $\beta_1(q^b) = q^\sharp$. So the set of the elements $q \in \mathcal{Q}$ such that $\beta_3(q) = q^\sharp$ is finite, otherwise the set of the elements $q^b \in \mathcal{Q}^b$ such that $\beta_1(q^b) = q^\sharp$ would be infinite which is a contradiction since $A_1$ is an abstraction and by Def. 6.(2).

Last,

$$ \begin{align*} & \sum_q (\gamma_3^Q(q^\sharp)(q) \mid q \in \mathcal{Q} \text{ s.t. } \beta_3^Q(q) = q^\sharp) \\ &= \sum_q \sum_{q^b} (\gamma_1(q^\sharp)(q^b) \mid q \in \mathcal{Q}, q^b \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^b) = q, \beta_3^Q(q) = q^\sharp) \\ &= \sum_{q^b} (\gamma_1(q^\sharp)(q^b) \mid q^b \in \mathcal{Q}^b \text{ s.t. } \beta_3^Q(\beta_2^Q(q^b)) = q^\sharp) \\ &= \sum_{q^b} (\gamma_1(q^\sharp)(q^b) \mid q^b \in \mathcal{Q}^b \text{ s.t. } \beta_1^Q(q^b) = q^\sharp) \\ &= 1 \end{align*} $$

In this computation, we have used (i) the definition of $\gamma_3^Q$; then (ii) variable elimination; then (iii) the definition of $\beta_3^Q$; and last (iv) the fact that $A_1$ is an abstraction and Def. 6.(2).

3. Let $q_1, q_2$ be two elements in $\mathcal{Q}$ such that $\beta_3^Q(q_1) = \beta_3^Q(q_2)$. By Def. 6.(1) and since $A_2$ is an abstraction, we can choose two elements $q_1^b$ and $q_2^b$ in $\mathcal{Q}^b$ such that $\beta_2^Q(q_1^b) = q_1$ and $\beta_2^Q(q_2^b) = q_2$. We have $\beta_3^Q(\beta_2^Q(q_1^b)) = q^\sharp$. So, by definition of $\beta_3^Q$, it follows that: $\beta_1^Q(q_1^b) = q^\sharp$. The same way, $\beta_1^Q(q_2^b) = q^\sharp$. As a consequence, we have: $\beta_1^Q(q_1^b) = \beta_1^Q(q_2^b)$. Then, since $A_1$ is an abstraction and by Def. 6.(3), we can conclude that $a(q_1^b) = a(q_2^b)$.

4. Let $q$ be an element in $\mathcal{Q}$. Since $A_2$ is an abstraction and by Def. 6.(1), there exists $q^b \in \mathcal{Q}^b$, such that $\beta_2^Q(q^b) = q$. Thus we have: $q \in \mathcal{I} \iff \beta_2^Q(q^b) \in \mathcal{I}$. Since $A_2$ is an abstraction and by Def. 6.(4), we have: $\beta_2^Q(q^b) \in \mathcal{I} \iff q^b \in \mathcal{I}^b$. Since $A_1$ is an abstraction and by Def. 6.(4), it follows that: $q^b \in \mathcal{I}^b \iff \beta_1^Q(q^b) \in \mathcal{I}^\sharp$. Then by definition of $\beta_3^Q$, we have $\beta_1(q^b) = \beta_3(q)$. As a consequence, $q \in \mathcal{I} \iff \beta_3^Q(q) \in \mathcal{I}^\sharp$.

5. Let us prove the two implications of the equivalence.

Let $q^\sharp, q^\sharp'$ be two elements in $\mathcal{Q}^\sharp$, and $\lambda^\sharp$ be an element in $\mathcal{L}^\sharp$, such that $q^\sharp \stackrel{\lambda^\sharp}{\rightleftharpoons} q^\sharp'$. By Def. 6.(5) and since $A_1$ is an abstraction, there exist two elements $q^b, q^b' \in \mathcal{Q}^b$ and an element $\lambda^b \in \mathcal{L}^b$, such that $q^b \stackrel{\lambda^b}{\longrightarrow} q^b'$. Then, by Def. 6.(5)
and since $A_2$ is an abstraction, it follows that: $\beta_2^Q(q^b) \xrightarrow{\beta_2^Q(\lambda^b)} \beta_2^Q(q^{b'})$.

Conversely, let $q, q'$ be two elements in $\mathcal{Q}$ and $\lambda$ be an element in $\mathcal{L}$, such that $q \xrightarrow{\lambda} q'$. By Def. 6.(5) and since $A_2$ is an abstraction, there exist two elements $q^b, q^{b'} \in \mathcal{Q}^b$ and an element $\lambda^b \in \mathcal{L}^b$, such that $q^b \xrightarrow{\lambda^b} q^{b'}$. Then, by Def. 6.(5) and since $A_1$ is an abstraction, it follows that: $\beta_1^Q(q^b) \xrightarrow{\beta_1^Q(\lambda^b)} \beta_1^Q(q^{b'})$.

6. Let $q$ be an element in $\mathcal{Q}$. We have:

$$ \pi_0(q) = \left( \sum_{q^b} \left( \gamma_2^Q(q)(q^b) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^b) = q \right) \right) \cdot \pi_0(q) $$

$$ \pi_0(q) = \sum_{q^b} \left( \gamma_2^Q(q)(q^b) \cdot \pi_0(q) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^b) = q \right) $$

$$ \pi_0(q) = \sum_{q^b} \left( \gamma_2^Q(\beta_2^Q(q^b))(q^b) \cdot \pi_0(\beta_2(q^b)) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^b) = q \right) $$

$$ \pi_0(q) = \sum_{q^b} \left( \pi_0^b(q^b) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^b) = q \right) $$

$$ \pi_0(q) = \sum_{q^b} \left( \gamma_1^Q(\beta_1^Q(q^b))(q^b) \cdot \pi_0^\sharp(\beta_1^Q(q^b)) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^b) = q \right) $$

$$ \pi_0(q) = \left( \sum_{q^b} \left( \gamma_1^Q(\beta_1^Q(q^b))(q^b) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^b) = q \right) \right) \cdot \pi_0^\sharp(\beta_1^Q(q^b)) $$

$$ \pi_0(q) = \gamma_3(\beta_3^Q(q))(q) \cdot \pi_0^\sharp(\beta_3^Q(q)) $$

In this computation, we have used (i) the fact that $A_2$ is an abstraction and Def. 6.(2); then (ii) formal distribution; then (iii) replacement of $q$ with $\beta_2(q^b)$; then (iv) the fact that $A_2$ is an abstraction and Def. 6.(6); then (v) the fact that $A_1$ is an abstraction and Def. 6.(6); then (vi) factorization; and last (vii) the definition of $\gamma_3^Q$.

7. Let $q^\sharp, q^{\sharp'}$ be two elements in $\mathcal{Q}^\sharp$, and $\lambda^\sharp$ be an element in $\mathcal{L}^\sharp$, such that $q^\sharp \xrightarrow{\lambda^\sharp} q^{\sharp'}$. Let $q^\star$ be an element in $\mathcal{Q}$ such that $\beta_3^Q(q^\star) = q^{\sharp'}$.

We first prove that, for any $q^b \in \mathcal{Q}^b$ such that $q^\sharp = \beta_1^Q(q^b)$. We have:

$$ \gamma_1(q^\sharp)(q^b) = \gamma_3(q^\sharp)(\beta_2^Q(q_2^b)) \cdot \gamma_2(\beta_2^Q(q^b))(q^b). \quad (1) $$

By definition of $\gamma_3^Q$, we have:

$$ \gamma_3^Q(q^\sharp)(\beta_2(q^b)) = \sum_{q^{b'}} \left( \gamma_1^Q(q^\sharp)(q^{b'}) \middle| q^{b'} \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^{b'}) = \beta_2^Q(q^b) \right). $$

Then,

$$ \gamma_3^Q(q^\sharp)(\beta_2(q^b)) \cdot \gamma_2(\beta_2^Q(q^b))(q^b) = \sum_{q^{b'}} \left( \gamma_1^Q(q^\sharp)(q^{b'}) \cdot \gamma_2(\beta_2^Q(q^b))(q^b) \middle| q^{b'} \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^{b'}) = \beta_2^Q(q^b) \right). $$

Let us consider $q^{b'} \in \mathcal{Q}^b$ such that $\beta_2^Q(q^{b'}) = \beta_2^Q(q^b)$, we have, by assumption over $\gamma_1^Q$ and $\gamma_2^Q$:

$$ \gamma_1^Q(\beta_1^Q(q^b))(q^b) \cdot \gamma_2^Q(\beta_2^Q(q^{b'}))(q^{b'}) = \gamma_1^Q(\beta_1^Q(q^{b'}))(q^{b'}) \cdot \gamma_2^Q(\beta_2^Q(q^b))(q^b). $$
Then, by assumption over $\beta_1^Q$ and $\beta_2^Q$, and because $\beta_2^Q(q^{b'}) = \beta_2^Q(q^b)$, we
have $\beta_1^Q(q^{b'}) = \beta_1^Q(q^b) = q^\sharp$. It follows that:

$$
\gamma_1^Q(q^\sharp)(q^b) \cdot \gamma_2^Q(\beta_2^Q(q^b))(q^{b'}) = \gamma_1^Q(q^\sharp)(q^{b'}) \cdot \gamma_2^Q(\beta_2^Q(q^b))(q^b).
$$

As a consequence, we have:

$$
\begin{align*}
& \gamma_3^Q(q^\sharp)(\beta_2(q^b)) \cdot \gamma_2(\beta_2^Q(q^b))(q^b) \\
&= \sum_{q^{b'}} \left( \gamma_1^Q(q^\sharp)(q^b) \cdot \gamma_2(\beta_2^Q(q^{b'}))(q^{b'}) \mid q^{b'} \in Q^b \text{ s.t. } \beta_2^Q(q^{b'}) = \beta_2^Q(q^b) \right) \\
&= \gamma_1^Q(q^\sharp)(q^b) \cdot \sum_{q^{b'}} \left( \gamma_2(\beta_2^Q(q^{b'}))(q^{b'}) \mid q^{b'} \in Q^b \text{ s.t. } \beta_2^Q(q^{b'}) = \beta_2^Q(q^b) \right).
\end{align*}
$$

Then, since, $\gamma_2(\beta_2^Q(q^{b'}))$ is a finite distribution, we get that:

$$
\gamma_3^Q(q^\sharp)(\beta_2(q^b)) \cdot \gamma_2(\beta_2^Q(q^b))(q^b) = \gamma_1^Q(q^\sharp)(q^b),
$$

which was our intermediary goal.

Then, let us denote $\mathcal{X} = w^{\sharp}(q^{\sharp}, \lambda^{\sharp}) \cdot \gamma_3^Q(q^{\sharp'})(q^*)$.
By definition of $\gamma_3^Q$, we have:

$$
\mathcal{X} = \sum_{q^{b'}} \left( \gamma_1^Q(q^{\sharp'})(q^{b'}) \cdot w^{\sharp}(q^{\sharp}, \lambda^{\sharp}) \middle| q^{b} \in \mathcal{Q}^b \text{ s.t. } \beta_2^Q(q^{b'}) = q^* \right).
$$

Then, since $A_1$ is an abstraction and by Def. 6.(7), $\mathcal{X}$ is equal to:

$$
\sum_{q^{b'}} \sum_{q^b} \sum_{\lambda^b} \left( \gamma_1^Q(q^\#)(q^b) \cdot w^b(q^b, \lambda^b) \left| \begin{array}{l} q^{b'}, q^b \in \mathcal{Q}^b, \lambda^b \in \mathcal{L}^b \text{ s.t.} \\ \beta_1^Q(q^b) = q^\#, \beta_1^Q(q^{b'}) = q^{b'}, \\ \beta_1^L(\lambda^b) = \lambda^\#, \beta_2^Q(q^{b'}) = q^*, \\ q^b \xrightarrow{\lambda^b} q^{b'} \end{array} \right. \right)
$$

By splitting the sum $\mathcal{X}$ we can write:

$$
\mathcal{X} = \sum_{q^{b'}} \sum_q \sum_{\lambda} (\text{term}(q^{b'}, q, \lambda) | q^{b'} \in \mathcal{Q}^b, q \in \mathcal{Q}, \lambda \in \mathcal{L}).
$$

where, for any triple $(q^{b'}, q, \lambda) \in \mathcal{Q}^b \times \mathcal{Q} \times \mathcal{L}$, the expression $\text{term}(q^{b'}, q, \lambda)$
is defined as:

$$
\sum_{q^b} \sum_{\lambda^b} \left( \gamma_1^Q(q^\#)(q^b) \cdot w^b(q^b, \lambda^b) \left| \begin{array}{l} q^b \in \mathcal{Q}^b, \lambda^b \in \mathcal{L}^b \text{ s.t. } \beta_1^Q(q^b) = q^\sharp, \\ \beta_1^Q(q^{b'}) = q^{\sharp'}, \beta_1^L(\lambda^b) = \lambda^\sharp, \\ \beta_2^Q(q^b) = q, \beta_2^L(\lambda^b) = \lambda, \\ \beta_2^Q(q^{b'}) = q^*, q^b \xrightarrow{\lambda^b} q^{b'} \end{array} \right. \right)
$$

But, for any triple $(q^{b'}, q, \lambda) \in \mathcal{Q}^b \times \mathcal{Q} \times \mathcal{L}$ such that $\text{term}(q^{b'}, q, \lambda) \neq 0$, we
have: $\beta_1^Q(q^{b'}) = q^{\sharp'}$; $\beta_2^Q(q^{b'}) = q^*$, $\beta_3^Q(q) = q^\sharp$ (since $\beta_1^Q(q^b) = q^\sharp$; $\beta_2^Q(q^b) = q$
and by definition of $\beta_3^Q$); $\beta_3^L(\lambda) = \lambda^\sharp$ (the same way); and $q \xrightarrow{\lambda} \beta_2(q^{b'})$ (since
$\beta_2^Q(q^b) = q, \beta_2^L(\lambda^b) = \lambda, \beta_2^Q(q^{b'}) = q^*, q^b \xrightarrow{\lambda^b} q^{b'}$ and by definition 6.5).

Thus we have:

$$ \mathcal{X} = \sum_{q^{b'}} \sum_q \sum_{\lambda} \left( \text{term}(q^{b'}, q, \lambda) \left| \begin{array}{l} q^{b'} \in \mathcal{Q}^b, q \in \mathcal{Q}, \lambda \in \mathcal{L} \text{ s.t.} \\ \beta_3^Q(q) = q^\sharp, \\ \beta_3^L(\lambda) = \lambda^\sharp, \beta_1^Q(q^{b'}) = q^{b'}, \\ \beta_2^Q(q^{b'}) = q^*, q \xrightarrow{\lambda} \beta_2(q^{b'}) \end{array} \right. \right). $$

Let us consider a triple $(q^{b'}, q, \lambda) \in \mathcal{Q}^b \times \mathcal{Q} \times \mathcal{L}$ such that: $\beta_3^Q(q) = q^\sharp$, $\beta_3^L(\lambda) = \lambda^\sharp$, $\beta_1^Q(q^{b'}) = q^{b'}, \beta_2^Q(q^{b'}) = q^*$, and $q \xrightarrow{\lambda} \beta_2(q^{b'})$.

We have:

$$ \text{term}(q^{b'}, q, \lambda) = \sum_{q^b} \sum_{\lambda^b} \left( \gamma_1^Q(q^\sharp)(q^b) \cdot w^b(q^b, \lambda^b) \left| \begin{array}{l} q^b \in \mathcal{Q}^b, \lambda^b \in \mathcal{L}^b \\ \text{s.t.} \\ \beta_2^Q(q^b) = q, \\ \beta_2^L(\lambda^b) = \lambda, \\ q^b \xrightarrow{\lambda^b} q^{b'} \end{array} \right. \right). $$

By (9(a)), the expression term($q^{b'}, q, \lambda$) is equal to:

$$ \sum_{q^b} \sum_{\lambda^b} \left( \gamma_3^Q(q^\sharp)(q) \cdot \gamma_2^Q(q)(q^b) \cdot w^b(q^b, \lambda^b) \left| \begin{array}{l} q^b \in \mathcal{Q}^b, \lambda^b \in \mathcal{L}^b \text{ s.t.} \\ \beta_2^Q(q^b) = q, \\ \beta_2^L(\lambda^b) = \lambda, \\ q^b \xrightarrow{\lambda^b} q^{b'} \end{array} \right. \right). $$

Then, since $A_2$ is an abstraction, by Def. 6.(7), and because $\beta_2(q^{b'}) = q^*$, it follows that:

$$ \text{term}(q^{b'}, q, \lambda) = \gamma_3^Q(q^\sharp)(q) \cdot \gamma_2^Q(q^*)(q^{b'}) \cdot w(q, \lambda). $$

Then, since $\gamma_2(\beta_2(q^{b'}))$ is a finite distribution, we get that:

$$ \mathcal{X} = \sum_q \sum_{\lambda} \left( \gamma_3^Q(q^\sharp)(q) \cdot w(q, \lambda) \left| \begin{array}{l} q \in \mathcal{Q}, \lambda \in \mathcal{L} \text{ s.t. } \beta_3^Q(q) = q^\sharp, \\ \beta_3^L(\lambda) = \lambda^\sharp, q \xrightarrow{\lambda} q^* \end{array} \right. \right). $$

<figure><img src="image_11.png" /></figure>

As expected, abstraction composition is the inverse of abstraction factorization (and conversely), as stated by the following algebraic properties:

*Property 1 (Algebraic identities).* Let $A_1, A_2$ be two abstractions. The following properties are satisfied:

1. if $A_1 \setminus A_2$ is well-defined, then $(A_1 \setminus A_2) \circ A_2$ is well-defined and $(A_1 \setminus A_2) \circ A_2 = A_1$;

2. if $A_2 \circ A_1$ is well-defined, then $(A_2 \circ A_1) \setminus A_1$ is well-defined and $(A_2 \circ A_1) \setminus A_1 = A_2$.
<figure><img src="image_12.png" /><figcaption>Fig. 9. Factorization is the inverse of composition (and conversely).</figcaption></figure>

*Proof.* Let $S^b = (Q^b, \mathcal{L}^b, \to_b, w^b, \mathcal{I}^b, \pi_0^b)$, $S = (Q, \mathcal{L}, \to, w, \mathcal{I}, \pi_0)$, and $S^\sharp = (Q^\sharp, \mathcal{L}^\sharp, \rightsquigarrow, w^\sharp, \mathcal{I}^\sharp, \pi_0^\sharp)$ be three weighted labeled transition systems.

1. We assume (eg see Fig. 9(a)) that $A_1$ is an abstraction between $S^b$ and $S^\sharp$, and $A_2$ is an abstraction between $S^b$ and $S$, such that $A_1 \setminus A_2$ is well-defined. We denote $A_1 = (S^b, S^\sharp, \beta_1^\mathcal{L}, \beta_1^\mathcal{Q}, \gamma_1^\mathcal{Q})$ and $A_2 = (S^b, S, \beta_2^\mathcal{L}, \beta_2^\mathcal{Q}, \gamma_2^\mathcal{Q})$. We also denote $A_3 = A_1 \setminus A_2 = (S, S^\sharp, \beta_3^\mathcal{L}, \beta_3^\mathcal{Q}, \gamma_3^\mathcal{Q})$. Then, the composition between $A_2$ and $A_3$ is well-defined: we denote $A_4 = A_3 \circ A_2 = (S^b, S^\sharp, \beta_4^\mathcal{L}, \beta_4^\mathcal{Q}, \gamma_4^\mathcal{Q})$. Our goal is to prove that $A_1 = A_4$, that is to say that $\beta_1^\mathcal{L} = \beta_4^\mathcal{L}, \beta_1^\mathcal{Q} = \beta_4^\mathcal{Q}$, and $\gamma_1^\mathcal{Q} = \gamma_4^\mathcal{Q}$.

- Let $\lambda^b$ be a transition label in $\mathcal{L}^b$. Since $A_4 = A_3 \circ A_2$, we have: $\beta_4^\mathcal{L}(\lambda^b) = \beta_3^\mathcal{L}(\beta_2^\mathcal{L}(\lambda^b))$. Then, by definition of $\beta_3^\mathcal{L}$ since $A_3 = A_1 \setminus A_2$ and because $\beta_2^\mathcal{L}(\lambda^b) = \beta_2^\mathcal{L}(\lambda^b)$, we get that: $\beta_3^\mathcal{L}(\beta_2^\mathcal{L}(\lambda^b)) = \beta_1^\mathcal{L}(\lambda^b)$. So $\beta_4^\mathcal{L}(\lambda^b) = \beta_1^\mathcal{L}(\lambda^b)$.

As a consequence, $\beta_4^\mathcal{L} = \beta_1^\mathcal{L}$.

- With the same kind of proof, we can show that: $\beta_4^\mathcal{Q} = \beta_1^\mathcal{Q}$.

- Let us consider $q^b \in Q^b$ and $q^\sharp \in Q^\sharp$.

We want to prove that $\gamma_4(q^\sharp)(q^b) = \gamma_1(q^\sharp)(q^b)$.

Whenever $\beta_4^\mathcal{Q}(q^b) \neq q^\sharp$, we know, since $\beta_1^\mathcal{Q} = \beta_4^\mathcal{Q}$, that $\beta_1^\mathcal{L}(q^b) \neq q^\sharp$. Since $A_1$ and $A_4$ are two abstractions, and by Def. 6.(2), it follows that $\gamma_4^\mathcal{Q}(q^\sharp)(q^b) = 0 = \gamma_1^\mathcal{Q}(q^\sharp)(q^b)$.

Whenever $\beta_4^\mathcal{Q}(q^b) = q^\sharp$, we know, since $\beta_1^\mathcal{Q} = \beta_4^\mathcal{Q}$, that $\beta_1^\mathcal{L}(q^b) = q^\sharp$.

Then, since $A_4 = A_3 \circ A_2$, we have by definition of $\gamma_4^\mathcal{Q}$:

$$ \gamma_4^\mathcal{Q}(q^\sharp)(q^b) = \gamma_3^\mathcal{Q}(q^\sharp)(\beta_2^\mathcal{Q}(q^b) \cdot \gamma_2^\mathcal{Q}(\beta_2^\mathcal{Q}(q^b))(q^b)). $$

Then, since $A_3 = A_1 \setminus A_2$ and by definition of $\gamma_3^\mathcal{Q}$, we have:

$$ \gamma_4^\mathcal{Q}(q^\sharp)(q^b) = \sum_{q^{b'}} \left( \gamma_1^\mathcal{Q}(q^\sharp)(q^{b'}) \middle| \begin{array}{l} q^{b'} \in Q^b \text{ s.t.} \\ \beta_2^\mathcal{Q}(q^{b'}) = \beta_2^\mathcal{Q}(q^{b'}) \end{array} \right) \cdot \gamma_2^\mathcal{Q}(\beta_2^\mathcal{Q}(q^b))(q^b). $$
Thus,

$$ \gamma_4^Q(q^\#)(q^b) = \sum_{q^{b'}} \left( \gamma_1^Q(q^\#)(q^{b'}) \cdot \gamma_2(\beta_2^Q(q^b))(q^b) \middle|_{\substack{q^{b'} \in Q^b \text{ s.t.} \\ \beta_2^Q(q^{b'}) = \beta_2^Q(q_2^b)}} \right). $$

But, since $A_1 \setminus A_2$ is well-defined, for any $q^{b'} \in Q^b$ such that $\beta_2^Q(q^b) = \beta_1^Q(q^{b'})$, we have:

$$ \gamma_1^Q(\beta_1^Q(q^{b'}))(q^{b'}) \cdot \gamma_2^Q(\beta_2^Q(q^b))(q^b) = \gamma_1^Q(\beta_1^Q(q^b))(q^b) \cdot \gamma_2^Q(\beta_2^Q(q^{b'}))(q^{b'}). $$

But since $A_1 \setminus A_2$ is well-defined and $\beta_2^Q(q^b) = \beta_2^Q(q^{b'})$, we have: $q^\# = \beta_1^Q(q^b) = \beta_1^Q(q^{b'})$. Thus, we have:

$$ \gamma_4^Q(q^\#)(q^b) = \sum_{q^{b'}} \left( \gamma_2^Q(\beta_2^Q(q^b)(q^{b'}) \cdot \gamma_1^Q(q^\#)(q^b)) \middle|_{\substack{q^{b'} \in Q^b \text{ s.t.} \\ \beta_2^Q(q^{b'}) = \beta_2^Q(q_2^b)}} \right). $$

Then:

$$ \gamma_4^Q(q^\#)(q^b) = \sum_{q^{b'}} \left( \gamma_2^Q(\beta_2^Q(q^b)(q^{b'}) \middle|_{\substack{q^{b'} \in Q^b \text{ s.t.} \\ \beta_2^Q(q^{b'}) = \beta_2^Q(q_2^b)}} \right) \cdot \gamma_1^Q(q^\#)(q^b). $$

Since $\gamma_2^Q(\beta_2^Q(q^b))$ is a finite distribution, we get that:

$$ \gamma_4^Q(q^\#)(q^b) = \gamma_1^Q(q^\#)(q^b). $$

Thus $\gamma_4^Q = \gamma_1^Q$.

We can conclude that $A_4 = A_1$.

2. We assume (eg see Fig. 9(b)) that $A_1$ is an abstraction between $S^b$ and $S$, and $A_2$ is an abstraction between $S$ and $S^\#$. We denote $A_1 = (S^b, S^\#, \beta_1^L, \beta_1^Q, \gamma_1^Q)$ and $A_2 = (S^b, S, \beta_2^L, \beta_2^Q, \gamma_2^Q)$. We also denote $A_3 = A_2 \circ A_1 = (S^b, S^\#, \beta_3^L, \beta_3^Q, \gamma_3^Q)$.

Let us prove that $A_3 \setminus A_1$ is well-defined.

(a) Let $q_1^b, q_2^b \in Q^b$ such that $\beta_1^Q(q_1^b) = \beta_1^Q(q_2^b)$.

Since $A_3 = A_2 \circ A_1$, we have, by definition of $\beta_3^Q$:

$$ \beta_3^Q(q_1^b) = \beta_2^Q(\beta_1^Q(q_1^b)) = \beta_2^Q(\beta_1^Q(q_2^b)) = \beta_3^Q(q_2^b). $$

(b) The same way, for any $\lambda_1^b, \lambda_2^b \in \mathcal{L}^b$, such that $\beta_1^L(\lambda_1^b) = \beta_1^L(\lambda_2^b)$, we have: $\beta_3^L(\lambda_1^b) = \beta_3^L(\lambda_2^b)$.

(c) Let $q_1^b, q_2^b \in Q^b$ such that $\beta_1^Q(q_1^b) = \beta_1^Q(q_2^b)$.

Since $A_3 = A_2 \circ A_1$ and by definition of $\gamma_3^Q$, we have:

$$ \gamma_3^Q(\beta_3^Q(q_1^b))(q_1^b) = \gamma_1^Q(\beta_1^Q(q_1^b))(q_1^b) \cdot \gamma_2^Q(\beta_3^Q(q_1^b))(\beta_1^Q(q_1^b)); $$

$$ \gamma_3^Q(\beta_3^Q(q_2^b))(q_2^b) = \gamma_1^Q(\beta_1^Q(q_2^b))(q_2^b) \cdot \gamma_2^Q(\beta_3^Q(q_2^b))(\beta_1^Q(q_2^b)). $$
Then:

$$
\begin{align*}
& \gamma_3^Q(\beta_3^Q(q_1^b))(q_1^b) \cdot \gamma_1^Q(\beta_1^Q(q_2^b))(q_2^b) \\
&= (\gamma_1^Q(\beta_1^Q(q_1^b))(q_1^b) \cdot \gamma_2^Q(\beta_3^Q(q_1^b))(\beta_1^Q(q_1^b))) \cdot \gamma_1^Q(\beta_1^Q(q_2^b))(q_2^b) \\
&= \gamma_1^Q(\beta_1^Q(q_1^b))(q_1^b) \cdot (\gamma_1^Q(\beta_1^Q(q_2^b))(q_2^b) \cdot \gamma_2^Q(\beta_3^Q(q_1^b))(\beta_1^Q(q_1^b))) \\
&= \gamma_1^Q(\beta_1^Q(q_1^b))(q_1^b) \cdot \gamma_3^Q(\beta_3^Q(q_2^b))(q_2^b).
\end{align*}
$$

Thus, $A_3 \setminus A_1$ is well defined.

We denote $A_4 = A_3 \setminus A_1 = (S, S^\# , \beta_4^L, \beta_4^Q, \gamma_4^Q)$.

Let us prove that $A_4 = A_2$.

- Let $\lambda$ be an element in $\mathcal{L}$. Since $A_1$ is an abstraction and by Def. 6.(1), there exists an element in $\lambda^b \in \mathcal{L}^b$, such that $\beta_1^L(\lambda^b) = \lambda$. Then, since $A_4 = A_3 \setminus A_1$ and by definition of $\beta_4^L$, we have, $\beta_4^L(\lambda) = \beta_3^L(\lambda^b)$. But $A_3 = A_2 \circ A_1$. So by definition of $\beta_3^L$, it follows that $\beta_3^L(\lambda^b) = \beta_2^L(\beta_1^L(\lambda_b)) = \beta_2^L(\lambda)$. As a consequence, we have: $\beta_4^L(\lambda) = \beta_2^L(\lambda)$.

Thus, $\beta_1^L = \beta_2^L$.

- The same way, we can show that $\beta_4^Q = \beta_2^Q$.

- Let us consider $q \in \mathcal{Q}$ and $q^\# \in \mathcal{Q}^\#$.

We want to prove that $\gamma_4(q^\#)(q) = \gamma_2(q^\#)(q)$.

Whenever $\beta_4^Q(q) \neq q^\#$, we know, since $\beta_2^Q = \beta_4^Q$, that $\beta_2^Q(q) \neq q^\#$. Since $A_2$ and $A_4$ are two abstractions, and by Def. 6.(2), it follows that $\gamma_4^Q(q^\#)(q) = 0 = \gamma_2^Q(q^\#)(q)$.

Whenever $\beta_4^Q(q) = q^\#$, we know, since $\beta_1^Q = \beta_4^Q$, that $\beta_1^Q(q^b) = q^\#$. Then, since $A_4 = A_3 \setminus A_1$, we have by definition of $\gamma_4^Q$:

$$
\gamma_4^Q(q^\#)(q) = \sum_{q^b} \left( \gamma_3^Q(q^\#)(q^b) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_1(q^b) = q \right).
$$

Since, $A_3 = A_2 \circ A_1$ and by definition of $\gamma_3^Q$, we have:

$$
\gamma_4^Q(q^\#)(q) = \sum_{q^b} \left( \gamma_1^Q(\beta_1^Q(q^b))(q^b) \cdot \gamma_2^Q(q^\#)(\beta_1^Q(q^b)) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_1(q^b) = q \right)
$$

$$
\gamma_4^Q(q^\#)(q) = \sum_{q^b} \left( \gamma_1^Q(q)(q^b) \cdot \gamma_2^Q(q^\#)(q) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_1(q^b) = q \right)
$$

$$
\gamma_4^Q(q^\#)(q) = \gamma_2^Q(q^\#)(q) \cdot \sum_{q^b} \left( \gamma_1^Q(q)(q^b) \middle| q^b \in \mathcal{Q}^b \text{ s.t. } \beta_1(q^b) = q \right)
$$

Then, since $A_1$ is an abstraction and by Def. 6.(2), $\gamma_1^Q(q)$ is a finite probability distribution. So we have:

$$
\gamma_4^Q(q^\#)(q) = \gamma_2^Q(q^\#)(q).
$$

Thus $\gamma_4^Q = \gamma_2^Q$.

We can conclude that $A_4 = A_2$.

<figure><img src="image_13.png" /></figure>
<figure><img src="image_14.png" /><figcaption>Fig. 10. Syntax for agents</figcaption></figure>

# 4 Kappa

The next step is to instantiate the generic framework that we have proposed in Sect. 3 with a particular language. We focus our study to the models that are written in Kappa [22]. Kappa is a graph-rewriting-based language. As an example, it has been used for describing signaling pathways [17]. Indeed, Kappa has a graphical notation that eases the design of models and it is accompanied with various tools including simulation [19] and static analyses [20, 28].

Nevertheless, we use here a process-algebra notation, which facilitates the presentation of proofs. Moreover, we use a version of Kappa where agents are identified, in order to help us designing the non standard semantics.

## 4.1 Syntax

We fix a finite set of agent types $\mathcal{A}$, a finite set of sites $\mathcal{S}$, and a finite set $\mathbb{I}$ of non empty strings. We also consider two signature maps $\Sigma$ and $\Sigma'$ assigning a set of sites to each agent type such that for any agent type $A \in \mathcal{A}$, $\Sigma'(A) \subseteq \Sigma(A)$. Intuitively, $\Sigma(A)$ is the set of sites of any agent type $A$, whereas $\Sigma'(A)$ is the set of sites that can bear a modifiable internal state $w \in \mathbb{I}$ (such as a level of energy). The syntax of agents is given in Fig. 10.

An *agent identifier* $l$ belongs to the set $\mathbb{N}$ of natural numbers, or to a copy of $\overline{\mathbb{N}}$ of the set of natural numbers. Most agents will be identified by natural numbers. Identifiers in $\overline{\mathbb{N}}$ will be used temporary when agents are created, before a proper identifier in $\mathbb{N}$ is allocated.

An *interface* $\sigma$ is a sequence of sites with internal states and binding states; specifically one writes $x_\iota^\lambda$ for a site $x$ with internal state $\iota$ and binding state $\lambda$. The internal state can denote any modifiable information about the site (or the agent): for instance, it can be used to encode a phosphorylation level. If the internal state of a site $x$ in an agent of type $A$ is $\epsilon$, it means either that the site has no internal state (whenever $x \notin \Sigma'(A)$), or that we do not know the internal state. There are also several levels of information about binding states. We use a *question mark* `?` if we do not know anything about the binding state; we use the symbol `epsilon`, if we know that the site is *free*; otherwise it is *bound*. There are several levels of information about bound sites: we use a *site address* $A_l@x$ if we know the binding partner (this means that the site is bound to the site $x$ of
the agent $A$ with identifier $l$; we use a *binding type* $A@x$ if we only know that the partner is some site $x$ of some agent $A$; lastly we use a *wildcard bond* `—` if we only know that a site is bound but have no further information about its partner. We generally omit the symbol $\epsilon$ in examples.

An *agent* is given by a type $A$ in $\mathcal{A}$, an agent identifier $l$ and an interface $\sigma$. Such an agent is denoted by $A_l(\sigma)$. We also require that (i) a site $s$ occurs at most once within the interface of an agent; (ii) if site $s$ occurs in an agent $A_l(\sigma)$ then $s \in \Sigma(A)$; (iii) if site $s$ occurs in an agent $A_l(\sigma)$ with a non empty internal state, then $s \in \Sigma'(A)$.

An *expression* $E$ is a sequence of agents such that no two agents have both the same type and the same identifier. Furthermore, given an expression $E$ and an agent type $A \in \mathcal{A}$, we denote by $\text{agents}(E, A)$ the set of identifiers $l$ such that there is an agent $A$ in the expression $E$ with identifier $l$.

A *pattern* is an expression $E$ such that whenever the binding state of the site $x$ in the agent of type $A$ with identifier $l$ is $A'_l@x'$, then there exists an agent of type $A'$ with the identifier $l'$, moreover this agent has the site $x'$ in its interface, and the binding state of this site is $A_l@x$ (thus site addresses encode a pairing relation between some sites). A *mixture* $E$ is a non-empty pattern that is fully specified, ie each agent of type $A$ in a mixture $E$ documents its full interface $\Sigma(A)$, sites can only be free or bear a site address, and any sites in $\Sigma'(A)$ have a non empty internal state; moreover we also require that in a mixture $E$, for any agent type $A$, the set $\text{agents}(E, A)$ is either empty, or of the form $\{i | 1 \le i \le p\}$ (this way, the identifiers of the agents of a given type in a mixture are consecutive identifiers in $\mathbb{N}$ starting with 1; moreover, $p$ is the number of agents of type $A$ in the mixture). A pattern $E$ is said to be *disconnected* if there is a subsequence $E'$ of it that is a non-empty pattern. A *pattern component* is a connected pattern. A (non standard) *species* is a fully specified non-empty pattern component, or equivalently a connected mixture.

A rule is given by a pair of patterns $(E_\ell, E_r)$ and a rate $k$ (which is a non negative real number), that is written $E_\ell \xrightarrow{k} E_r$, with some additional constraints explained below. The left hand side (lhs) $E_\ell$ of a rule describes the agents taking part in it and various conditions on both their internal and binding states for the rule to apply. The right hand side (rhs) describes what the rule does.

**Definition 8.** In a rule $E_\ell \xrightarrow{k} E_r$, firstly agents in thelhs are identified with natural numbers $i \in \mathbb{N}$ and secondly the pattern $E_r$ is obtained from $E_\ell$ in the following stepwise fashion (the order matters):

- (i) *creation*: some agents $A_i^-(\sigma)$ with an agent identifier in $\overline{\mathbb{N}}$, with their full interfaces $\Sigma(A)$, with all sites free and with all sites $s \in \Sigma'(A)$ having a non empty internal state are added;

- (ii) *unbinding*: some occurrences of the wildcard `—` and some site addresses $A_i^-@n$ are removed;

- (iii) *deletion*: some agents with only free sites are removed;

- (iv) *modification*: some (non empty) internal states are replaced with (non empty) internal states;
- (v) binding: some free sites are bound pair-wise by using appropriate site addresses.

Agent types and identifiers ensure a 1-1 mapping correspondence between the agents in the rhs and in the rhs that are neither removed, nor created. Moreover, any two agents in correspondence $A_i(\sigma)$, $A'_i(\sigma')$ must have same agent type, ie $A = A'$, their interfaces $\sigma, \sigma'$ must show the same sites, and the sites which have a non empty interfaces are the same; moreover, their identifiers belong to $\mathbb{N}$.

Note that according to Def. 8 binding types can only be tested.

A system is given by a finite distribution of some initial mixtures, and a finite set of rules. If both $E_\ell \underset{k_1}{\stackrel{k_1}{\rightleftharpoons}} E_r$ and $E_r \underset{k_2}{\stackrel{k_2}{\rightleftharpoons}} E_\ell$ are in this set of rules, these rules are said to be reversible and written $E_\ell \underset{k_2}{\stackrel{k_1}{\rightleftharpoons}} E_r$.

**Example 1.** We can refactor in Kappa the example in Sect. 2: we set $\mathbb{I} = \{u, p\}$ ($u$ stands for unphosphorylated or deactivated, and $p$ for phosphorylated or activated) we set $\mathcal{A} = \{A, B\}$, $\mathcal{S} = \{x\}$, $\Sigma(A) = \Sigma'(A) = \Sigma(B) = \Sigma'(B) = \{x\}$. The molecular species $A_1^*B_1^*$ is now written $A_1(x_p^{B_1|x})$, $B_1(x_p^{A_1|x})$, and the rules emulating the earlier reactions are:

$$ 
\begin{align*}
A_1(x_u^?) &\underset{k_{A-}}{\overset{k_{A+}}{\rightleftharpoons}} A_1(x_p^?), \\
B_1(x_u^?) &\underset{k_{B-}}{\overset{k_{B+}}{\rightleftharpoons}} B_1(x_p^?), \\
A_1(x), B_1(x) &\underset{k_{A..B}}{\overset{k_{A+B}}{\rightleftharpoons}} A_1(x^{B_1|x}), B_1(x^{A_1|x}).
\end{align*}
$$

We notice that we have modeled complexation with only one rule. This amounts to say that we have assumed that the rate of complexation of two particles A and B does not depend on the state of the two particles A and B. In other words, we have assume that $k_{A+B} = k_{A^*+B^*}$. $\square$

## 4.2 Individuals-based semantics

Now we associate each model written in Kappa with a weighted labeled transition system (eg see Def. 1 on page 21). In the states of this weighted labeled transition system, agents are identified by some identifiers, in order to derive (eg see Def 5 on page 23) a so-called *individuals-based semantics*. This semantics is also called non-standard, because we keep more information than just the number of instances of each molecular species. Moreover, special care has to be taken about how identifiers are allocated when new agents are created, in order to ensure that two mixtures that are equivalent up to reindexing have the same probability to occur. More precisely, whenever new agents are created, their identifiers are inserted between already existing ones, shifting the identifiers of older agents. As a consequence, a given agent is not identified with the same
$$ \begin{array}{l} E, N_l(\sigma, s, s', \sigma') , E' \equiv E, N_l(\sigma, s', s, \sigma') , E' \\ E, a, a', E' \equiv E, a', a, E' \end{array} $$

(a) Structural congruence.

$$ \begin{array}{rcl} \iota_{\ell} & = & \iota, \epsilon \\ \lambda & = & \phi(\lambda_{\ell}) \\ N_l @ n & = & N @ n \\ N_l @ n & = & - \\ \lambda & = & ? \\ \iota & = & \iota_{\ell} \wedge \lambda \\ \sigma & = & \varepsilon \\ s & = & s_{\ell} \wedge \sigma \\ \sigma & = & \sigma_{\ell} \end{array} \quad \begin{array}{l} \iota[\epsilon] = \iota \\ \lambda[\epsilon] = \epsilon \\ (s, \sigma)[s_r, \sigma_r] = s[s_r], \sigma[\sigma_r] \\ N_l(\sigma)[N_l(\sigma_r)] = N_l(\sigma[\sigma_r]) \end{array} $$

(c) Agent matching.

$$ \begin{align*} \lambda &= \epsilon, N @ n, -, ? \implies \bar{\phi}(\lambda) = \lambda \\ \bar{\phi}(N_l @ n) &= N_{\phi(N,l)} @ n \\ \bar{\phi}(n_{\iota}^{\lambda}) &= n_{\iota}^{\bar{\phi}(\lambda)} \\ \bar{\phi}(s, \sigma) &= \bar{\phi}(s), \bar{\phi}(\sigma) \\ \bar{\phi}(N_l(\sigma)) &= N_{\phi(N,l)}(\bar{\phi}(\sigma)) \end{align*} $$

(b) Agent substitution.

$$ \begin{align*} \iota[\epsilon] &= \iota \\ \lambda[\epsilon] &= \epsilon \\ \lambda[N_l @ n] &= N_l @ n \\ \lambda[N_l @ n] &= \lambda \\ \lambda[-] &= \lambda \\ \lambda[?] &= \lambda \\ n_{\iota}^{\lambda}[n_{\iota r}^{\lambda r}] &= n_{\iota[\iota r]}^{\lambda[\lambda r]} \\ \sigma[\epsilon] &= \sigma \\ (s, \sigma)[s_r, \sigma_r] &= s[s_r], \sigma[\sigma_r] \\ N_l(\sigma)[N_l(\sigma_r)] &= N_l(\sigma[\sigma_r]) \end{align*} $$

(d) Agent replacement.

<caption>**Fig. 11.** Structural congruence, substitution, matching and replacement. Definitions are made by induction over the syntax.</caption>

identifier along a given trace. Nevertheless, whenever the identifier of an agent $a$ of a given type is less (remember that proper identifiers are totally ordered) than the identifier of an agent $a'$ of the same type, then this property holds until the agent $a$ or the agent $a'$ is removed.

First, we define the (non standard) states $Q^b$ of the system. For that purpose, we define a structural equivalence $\equiv$ as the smallest binary equivalence relation between expressions that satisfies the rules given in Fig. 11(a). These rules stipulate that neither the order of sites in interfaces nor the order of agents in expressions matters. Then we define $Q^b$ as the set of $\equiv$-equivalent classes of mixtures. In order to ease the notations, we usually denote an $\equiv$-equivalence class of expressions by one of its element.

We recall that the initial (non standard) states $I^b$ and the initial (non standard) state distribution $\pi_0^b$ were given when defining the system.

Now we define the (non standard) transition relation. We start by defining computation steps and we postpone the definition of labels and weights. Informally, to apply a rule $E_{\ell} \xrightarrow{k} E_{r}$ to a mixture $E$, one needs to embed $E_{\ell}$ into $E$. For that purpose, we define a substitution as a partial mapping $\phi$ between pairs $(A, l) \in A \times (\mathbb{N} \cup \bar{\mathbb{N}})$ of agent type/identifier and identifiers $l' \in \mathbb{N} \cup \bar{\mathbb{N}}$. A substitution $\phi$ can be applied with a pattern $E$ if, and only if, for any agent type $A \in A$, we have $(A, l) \in \text{dom}(\phi)$ for any agent identifier $l \in \text{agents}(E, A)$. Indeed applying a substitution $\phi$ consists in replacing agent identifier $l$ of agent of type $A$ with the agent identifier $\phi(A, l)$. This is formalized, in Fig. 11(b), by defining the extension $\bar{\phi}$ of $\phi$ to agents. Furthermore, a given substitution $\phi$ is into if, and only if, for any agent type $A$, and any two identifiers $l, l'$, we have $\phi(A, l) = \phi(A, l') \implies l = l'$. Roughly speaking, an into substitution $\phi$
is a candidate for identifying the agents of two patterns. More precisely, each agent $A_{l_\ell}(\sigma_\ell)$ in the first pattern can be identified with the agent $A_l(\sigma)$, if (i) identifiers are the same (ie $l = \phi(A, l_\ell)$) and (ii) the signature $\sigma$ contains more information than the signature $\bar{\phi}(\sigma_\ell)$. The second property is formalized by a matching relation $\models$ which is given in Fig. 11(c). Yet, since interfaces are defined up to permutations of sites, one may have to reorder the sites before applying the matching relation.

We can now properly define an embedding between two patterns. An embedding $\phi$ between two patterns $E_\ell$ and $E$ is an into substitution such that: (i) $\text{dom}(\phi) = \{(A, l) \mid A \in \mathcal{A}, l \in \text{agents}(E_\ell, A)\}$, (ii) and for any $(A, l) \in \text{dom}(\phi)$, there exists an agent $a'$ such that $a \equiv a'$ and $a' \models \bar{\phi}(a_\ell)$, where $a_\ell$ is the unique agent in $E_\ell$ of type $A$ and the identifier $l$ and $a$ the unique agent in $E$ of type $A$ and the identifier $\phi(A, l)$. Moreover, whenever both $E_\ell$ and $E$ are two mixtures, we say that $\phi$ is an *isomorphic embedding*. At last, whenever $\phi$ is an isomorphic embedding, the into substitution that is mapping each pair $(A, l)$ of agent name/identifier that belongs to the set $\{(A, l) \mid A \in \mathcal{A}, l \in \text{agents}(E, A)\}$ to the unique identifier $l'$ such that $\phi(A, l') = l$, is an embedding. We denote it by $\phi^{-1}$. We can check that $\phi^{-1}(\phi(E))$ is equal to the mixture $E$ and that $(\phi^{-1})^{-1} = \phi$. Given a pattern $E$, we define the number of symmetries in $E$ as the number of embeddings $\phi$ such as $E$ and $\phi(E)$ are $\equiv$-equivalent. We denote the number of symmetries of $E$ as $\text{sym}(E)$.

Now we define the impact of applying a rule $E_\ell \xrightarrow{k} E_r$ along a given embedding $\phi$ between the rhs $E_\ell$ of the rule and a mixture $E$. For that purpose we consider three kinds of agents:

- Agents $A_{i_\ell}(\sigma_\ell)$ are said to be preserved if, and only if, $A_{l_\ell}(\sigma_\ell)$ occurs in $E_\ell$ and there exists an interface $\sigma_r$ such that $A_{l_\ell}(\sigma_r)$ occurs in $E_r$;

- Agents $A_{l_r}(\sigma_r)$ are said to be created if, and only if, $A_{l_r}(\sigma_r)$ occurs in $E_r$, but there is no agent of type $A$ with identifier $l_r$ in $E_\ell$;

- Agents $A_{l_\ell}(\sigma_\ell)$ are said to be removed if, and only if, $A_{l_\ell}(\sigma_\ell)$ occurs in $E_\ell$, but there is no agent of type $A$ with identifier $l_\ell$ in $E_r$.

We want to extend the embedding $\phi$ so that it can be applied on both side of the rule. This means that we have to extend its definition in order to deal with the temporary identifiers of newly created agents. This is made by defining the into substitution $\phi^*$ over $\text{dom}(\phi) \cup (\mathcal{A} \times \overline{\mathbb{N}})$ by $\phi^*(A, i) = \phi(A, i)$ whenever $(A, i) \in \text{dom}(\phi)$ and $\phi^*(A, \bar{i}) = \bar{i}$ otherwise (ie $\phi^*$ preserves temporary identifiers).

Then, for any agent $A_{l_\ell}(\sigma_\ell)$ that is removed, the agent of type $A$ with identifier $\phi(A, l_\ell)$ is removed in $E$; for any agent $a_r$ that is created, the agent $\bar{\phi}^*(a_r)$ is added in $E$; last for any preserved agent $a_\ell$, we denote by $a_r$ and $a$ the agents in $E_r$ and $E$ which have the same name and the same identifier as the agent $a_\ell$, then we select an agent $a'$ (the choice does not matter) such that $a \equiv a'$ and $a' \models \bar{\phi}(a_\ell)$, then the agent $a$ is replaced with agent $a'[\bar{\phi}^*(a_r)]$, where $[\cdot]$ is a replacement function that is defined in Fig. 11(d).

We denote by $E[E_r]_\phi$ the so obtained pattern (which is well defined up to $\equiv$-equivalence).
One shall notice that $E[E_r]_\phi$ might be not a mixture. Firstly, there might be some pending bonds which are sites with a binding state of the form $A_l@x$ but, either the agent of type $A$ and identifier $l$ has been removed, or the site $x$ of the agent of type $A$ and identifier $l$ has been made free. Secondly, the set agents($E, A$) of identifiers of agents of a given type $A$ might not be of the form $\{i | 1 \le i \le p\}$, because some agents have been removed and/or some agents have been created (with an identifier in $\overline{\mathbb{N}}$).

In order to recover a mixture, we first remove pending bonds: we introduce the function **clean** between patterns, such that **clean**($E$) is obtained by replacing with the symbol $\epsilon$, each site address $A_l@x$ such that either there is no agent of type $A$ and identifier $l$ in $E$, or the site $x$ of the agent of type $A$ with identifier $l$ is free. Then, we reindex the expression and replace temporary identifiers (in $\overline{\mathbb{N}}$) with proper ones (in $\mathbb{N}$). Formally, let us introduce $E$ a pattern, we consider the set **shift**($E$) of into substitutions $\phi'$ such that: (i) for any agent type $A \in \mathcal{A}$, the set agents($\phi'(E), A$) is either empty, or of the form $\{i | 1 \le i \le p\}$ for a given $p \in \mathbb{N} \setminus \{0\}$ and (ii) for any agent type $A \in \mathcal{A}$, and any two identifiers $l, l'$ in $\mathbb{N} \cap \text{agents}(E', A)$, we have: $i < i' \implies \phi'(A, i) < \phi'(A, i')$. Roughly speaking, the relative order between proper identifiers is preserved, Then created agents are inserted with arbitrary proper identifiers and former proper identifiers are shifted to take into account agent removal and creation. We could not just have identified created agent with fresh identifiers, because it would have broken the fact that two mixtures having the same agents but distinct identifiers are equiprobable. It is worth noting, that this allocation heuristic would be inappropriate for a simulation algorithm (where it would be better to allocate fresh identifiers within a set of available ones). Yet it makes the proofs easier (building a simulation algorithm is not the purpose of our framework).

**Example 2.** We set $\mathcal{A} = \{A\}, \mathbb{I} = \{\}, \mathcal{S} = \{a, b\}, \Sigma(A) = \{a, b\}, \Sigma'(A) = \emptyset$. We consider the mixture $E = A_1(a^{A_2@b}, b^{A_3@a})$, $A_2(a, b^{A_1@a})$, $A_3(a^{A_1@b}, b)$ and the rule $A_1(a) \xrightarrow{k} A_1(a, b)$. Intuitively, this rule can be applied with an agent of type $A$, the site $a$ of which is free (whatever the state of the site $b$ is). Moreover, this rule removes the agent $A_1(a)$, and replace it with a new agent $A_1(a, b)$ of type $A$ with both site $a$ and $b$ free (in this rule, no agent is preserved).

There exists one embedding between the $\text{lhs } A_1(a)$ of the rule and the mixture $E$. Namely, $\phi = [A, 1 \mapsto 2]$ (neither the substitution $[A, 1 \mapsto 1]$, nor $[A, 1 \mapsto 3]$ is an embedding, since the site $a$ is free neither in the agent $A_1(a^{A_2@b}, b^{A_3@a})$, nor in the agent $A_3(a^{A_1@b}, b)$). Moreover, the expression $E[E_\ell]_{\phi_2}$ is equal to the expression $A_1(a^{A_2@b}, b^{A_3@a})$, $A_1(a, b)$, $A_3(a^{A_1@b}, b)$. This expression has a pending bond (on the site $a$ of agent $A_1$), which is removed by the primitive **clean**. Indeed the expression $\text{clean}(E[E_\ell]_{\phi_2})$ is equal to the expression $A_1(a, b^{A_3@a})$, $A_1(a, b)$, $A_3(a^{A_1@b}, b)$.

Then there are three choices for reindexing the agents, namely $\phi'_1 := [(A, 1) \mapsto 2; (A, 2) \mapsto 3; (A, \overline{1}) \mapsto 1]$, $\phi'_2 := [(A, 1) \mapsto 1; (A, 2) \mapsto 3; (A, \overline{1}) \mapsto 2]$, and $\phi'_3 := [(A, 1) \mapsto 1; (A, 2) \mapsto 2; (A, \overline{1}) \mapsto 3]$, depending whether we associate the identifier 1, 2, or 3 to the created agent. As a result, we get three possibles
mixture after having computed the rule along $\phi_2$:

$$ \overline{\phi}'_1(\text{clean}(E[E_r]_\phi)) = A_1(a,b), A_2(a,b^{A_3\@a}), A_3(a^{A_2\@b},b), $$

$$ \overline{\phi}'_2(\text{clean}(E[E_r]_\phi)) = A_1(a,b^{A_3\@a}), A_2(a,b), A_3(a^{A_1\@b},b), $$

$$ \overline{\phi}'_3(\text{clean}(E[E_r]_\phi)) = A_1(a,b^{A_2\@a}), A_2(a^{A_1\@b},b), A_3(a,b). $$

<figure><img src="image_15.png" /></figure>

Now we can define labels and labeled transitions. We shall notice that the impact of applying a rule $E_\ell \xrightarrow{k} E_r$ on a mixture $E$, is fully defined by the embedding $\phi$ between the rhs $E_\ell$ of the rule and the mixture $E$, and the substitution $\phi'$ (that allocates proper identifiers to created agents). So we define the set $\mathcal{L}^b$ of labels as the set of the tuples $(r, E, \phi, \phi')$ where $r$ is a rule $E_\ell \xrightarrow{k} E_r$, $E$ is a state in $\mathcal{Q}^b$, $\phi$ is an embedding between $E_\ell$ and $E$, and $\phi'$ is an into substitution in **shift** (clean $(E[E_r]_\phi)$). Moreover, we define the set of transitions $\rightarrow^b$, as the set of the tuples of the form:

$$ (E, (E_\ell \xrightarrow{k} E_r, E, \phi, \phi'), \overline{\phi'}(\text{clean}(E[E_r]_\phi))). $$

Last we define the weight of transitions. A rule is triggered according to the number of embeddings of its left hand side into the current mixture. Thus, the weight function is defined this way:

$$ w^b(E, (E_\ell \xrightarrow{k} E_r, E, \phi, \phi')) = \frac{k}{\text{sym}(E_\ell) \cdot \text{card}(\text{shift}(\text{clean}(E[E_r]_\phi)))}. $$

This way, the overall weight of all transitions for a given rule $E_\ell \xrightarrow{k} E_r$, mixture $E$, and embedding $\phi$ between $E_\ell$ and $E$, is equal to $\frac{k}{\text{sym}(E_\ell)}$ (as expected).

As a conclusion, the so constructed tuple satisfies Def. 1 (on page 21), as stated by the following theorem:

**Theorem 4.** The tuple $S^b = (\mathcal{Q}^b, \mathcal{L}^b, \rightarrow_b, w^b, \mathcal{I}^b, \pi_0^b)$ is a weighted labeled transition system.

*Proof (sketch).* The system is finitely branching because each state is finite and the number of rule is finite. As a consequence, the number of embeddings between the rhs of rules and any mixture is finite. All other requirements directly come from the definition.

<figure><img src="image_16.png" /></figure>
## 4.3 Population-based semantics

Indeed, the previous granularity of observation keeps too much information: as in the example of Sect. 2.2, we propose to abstract away agent identifiers, which amounts to consider mixtures up to isomorphic embeddings.

For that purpose we propose to induce the abstraction by an admissible pair of equivalence relations over non standard states and non standard labels. We introduce the binary equivalence relation ~Q> over non standard states as follows: given $q_1^b, q_2^b \in Q^b$, we say that $q_1^b$ and $q_2^b$ are equivalent up to an isomorphic embedding if, and only if, there exists an embedding $\psi$ such that $q_2^b \equiv \bar{\psi}(q_1^b)$. In such a case, we write $q_1^b \sim_{Q>} q_2^b$.

Then we introduce the binary equivalence relation ~L> over non standard transition labels. Given two non standard transition labels $\lambda_1 = (r_1, q_1^b, \phi_1, \phi_1')$ and $\lambda_1 = (r_2, q_2^b, \phi_2, \phi_2')$, we define the binary equivalence relation ~L> by $\lambda_1^b \sim_{L>} \lambda_2^b$ if, and only if, $r_1 = r_2$ and there exists an embedding $\psi$ such that: $q_2^b = \bar{\psi}(q_1^b)$ and $\phi_2(A, i) = \psi(A, \phi_1(A, i))$ for any agent type $A \in A$ and any agent identifier $i \in$ agents($A, E_\ell$) (where $E_\ell$ is thelhs of the rule $r_1$). It is worth noticing that we require no relation between $\phi_1'$ and $\phi_2'$ since the purpose of these mappings is to allocate the identifiers of newly created agents, and that the population-based semantics abstract away agent identifiers.

In order to ensure that the pair (~Q>, ~L>) is admissible for abstracting the system S^b, we require that at time t = 0, ~Q>-equivalent non standard states have the same probability to occur, that is to say a given non standard state is an initial state if, and only if, (i) any ~Q>-equivalent state is; and (ii) two given ~Q>-equivalent non standard states $q_1^b, q_2^b$ have the same initial probability (that is to say $i^b(q_1^b) = i^b(q_2^b)$).

**Proposition 4.** The pair (~Q>, ~L>) of binary equivalence relations is admissible for abstracting the system S^b.

We give the following lemmas before proving Prop. 4.

**Lemma 4.** Let $\lambda_1^b = (r_1, q_1^b, \phi_1, \phi_1')$ and $\lambda_2^b = (r_2, q_2^b, \phi_2, \phi_2')$ be two non standard transition labels in L^b such that $\lambda_1^b \sim_{L>} \lambda_2^b$. Let $\psi$ be an embedding such that $\bar{\psi}(q_1^b) = q_2^b$ and $\phi_2(A, i) = \psi(A, \phi_1(A, i))$ for any $A \in A$, $i \in$ agents($A, E_\ell$).

Then, $q_2^b[E_r]_{\phi_2}$ is well defined if and only if, $q_1^b[E_r]_{\phi_1}$ is well defined. Moreover, in such a case, we have:

$$ \text{clean} (q_2^b[E_r]_{\phi_2}) \equiv \bar{\psi}^*(\text{clean}[q_1^b[E_r]_{\phi_1}]), $$

where $\psi^*$ maps each pair $(A, i) \in \text{dom}(\psi)$ to the identifier $\psi(A, i)$, and each pair $(A, \bar{i}) \in A \times \bar{N}$ to the identifier $\bar{i}$.

*Proof (sketch).* Let us denote by $E_\ell$ thelhs of the rule $r_1$.

Consider the agent $a_\ell$ of type $A \in A$ and identifier $i \in \bar{N}$ in $E_\ell$. We have $\phi_2(A, i) = \psi(A, \phi_1(A, i))$. Then the agent $a_2$ with identifier $\phi_2(A, i)$ in $q_2^b$ is equal to the agent $a_1$ with identifier $\phi_1(A, i)$ in $q_1^b$. Thus, the agent $a_2$ matches $a_\ell$ (up to $\equiv$) if and only if the agent $a_1$ matches $a_\ell$ (up to $\equiv$).
This proves that $q_2^b[E_r]_{\phi_2}$ is defined, if and only if $q_1^b[E_r]_{\phi_1}$ is defined. Moreover, for any agent $a_\ell$ of type $A \in \mathcal{A}$ and identifier $i \in \mathbb{N}$ in $E_\ell$, the computation of $r_1$ along $\phi_1$ and the computation of $r_1$ along $\phi_2$, modifies (or deletes) the agent with type $A \in \mathcal{A}$ and identifier $\phi_1(A, l)$ in $q_1^b$ and the agent with type $A$ and identifier $\phi_2(A, l)$ in $q_2^b$ the same way. As a consequence, we have $q_2^b[E_r]_{\phi_2} \equiv \overline{\psi^\star}(q_1^b[E_r]_{\phi_1})$. Yet, the primitive **clean** commutes with embeddings and $\equiv$-equivalence, so: **clean**($q_2^b[E_r]_{\phi_2}$) $\equiv \overline{\psi^\star}$(**clean**($q_1^b[E_r]_{\phi_1}$)). $\square$

Now we can prove Prop. 4.

*Proof (Prop. 4).* We show that the requirements of Def. 7 are satisfied.

1. Given a non standard state $q^b \in \mathcal{Q}^b$, there is a finite number of agents in $q^b$. The set $[q^b]_{\sim_{\mathcal{Q}^b}}$ is indeed the set of mixtures that are isomorphic to $q^b$. This set is finite, because in a mixture, we have required that agent of same type are indexed with consecutive labels starting by 1.

2. Given two non standard states $q_1^b$ and $q_2^b$ such that $q_1^b \sim_{\mathcal{Q}^b} q_2^b$, there exists an embedding $\psi$ such that $q_2^b = \overline{\psi}(q_1^b)$.

We consider a rule $r = E_\ell \xrightarrow{k} E_r$. We want to construct a bijection $f_\psi$ between the non standard transition labels $\lambda_1^b$ of the form $(r, q_1^b, \phi_1, \phi'_1)$ and the non standard transition labels $\lambda_2^b$ of the form $(r, q_2^b, \phi_2, \phi'_2)$.

We define $f_\psi(r, q_1^b, \phi_1, \phi'_1)$ as $(r, q_2^b, \phi_2, \phi'_2)$ where:

- $\phi_2(A, i) = \psi(A, (\phi_1(A, i)))$ for any agent type $A \in \mathcal{A}$ and any agent identifier $i \in \text{agents}(A, E_\ell)$;

- $\phi'_2$ is defined by $\phi'_2(A, \bar{i}) = \phi'_1(A, \bar{i})$ for any pair $(A, \bar{i}) \in \text{dom}(\phi'_1)$ such that $\bar{i} \in \mathbb{N}$ (which means that $\lambda_1^b$ and $\lambda_2^b$ allocate the identifier of newly created agents the same way) and $(r, q_2^b, \phi_2, \phi'_2) \in \mathcal{L}^b$ (which implies that $\phi'_2$ should preserve the relative order of proper identifiers).

The mapping $f_\psi$ is a bijection, the inverse of with is $f_{\psi^{-1}}$, where $f_{\psi^{-1}}$ is defined the same way as $f_\psi$.

Let us now consider a non standard transition label $\lambda_1^b$ such that $\lambda_1^b$ is of the form $(r, q_1^b, \phi_1, \phi'_1)$.

We denote $\lambda_2^b = f_\psi(\lambda_1^b) = (r, q_2^b, \phi_2, \phi'_2)$.

By definition of $\sim_{\mathcal{L}^b}$, we have $\lambda_1^b \sim_{\mathcal{L}} \lambda_2^b$.

Moreover, by Lem. 4, we have: **clean**($q_2^b[E_r]_{\phi_2}$) $\equiv \overline{\psi^\star}$(**clean**($q_1^b[E_r]_{\phi_1}$)), where $\psi^\star$ is defined as in Lem. 4. So the sets **shift**(**clean**($q_1^b[E_r]_{\phi_1}$)) and **shift**(**clean**($q_2^b[E_r]_{\phi_2}$)) have the same number of elements, which ensures that $w^b(q_1^b, \lambda_1^b) = w^b(q_2^b, \lambda_2^b)$. By summing over all non standard transition labels in $\mathcal{L}^b$, it follows that $a(q_1^b) = a(q_2^b)$.

3. For any $q_1^b, q_2^b \in \mathcal{Q}^b$, $q_1^b \sim_{\mathcal{Q}^b} q_2^b$ $\land$ $q_1^b \in \mathcal{I}^b$ $\implies$ $q_2^b \in \mathcal{I}^b \land \pi_0^b(q_1^b) = \pi_0^b(q_2^b)$ (by assumption);

4. Let $\lambda_1^b, \lambda_2^b \in \mathcal{L}^b$ be two transition labels such that $\lambda_1^b \sim_{\mathcal{L}^b} \lambda_2^b$. We write $\lambda_1^b = (r_1, q_1^b, \phi_1, \phi'_1)$ and $\lambda_2^b = (r_2, q_2^b, \phi_2, \phi'_2)$. We write $r_1 = E_\ell \xrightarrow{k} E_r$. Let
$q_1^b, q_2^b \in \mathcal{Q}^b$ be two non standard states (or mixtures) such that $q_1^b \xrightarrow{\lambda_1^b} q_1^{b'}$,
and $q_2^b \xrightarrow{\lambda_2^b} q_2^{b'}$.

We want to prove that $q_1^b \sim_{\mathcal{Q}^b} q_2^b$, $q_1^{b'} \sim_{\mathcal{Q}^b} q_2^{b'}$, and $w^b(q_1^b, \lambda_1^b) = w^b(q_2^b, \lambda_2^b)$.
We have $\lambda_1^b \sim_{\mathcal{L}^b} \lambda_2^b$, so by definition, there exists an embedding $\psi$ such that:
$q_2^b = \bar{\psi}(q_1^b)$ and $\phi_2(A, i) = \psi(A, \phi_1(A, i))$ for any agent type $A \in \mathcal{A}$ and any
agent identifier $i \in \text{agents}(A, E_\ell)$.

Since $q_2^b = \bar{\psi}(q_1^b)$ and by definition of $\sim_{\mathcal{Q}^b}$, we have $q_1^b \sim_{\mathcal{Q}^b} q_2^b$.

Then, since $\lambda_1^b \sim_{\mathcal{L}^b} \lambda_2^b$, we have $r_1 = r_2$. Then, by Lem. 4, we have:
$$ \text{clean}(q_2^b[E_r]_{\phi_2}) \equiv \bar{\psi}^*(\text{clean}(q_1^b[E_r]_{\phi_1})) $$
where $\psi^*$ is defined as in Lem. 4.
Since $\phi_1'$ and $\phi_2'$ are into substitutions, we can conclude that $q_1^{b'} \sim_{\mathcal{Q}^b} q_2^{b'}$.

Last, since **clean**($q_2^b[E_r]_{\phi_2}$) $\equiv \bar{\psi}^*(\mathbf{clean}(q_1^b[E_r]_{\phi_1}))$ and by definition of
$\psi^*$, the sets **shift**(**clean**($q_1^b[E_r]_{\phi_1}$)) and **shift**(**clean**($q_2^b[E_r]_{\phi_2}$)) have
the same number of elements, which ensures that $w^b(q_1^b, \lambda_1^b) = w^b(q_2^b, \lambda_2^b)$.

5. Let $q_1^{b'}$ and $q_2^{b'}$ be two non standard states in $\mathcal{Q}^b$ such that $q_1^{b'} \sim_{\mathcal{Q}^b} q_2^{b'}$. Let $q_\star^b \in \mathcal{Q}^b$ be a non standard state, and $\lambda_\star^b \in \mathcal{L}^b$ be a non standard transition label.

We want to prove that the set $\{(q^b, \lambda^b) \mid q^b \sim_{\mathcal{Q}^b} q_\star^b, \lambda^b \sim_{\mathcal{L}^b} \lambda_\star^b, q^b \xrightarrow{\lambda^b} q_1^{b'}\}$
and the set $\{(q^b, \lambda^b) \mid q^b \sim_{\mathcal{Q}^b} q_\star^b, \lambda^b \sim_{\mathcal{L}^b} \lambda_\star^b, q^b \xrightarrow{\lambda^b} q_2^{b'}\}$ are in bijection.

We have $q_1^{b'} \sim_{\mathcal{Q}^b} q_2^{b'}$, so there exists an embedding $\psi_r$ such that $q_2^{b'} = \bar{\psi}_r(q_1^{b'})$.
Let us pick such an embedding $\psi_r$ arbitrarily.

We consider a non standard state $q_1^b$ and a transition label $\lambda_1^b$ such that

$q_1^b \sim_{\mathcal{Q}^b} q_\star^b, \lambda_1^b \sim_{\mathcal{L}^b} \lambda_\star^b$, and $q_1^b \xrightarrow{\lambda_1^b} q_1^{b'}$. We write $\lambda_1^b = (r_1, q_1^b, \phi_1, \phi_1')$.

There might be several non standard states $q_2^b$ and several non standard transition labels $\lambda_2^b = (r_2, q_2^b, \phi_2, \phi_2')$ such that $q_2^b \sim_{\mathcal{Q}^b} q_\star^b$, $\lambda_2^b \sim_{\mathcal{L}^b} \lambda_\star^b$, and $q_2^b \xrightarrow{\lambda_2^b} q_2^{b'}$, because there are indeed several degrees of freedom. Firstly some agents might have been removed so that they do not occur in $q_1^{b'}$ and $q_2^{b'}$ anymore (and so the choice for their identifiers in $q_2^b$ is arbitrary); secondly there might be some symmetries in $q_1^b$ (ie $\text{sym}(q_1^b) > 1$), so that some identifiers can be swapped arbitrarily in $q_2^b$; thirdly, some created agents might have the same interface, so that their image by $\phi_2'$ might be swapped arbitrarily. So we will require additional constraints in order to ensure the uniqueness of the non standard state $q_2^b$ and the non standard transition label $\lambda_2^b$.

We know that there exists a unique embedding $\psi_\ell$ such that:

(a) for any agent type $A \in \mathcal{A}$ and any proper agent identifiers $i, i' \in \mathbb{N}$ which satisfy:

- $\{i, i'\} \cap \{\phi'_1(A, \vec{j}) \mid \vec{j} \in \mathbb{N}\} = \emptyset$ (ie none of the agents of type $A$ and identifier $i$ and of type $A$ and identifier $i'$ have been created in $q_1^{b'}$),

- and $i, i' \in \text{agents}(q_1^{b'}, A)$ (ie none of the agents of type $A$ and identifier $i$ and $i'$ have been deleted),

we have: $\psi_r(A, i) < \psi_r(A, i') \implies \psi_\ell(A, \psi_r(A, i)) < \psi_\ell(A, \psi_r(A, i'))$ (ie $\psi_\ell$ preserves the relative order of the identifiers of the agents that are neither created, nor removed);
(b) for any agent type $A \in \mathcal{A}$ and any proper agent identifier $i \in \mathbb{N}$,
$\psi_\ell(A, \phi_1(A, i)) = \phi_1(A, i)$, if the agent of type $A$ and identifier $i$ is removed in the rule $r_1$ (ie $\psi_\ell$ preserves the identifiers of the deleted agents).

Then we define the non standard state $q_2^b$ by $q_2^b = \bar{\psi}_\ell(q_1^b)$ and the embedding
$\phi_2$ by $\phi_2(A, i) = \psi_\ell(A, \phi_1(A, i))$ for any agent type $A \in \mathcal{A}$ and any agent
identifier $i \in \text{agents}(A, E_\ell)$.

On another hand, we define $\phi'_2$ as the unique into substitution such that
$(r_2, q_2^b, \phi_2, \phi'_2)$ is a non standard label in $\mathcal{L}^b$ and $\phi'_2(A, \bar{i}) = \psi_r(A, (\psi'_1(A, \bar{i})))$
for any agent type $A \in \mathcal{A}$ and any temporary identifier in $\mathbb{N} \cap \text{agents}(A, E_r)$
(this fixes how the identifiers of created agents are allocated in $q_2^{b'}$).

By construction, we have: $q_2^b \sim_{Q^b} q_\star^b, \lambda_2^b \sim_{\mathcal{L}^b} \lambda_\star^b$, and $q_2^{\lambda_b} \xrightarrow{\lambda_b} q_2^{b'}$.

The same construction can be made by replacing the index 1 with the index 2 (and conversely) and the embedding $\psi_r$ with the embedding $\psi_r^{-1}$. The resulting function maps the pair $(q_2^b, \lambda_2^b)$ back to $(q_1^b, \lambda_1^b)$.

As a consequence, the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b} q_\star^b, \lambda^b \sim_{\mathcal{L}^b} \lambda_\star^b, q^b \xrightarrow{\lambda^b} q_1^{b'}\}$ and the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b} q_\star^b, \lambda^b \sim_{\mathcal{L}^b} \lambda_\star^b, q^b \xrightarrow{\lambda^b} q_2^{b'}\}$ are in bijection.

We denote by $(S^b, S, \beta_1^\mathcal{L}, \beta_1^Q, \gamma_1^Q)$ the abstraction that is induced by the pair $(\sim_{Q^b}, \sim_{\mathcal{L}^b})$. Then we call the system $S$, the population-based semantics (of the set of rules and initial distribution of states).

**Theorem 5 (population-based semantics).** The population-based semantics is a sound and complete abstraction (as defined in The. 3) of the individuals-based semantics.

We recall that the correspondence can be established only if $\sim_{Q^b}$-equivalent
non standard states are equiprobable at the beginning of the system computa-
tion. Indeed, the hypothesis in Def. 6 only ensures that this equiprobability is
invariant, which is why we have to require this fairness property at time $t = 0$.

Now we give more intuitive explanations about the population-based semantics. We shall notice that the elements of the quotient of the set of mixtures by the binary equivalence $\sim_{Q^b}$ can be seen as multiset of molecular species. For that purpose, we assume that we are given a set $\mathcal{R}$ of non standard species, such that for any non standard species $q^b$, there exists a unique non standard species $q_\star^b \in \mathcal{R}$ such that $q^b \sim_{Q^b} q_\star^b$. This way the elements of $\mathcal{R}$ can be seen as a normal form for $\sim_{Q^b}$-equivalent non standard species. Then each non standard mixture $q^b \in \mathcal{Q}^b$ can be decomposed into a set of non standard species, each of them is $\sim_{Q^b}$-equivalent to a non standard species in $\mathcal{R}$. Each such species may occur several times, so the non standard state $q^b$ can be seen, up to $\sim_{Q^b}$ as a multiset of species in $\mathcal{R}$.

Furthermore the equivalence relation $\sim_{\mathcal{L}^b}$ identifies the labels of the transitions which consist in the application of the same rule to the same molecular species (and along the same embeddings) within a given mixture. It also abstracts away the allocation of new markers. More precisely, let us consider
$\lambda^b = (r, q^b, \phi, \phi')$ a non standard label in $\mathcal{L}^b$. We denote $r = E_\ell \xrightarrow{k} E_r$. Then, we have:

$$w([q^b]_{\sim_{\mathcal{Q}^b}}, [\lambda^b]_{\sim_{\mathcal{L}^b}}) = \frac{k \cdot x(\lambda^b)}{\mathrm{sym}(E_\ell)},$$

where $x(\lambda^b)$ is the number of embeddings $\phi_1$ between $E_\ell$ and $q^b$ such that there exists an isomorphic embedding $\psi$ which satisfies $\phi_1(A, i) = \psi(A, \phi(A, i))$ for any agent type $A \in \mathcal{A}$ and any agent identifier $i \in \mathrm{agents}(A, E_\ell)$.

*Example 3.* We return to the example in Sect. 2. There are eight classes of non standard species: four classes of molecular species with a single agent (the class $[N_1(x_w)]_{\sim_{\mathcal{Q}^b}}$ for any $N \in \{A, B\}$ and $w \in \{u, p\}$) and four classes of molecular species with two connected agents (the class $[A_1(x_{w_A}^{B_1@x}), B_1(x_{w_B}^{A_1@x})]_{\sim_{\mathcal{Q}^b}}$ for any $w_A, w_B \in \{u, p\}$).

Now we consider the rule $r := A_1(x_u^?) \xrightarrow{k_{A+}} A_1(x_p^?)$ which allows the activation of any agent of type $A$ whatever the binding state of its site $x$ is. There is at most three classes $\lambda_{A^c}, \lambda_{A^c B^c}, \lambda_{A^c B^*}$ of transition labels for the rule $r$, depending on whether the agent of type $A$ to be deactivated is free, bound to a deactivated agent of type $B$, or bound to an activated agent of type $B$.

Moreover, given the standard state $q$, the weight $w(q, \lambda_{A^c B^*})$, for instance, is exactly the product the rate constant $k$ and the number of agents of type $A$ that are bound to an activated agent of type $B$, in the standard state $q$.

# 5 Stochastic fragments

In this section we are looking for certain suitable pattern components that will enable the definition of a coarser abstraction of the population-based semantics. We call these components stochastic fragments.

## 5.1 Dependency analysis

So as to define our suitable components in general, we will use the annotated contact map (defined below) to report an over-approximation of the correlations that can be established by rules.

We suppose given a rule set and a finite distribution of initial states. The associated contact map is a summary of the potential bindings between agents. Specifically, the nodes of the contact map are the agent types occurring in $\mathcal{A}$ with their full set of sites, and there is an edge between two sites if these two sites may form a bond during a given trace.

An example of a contact map is given in Fig. 12(a). As one sees, sites in the contact map may be connected to several sites, which implies a competition between two binding states; indeed, an agent can even be connected to itself (via the same, or different, sites).

We now give the definition of an annotated contact map:
<figure><img src="image_17.png" /><figcaption>**Fig. 12.** Maps for the model that is defined by $\mathcal{A} = \{A, B, C\}$, $\Sigma = [A \mapsto \{x\}, B \mapsto \{a, c\}, C \mapsto \{a, b\}]$, and $\Sigma'$ maps any agent name to the empty set, the initial state $A_1(x), B_1(a, c), C_1(a, b)$ and the three following rules (with arbitrary rates): $A_1(x), B_1(a) \Rightarrow A_1(x^{B_1 \@ a}), B_1(a^{A_1 \@ x});$ $A_1(x), C_1(a) \Rightarrow A_1(x^{C_1 \@ a}), C_1(a^{A_1 \@ x});$ and $B_1(c), C_1(b, a^-) \Rightarrow B_1(c^{C_1 \@ b}), C_1(b^{B_1 \@ c}, a^-)$.</figcaption></figure>

**Definition 9.** An annotated contact map (ACM) is a contact map where in addition: (i) each agent $A$ has an associated partitioning $\mathcal{P}_A$ of $\Sigma(A)$; (ii) a subset of edges is distinguished.

Distinguished edges are called *soft* (represented with dashed lines), the others are called *solid*. An example of ACM is given in Fig. 12(b). Intuitively, if the states of some sites within a same agent are correlated, then these sites should belong to the same partition class in the ACM. Moreover, if the states of two subcomplexes connected by a bond, are correlated, then the corresponding edge should be solid.

As explained above, the ACM intends to record the correlations which can be established when applying rules. We introduce here a dependency analysis that is based on the syntax of the rules. Then we use this dependency analysis to define sound ACMs.

First we formalize the notion of tests and modifications within a rule:

**Definition 10 (tests and modifications).** Consider a rule $r = E_\ell \xrightarrow{k} E_r$; a site $s$ is said to be tested by $r$ if for some $i \in \mathbb{N}$, $A_i(\sigma)$ is the agent with the identifier $i$ in $E_\ell$ and $s$ occurs in $\sigma$; a site $s$ is said to be modified by $r$ if for some $l \in \mathbb{N} \cup \mathbb{N}$, either there is no agent $A_l(\sigma)$ in $E_\ell$ and there is one agent $A_l(\sigma)$ with $s \in \sigma$ (agent creation); or if there is no agent $A_l(\sigma)$ in $E_r$ and there is one agent $A_l(\sigma)$ in $E_\ell$ with $s \in \sigma$ (agent deletion); or if $A_l(\sigma)$ is in $E_\ell$ and $A_l(\sigma')$ is in $E_r$ and either the binding state or the internal state of $s$ is different in $\sigma$ and $\sigma'$.

Then, we distinguish some rules which can enforce no correlation.

**Definition 11 (trivial rules).** We say that a rule is trivial: - trivial dissociation: if it deletes a (wildcard) bond without testing or modifying
anything else, ie if it is either of the form $A_i(x^{B_j@y})$, $B_j(y^{A_i@x}) \xrightarrow{k} A_i(x)$,
$B_j(y)$, or of the form $A_i(x^-) \xrightarrow{k} A_i(x)$;

- trivial complexation: if it creates a bond without testing or modifying anything else, ie if it is of the form $A_i(x)$, $B_j(y) \xrightarrow{k} A_i(x^{B_j@y})$, $B_j(x^{A_i@x})$;

- trivial deletion: or if it deletes an agent without testing anything, ie if it is of the form $A_i(\varepsilon) \xrightarrow{k} \varepsilon$.

Since trivial rules cannot enforce correlations between the state of several parts of a given molecular species, they do not have to be considered during the dependency analysis.

We are now pinpointing those ACMs that soundly summarize the correlation between part of species.

**Definition 12 (valid annotated contact map).** A valid annotated contact map is an ACM that satisfies the following additional criteria:

- (1.i) if site x and site y are tested or modified in the same agent of type A in r, then they belong to the same class in the partitioning of the site of A.

- (2.i) if the binding state of the site x in an agent of type A is of the form $B_i@y$, then the edge between the site x of the node A and the site y of the node B must be solid;

- (2.ii) if a bond can be released by r, between the site x in an agent of type A and the site y of an agent of type B, then the edge between the site x of the node A and the site y of the node B must be solid (due to side-effects, x and/or y might not occur in r).

Please note that Def. 12 gives necessary conditions for an ACM to be valid. Moreover, given a valid ACM, we can always merge two equivalence classes of sites, or replace a soft edge with a solid edge: the result will still be a valid ACM.

The idea behind the above definition is that when no correlations can be enforced between subparts of a molecular species, we can safely fragment this species into its subparts (which is why we call them fragments!).

Note that in the above definition, ACMs incur no constraint from trivial rules. Moreover, if an agent of type $A \in \mathcal{A}$ can be created in a rule, then there is only one class in the partition $P_A$ of $\Sigma(A)$ (by definition, all the sites of $A$ are modified by the rule). Whenever a rule can remove an agent of type $A$, either the rule is trivial (ie of the form $A_i(\varepsilon) \xrightarrow{k} \varepsilon$) in which case it induces no constraint, or the rule is not trivial, and on the first hand, there is only one class in the partition $P_A$ of $\Sigma(A)$, and on the second hand, each bond which can stem from a site of the removed $A$ and which is compatible with the lhs of the rule must be solid.

*Example 4.* In the example of Fig. 12, all rules are trivial, except the rules $B_1(c)$, $C_1(b, a^-) \leftrightarrow B_1(c^{C_1@b})$, $C_1(b^{B_1@c}, a^-)$. As a consequence, the sites b and a must be in the same partition class in $P_C$. Moreover, the bond between the site b of the node C, and the site c of the node B must be solid (since it can be put/released by the rule). These are the only constraints that we have on the ACM. So the ACM given in Fig. 12(b) is valid.
*Example 5.* In the example of Sect. 2, whenever we have $k_{A+B} = k_{A\star+B\star}$, the complexation between particles of type A and particles of type B can be encoded by the following trivial rule:

$$A_1(x), B_1(x) \xrightarrow{k_{A+B}} A_1(x^{B_1}@x), B_1(x^{A_1}@x).$$

As a consequence, complexation induces no constraint on valid ACMs.

But, whenever we have $k_{A+B} \neq k_{A\star+B\star}$, we need several rules to model complexation. For instance, we may use the following set of rules:

$$\begin{align*}
A_1(x_u), B_1(x) &\xrightarrow{k_{A+B}} A_1(x_u^{B_1}@x), B_1(x^{A_1}@x), \\
A_1(x_p), B_1(x_u) &\xrightarrow{k_{A+B}} A_1(x_p^{B_1}@x), B_1(x_u^{A_1}@x), \\
A_1(x_p), B_1(x_p) &\xrightarrow{k_{A\star+B\star}} A_1(x_p^{B_1}@x), B_1(x_p^{A_1}@x).
\end{align*}$$

At least one of these rules is not trivial, which implies that the edge between the site $x$ of the node A, and the site $x$ of the node B must be solid in any valid ACM.

This matches with our conclusions in Sects. 2.3.1 and 2.3.2, where we have stated that complexes can be safely split into two fragments, if and only if the complexation rate is independent from the internal states of the particle of type A and the particle of type B to be complexed.

This is a major difference between differential fragments [28] and stochastic fragments, since in the case of a differential semantics, complexes can be split into two fragments, even if the complexation rate depends on the states of particles to be complexed.

## 5.2 Fragments

Each valid annotated contact map (of which there are many depending on the choices of partitions and soft edges) defines a set of fragments. Soft edges specify when we can cut molecular species into pattern components, and partitions specify which sites must appear together in interfaces.

**Definition 13.** Given a valid ACM, a non standard fragment for that ACM is a proper pattern component $F^b$ with no wildcard bonds such that:

- (i) for each agent $A_l(\sigma)$ occurring in $F^b$, the set of sites in $\sigma$ is a class of $\mathcal{P}_A$;

- (ii) for each agent $A_l(\sigma)$ occurring in $F^b$, each site $x$ occurring in $\sigma$ and such that $x \in \Sigma'(A)$ has a non empty internal state;

- (iii) each pair of site address occurring as binding state in $F^b$ corresponds to two sites that are connected by a solid edge of the ACM;

- (iv) each binding type occurring in $F$ corresponds to a soft edge.

A fragment $F$ is a set of non standard fragments which are equal up to substitution (ie the set of the non standard fragments $\bar{\phi}(F^b)$, for a given non standard fragment $F^b$ and any into embedding $\phi$ such that $\mathrm{dom}(\phi) = \{(A, l) | l \in \mathrm{agents}(F^b, A)\}$).
*Example 6.* In the example of Fig. 12, the non standard fragments are of the form: $A_l(x)$; $A_l(x^{B@a})$; $A_l(x^{C@a})$; $B_l(a)$; $B_l(a^{A@x})$; $B_l(c)$; $C_l(a,b)$; $C_l(a^{A@x},b)$; $B_l(c^{C_{l'}@b})$ , $C_{l'}(a,b^{B_l@c})$; $B_l(c^{C_{l'}@b})$ , $C_{l'}(a^{A@x},b^{B_l@c})$. So there are 10 fragments.

*Example 7.* In the example of Sect. 2, whenever $k_{A+B} = k_{A^*+B^*}$, the non standard fragments are of the form: $A_l(x_u)$; $A_l(x_p)$; $A_l(x_u^{B@x})$; $A_l(x_p^{B@x})$; $B_l(x_u)$; $B_l(x_p)$; $B_l(x_u^{A@x})$; $B_l(x_p^{A@x})$. So there are 8 fragments.

Otherwise, the non standard fragments are the non standard species, which gives 8 fragments as well.

We see that the fewer non trivial rules, and the smaller their components, the fewer fragments are defined. This means in particular that by removing redundant tests in a rule —while preserving the semantics of the system— as the static analysis that is described in [20] permits, one can simplify the set of fragments and obtain a better reduction. Likewise, the restriction above to non trivial rules is important for the efficiency of the compression, as it allows to cut fragments on bonds that are only ever tested by trivial rules. These are two good reasons to introduce binding types in the language of patterns.

As said, there might be several valid annotated contact maps. We distinguish two particular ones, that may coincide. The *trivial* annotation arises by taking for all agent type *A* in the ACM the trivial partition {$Σ(A)$}, and taking all edges to be solid. Its set of fragments is in bijection with the set of all molecular species. The *minimal* annotation is obtained by choosing edges soft whenever possible, and choosing minimal partitioning (ie which gather as few sites as possible).

We identify in the following a key property of our fragments that will be sufficient for the derivation of a fragment-based semantics. For that purpose, we use the notion of rule refinements, which is based on the following idea: a rule may require less or more constraints about its context of application. This way, a rule can be refined by increasing both the left and the right hand sides of the rule. A neutral refinement, consists in replacing a given rule into a set of refined rules so that each case of application of the former rule is handled with exactly one refined rule. In such a case, the rates of the so refined rules can be derived (according to the loss/gain of symmetries in left hand sides) so that the former system and the refined system have the same stochastic semantics. We refer to [18, 40] for a more complete description of rule refinements. Here we are using heterogeneous refinements as described in [40], where in a rule, agents with the same type can be refined by using a different set of states.

**Proposition 5 (neutral refinement).** Any non trivial rule $E_\ell \xrightarrow{k} E_r$ can be neutrally refined into a (potentially infinite) set of rules $\{E_{\ell i} \xrightarrow{k_i} E_{ri}\}$, such that any pattern component (in the `lhs` or in the `rhs`) in a refined rule $E_{\ell i} \xrightarrow{k_i} E_{ri}$ is a (non standard) fragment.

A consequence of Prop. 5 is that there is no side effects in the so refined set of rules. This is mainly because of the three following reasons: (a) there is no
wildcard bond ‘-’ in fragments, (b) all the sites of the agents that are removed
in non trivial rules, belong to the same partition class, and (c) any bond that
can be released by side effects corresponds to a solid edge in the ACM.

*Proof.* The rules of this neutral refinement can be recursively enumerated in the following way.

First, for any agent $A_i(\sigma)$ that occurs in a pattern component in the lhs of the initial rule, we know, by Def. 12 (1.i) that the set of sites occurring in $\sigma$ is a subset of a partition class in $P_A$, so we can complete the interface $\sigma$ by adding the sites $x$ that are in this class but not in $\sigma$, with no internal state and a question mark ‘?’ as binding state.

Then, consider that we have a set $X$ of rules that we want to refine. We assume (induction hypotheses) that in any rule $r \in X$, (i) whenever an agent of type $A \in \mathcal{A}$ and interface $\sigma$ occurs in a pattern component, then the set the sites occurring in $\sigma$ is the union of some partition classes in $P_A$, (ii) any site address occurring in a pattern component corresponds to a solid edge in the ACM, (iii) any bond which can be released or removed by the rule corresponds to a solid edge in the ACM.

Let $r$ be a rule of minimal size (ie the number of agents in $r$ is minimal) in $X$. We consider the following cases:

- Whenever the rule $r$ contains a site $x \in S$ in an agent of type $A \in \mathcal{A}$ with no internal state whereas $x \in \Sigma'(A)$, the rule is refined by enumerating all the potential internal state $w \in \mathbb{I}$. Induction hypotheses are trivially preserved.

- Otherwise, whenever the rule $r$ in $X$ contains a question mark ‘?’, then this rule is refined by enumerating the types of all the potential partners of the site (according to the contact map), and replacing the question mark either by the empty binding state ‘$\epsilon$’ or by a corresponding binding type $A@x$. Induction hypotheses are trivially preserved.

- Otherwise, whenever the rule $r$ in $X$ contains a wild card bond ‘-’, then this rule is refined by enumerating the types of all the potential partners of the site. Induction hypotheses are trivially preserved.

- Otherwise, whenever the rule $r$ in $X$ contains an agent $A_i(\sigma)$ with a site of the form $x_i^{B@y}$ and such that the edge between the site $x$ of the agent $A$ and the site $y$ of the agent $B$ is solid in the ACM, then the rule is refined into several ones, by enumerating the potential target of this bond:

1. the target might be a fresh agent, we choose a fresh (for the agents of type $B$) proper identifier $j \in \mathbb{N}$, we replace the binding type of the site $x$ in the agent $A_i(\sigma)$ with the site address $B_j@y$, and we add the agent $B_j(\sigma')$ before both thelhs and the rhs of the rule, where $\sigma'$ contains all the sites in the partition class of $y$ in $P_B$ and the site $y$ has no internal state and the binding state $A_i@x$. Moreover, all other sites have no internal state and a question mark as binding state ‘?’.

2. the target might be an existing agent where the site $y$ is either already in the interface, or not:

• For any agent $B_j(\sigma')$ such that the site $y$ occurs in $\sigma'$ with a binding state that is a question mark ‘?’, a wildcard bond ‘-’, or a binding
state of the form $A@x$, in thelhs of the rule. In that case, we replace
the binding state of the site $x$ in the agent $A_i(\sigma)$ with the binding
state $B_j@y$ and the binding state of the site $y$ in the agent $B_j(\sigma')$
with the binding state $A_i@x$.

* For any agent $B_j(\sigma')$ such that the site $y$ does not occur in $\sigma'$, then we refine $\sigma'$ by adding all the sites in the class of $y$ in $P_B$, moreover, the site $y$ has no internal state and the binding state $A_i@x$, whereas all other sites have no internal state and a question mark as binding state '?'. Then we replace the binding state of the site $x$ in the agent $A_i(\sigma)$ with the binding state $B_j@y$.

Induction hypotheses are preserved, since the edge is solid in the ACM.

- Otherwise, any pattern component (in the lhs or in the rhs) in the rule $r$ is a non standard fragment. We collect this rule (by correcting its rate according to gain/loss of symmetries [40]), and remove it from the set $X$.

One shall notice, that there might be several choices when applying these induc-
tion steps, but they commute. Moreover, the fact that $r$ is chosen so as its size is
minimal ensure that we do not refine a given rule infinitely, without ever using
the last case.

<figure><img src="image_18.png" /></figure>

Our framework does not require the neutral refinements of each rule to be
finite. Indeed, in the following, we will always use the existence of the refinement,
but we do not need as explicit definition of it.

5.3 Fragments-based semantics

Now we propose to use fragments in order to define a coarser granularity of
observation. The idea is to abstract each multiset of molecular species by a
multiset of fragments. This amount to say that we forget away both the pairing
relation between the sites that are connected through a soft bond and which sites
belong to the same agents whenever they do not belong to the same partition
class.

For that purpose, we need to relax the definition of the equivalence relation
~Q>, so as to identify two non standard states having the same multiset of
fragments. This is done by defining a new kind of substitutions, which can (i)
shuffle agent identifiers (as in the substitutions that we have used in the definition
of ~Q>, (ii) permute parts of interfaces according to partition classes in the
ACM, (iii) permute the binding states of pair of sites of the form s₁ = x<sub>l₁</sub><sup>λ₁</sup> and
s₂ = x<sub>l₂</sub><sup>λ₂</sup> where A and B are an agent types in A, x is a site name in Σ(A),
y is a site name in Σ(B), s₁ is in the interface σ of an agent A<sub>l₁</sub>(σ), s₂ is in
the interface σ₂ of an agent A<sub>l₂</sub>(σ₂), λ₁ = B<sub>l₁'</sub>@y, λ₂ = B<sub>l₂'</sub>@y, and the edge
between the site x of the node A and the identifier l₁ and the site y of the node
B, is soft in the ACM.

More formally, a *fragment shuffling* is given by a triple $\phi = (\phi_l, \phi_\sigma, \phi_\lambda)$ where $\phi_l$ is a partial mapping between pairs $(A, l) \in \mathcal{A} \times (\mathbb{N} \cup \bar{\mathbb{N}})$ of agent type/identifier