and identifiers $l' \in \mathbb{N} \cup \overline{\mathbb{N}}$ (ie $\phi_l$ is a substitution); $\phi_\sigma$ and $\phi_\lambda$ are two partial mappings between triples $(A, l, x) \in \mathcal{A} \times (\mathbb{N} \cup \overline{\mathbb{N}}) \times \mathcal{S}$ of agent type/identifier/site name and identifiers $l' \in \mathbb{N} \cup \overline{\mathbb{N}}$.

A fragment shuffling can be applied with a pattern $E$, if and only if, the following properties are satisfied:

- for any agent type $A \in \mathcal{A}$, we have $(A, l) \in \text{dom}(\phi_l)$ for any agent identifier $l \in \text{agents}(E, A)$;

- for any pair $(A, l) \in \text{dom}(\phi_l)$ and any site $x \in \Sigma(A)$ such that the agent of type $A$ an identifier $l$ in $E$ documents the site $x$, we have: (i) $(A, l, x) \in \text{dom}(\phi_\sigma)$, (ii) $(A, l, x) \in \text{dom}(\phi_\lambda)$, (iii) the agent of type $A$ with identifier $\phi_\sigma(A, l, x)$ and the agent of type $A$ with identifier $\phi_\lambda(A, l, x)$ document the site $x$;

- for any triple $(A, l, x) \in \text{dom}(\phi_\lambda)$, $\phi_\lambda(A, l, x) \neq l$ implies that there exists an agent type $B \in \mathcal{A}$ and a site name $y \in \Sigma(B)$ such that (a) the site $x$ of the agents of type $A$ and identifiers $l$ and $\phi_\lambda(A, l, x)$ in $E$ bear the binding states $B_{l'}@y$ and $B_{l''}@y$ (for two given identifiers $l'$ and $l''$ in $\mathbb{N} \cup \overline{\mathbb{N}}$), (b) the edge between the site $x$ of $A$ and the site $y$ of $B$ is soft in the ACM;

- for any agent type $A \in \mathcal{A}$, any identifier $l \in \mathbb{N} \cup \overline{\mathbb{N}}$, and any two site names $x, x' \in \mathcal{S}$ such that $(A, l, x) \in \text{dom}(\phi_\sigma)$, we have $\phi_\sigma(A, l, x) = \phi_\sigma(A, l, x')$ whenever the site names $x$ and $x'$ belongs to the same partition class in $P_A$;

- for any triple $(A, l, x) \in \text{dom}(\phi_\sigma)$ and any agent identifier $l' \in \mathbb{N} \cup \overline{\mathbb{N}}$ such that $(A, l', x) \in \text{dom}(\phi_\sigma)$ and $\phi_\sigma(A, l, x) = \phi_\sigma(A, l', x)$, we have $l = l'$;

- for any triple $(A, l, x) \in \text{dom}(\phi_\lambda)$ and any agent identifier $l' \in \mathbb{N} \cup \overline{\mathbb{N}}$ such that $(A, l', x) \in \text{dom}(\phi_\lambda)$ and $\phi_\lambda(A, l, x) = \phi_\lambda(A, l', x)$, we have $l = l'$;

Intuitively, the mapping $\phi_l$ is used to reorder agent identifiers, the mapping $\phi_\sigma$ make the agents exchange some part of their interfaces (according to partition classes in the ACM), and the mapping $\phi_\lambda$ is used to exchange soft bonds. This is formalized as follows: given a non standard pattern $q_1^b$ and $\phi = (\phi_l, \phi_\sigma, \phi_\lambda)$ be a fragment shuffling which can be applied with $q_1^b$, then the image $q_2^b = \bar{\phi}(q_1^b)$ of $q_1^b$ by $\phi$ is defined up to $\equiv$ by $h_2(h_1(g_2(g_1(f_2(f_1(q_1^b))))))$ where: $f_1(q_1^b)$ consists in replacing, for any triple $(A, l, x) \in \text{dom}(\phi_\lambda)$, the binding state of the site $x$ of the agent of type $A$ and identifier $l$ with the binding state of the site $x$ of the agent of type $A$ with identifier $\phi_\lambda(A, l, x)$; then in the result, $f_2$ consists in replacing for any triple $(A, l, x) \in \text{dom}(\phi_\lambda)$ each occurrence of the binding address $A_l@x$ with the binding address $A_{\phi_\lambda(A,l,x)}@x$; then in the result, applying the function $g_1$ consists in replacing, for any triple $(A, l, x) \in \text{dom}(\phi_\lambda)$, the site $x_l^\lambda$ in the interface of the agent of type $A$ and identifier $l$, with the site $x_{l'}^\lambda$ of the agent of type $A$ and identifier $\phi_\sigma(A, l, x)$; then in the result, $g_2$ consists in replacing, for any triple $(A, l, x) \in \text{dom}(\phi_\lambda)$, each occurrence of the binding address $A_l@x$ with the binding address $A_{\phi_\sigma(A,l,x)}@x$; then in the result, applying the function $h_1$ consists in replacing the identifier of the agent of type $A$ and identifier $l$ with the identifier $\phi_l(A, l)$; then in the result, applying the function $h_2$ consists in replacing each occurrence of the binding address of the form $A_l@x$ with the binding address $A_{\phi_l(A,l)}@x$.

A fragment shuffling $\psi = (\psi_l, \psi_\sigma, \psi_\lambda)$ such that there exists two non standard states $q_1^b, q_2^b \in \mathcal{Q}^b$ which satisfy $q_2^b = \bar{\psi}(q_1^b)$ is called an isomorphic fragment
shuffling. Moreover, the fragment shuffling $\psi^{-1} = (\psi_l^{-1}, \psi_\sigma^{-1}, \psi_\lambda^{-1})$ that is defined by: $\psi_\lambda^{-1}(A, l, x) = l'$ where $l'$ is the unique identifier such that

$$ \psi_l(A, \psi_\sigma(A, \psi_\lambda(A, l', x), x)) = l; $$

$\psi_\sigma^{-1}(A, l, x) = l'$ where $l'$ is the unique identifier such that: $\psi_l(A, \psi_\sigma(A, l', x)) = l$; and $\psi_l^{-1}(A, l) = l'$ where $l'$ is the unique identifier such that $\psi_l^{-1}(A, l) = l'$. We can check that $\overline{\psi^{-1}(\overline{\psi}(q_1^b))} = q_1^b$ and that $(\psi^{-1})^{-1} = \psi$.

**Example 8.** Let us consider the following example. We define $\mathcal{A}$ as $\{A\}$, $\mathcal{S}$ as $\{x, y, z\}$, $\mathbb{I}$ as $\{u, p\}$. We also assume that $\Sigma(A) = \Sigma'(A) = \{x, y, z\}$ and that in the ACM, $P_A = \{\{x\}, \{y, z\}\}$ and any edge is soft.

We consider the non standard state $q_a^b \in \mathcal{Q}^b$ that is defined as follows:

$$ q_a^b = A_1(x_u^{A_2@y}, y_u^{A_2@x}, z_u), A_2(x_p^{A_1@y}, y_p^{A_1@x}, z_p). $$

Then the set of the non standard states which are the images of $q_a^b$ by a fragment shuffling is given by $\{q_a^b, q_b^b, q_c^b, q_d^b\}$ where:

$$ q_b^b = A_1(x_u^{A_2@y}, y_p^{A_2@x}, z_p), A_2(x_p^{A_1@y}, y_u^{A_1@x}, z_u); $$

$$ q_c^b = A_1(x_u^{A_1@y}, y_u^{A_1@x}, z_u), A_2(x_p^{A_2@y}, y_p^{A_2@x}, z_p); $$

$$ q_d^b = A_1(x_u^{A_1@y}, y_p^{A_1@x}, z_p), A_2(x_p^{A_2@y}, y_u^{A_2@x}, z_u). $$

(Let us remember that non standard states are considered up to $\equiv$.)

For instance the non standard state $q_d^b$ can be obtained by the fragment shuffling $(\phi_l, \phi_\sigma, \phi_\lambda)$ where for any $l \in \{1, 2\}$, $\phi_l(A, l) = l$, $\phi_\sigma(A, l, x) = l$, $\phi_\sigma(A, l, y) = \phi_\sigma(A, l, z) = 3-l$, and $\phi_\lambda(A, l, z) = (A, l, z)$ and $\phi_\lambda(A, l, x) = \phi_\lambda(A, l, y) = 3-l$. This fragment shuffling is not unique, since applying $(\phi_l, \phi_\sigma, \phi_\lambda)$ where for any $l \in \{1, 2\}$, $\phi_l(A, l) = l$, $\phi_\sigma(A, l, x) = 3-l$, $\phi_\sigma(A, l, y) = \phi_\sigma(A, l, z) = l$, and $\phi_\lambda(A, l, z) = (A, l, z)$ and $\phi_\lambda(A, l, x) = \phi_\lambda(A, l, y) = 3-l$ gives the same result (up to $\equiv$).

We introduce the binary relation $\sim_{\mathcal{Q}^b}^\#$ over non standard states as follows: given $q_1^b, q_2^b \in \mathcal{Q}^b$, we say that $q_1^b$ and $q_2^b$ are equivalent up to reorganization of their fragments if, and only if, there exists an (isomorphic) fragment shuffling $\psi$ such that $q_2^b = \overline{\psi}(q_1^b)$. In such a case, we write $q_1^b \sim_{\mathcal{Q}^b}^\# q_2^b$.

Then we introduce the binary equivalence relation $\sim_{\mathcal{L}^b}^\#$, over non standard 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 $\sim_{\mathcal{L}^b}$ by $\lambda_1^b \sim_{\mathcal{L}^b} \lambda_2^b$ if, and only if:

1. $r_1 = r_2$;

2. there exists an fragment shuffling $\psi = (\psi_l, \psi_\sigma, \psi_\lambda)$ such that:

- $q_2^b = \overline{\psi}(q_1^b)$;

- $\phi_2$ maps any pair $(A, i) \in \text{dom}(\phi_1)$ of agent type/identifier, to the identifier $\psi_l(A, \phi_1(A, l))$ whenever the agent of type A and identifier i in $E_\ell$ has an empty interface;
- $\phi_2$ maps any pair $(A, i) \in \text{dom}(\phi_1)$ of agent type/identifier, to the identifier $\psi_l(A, \psi_\sigma(A, \phi_1(A, l), y))$ where $y$ is the name of a site occurring in the interface of the agent with type $A$ and identifier $l$ in $E_\ell$ otherwise (by definition of fragment shuffling, the result does not depend on the choice of the site $y$).

3. the unique non standard states $q_1^b$ and $q_2^b$ such that: $q_1^b \xrightarrow{\lambda_1^b} q_1^{b'}$ and $q_2^b \xrightarrow{\lambda_2^b} q_2^{b'}$, also satisfy $q_1^{b'} \sim_{\mathcal{Q}^b} q_2^{b'}$.

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 fragments-based semantics abstract away agent identifiers. One shall also notice that the fact that the two resulting states $q_1^{b'}$ and $q_2^{b'}$ are $\sim_{\mathcal{Q}^b}^{\sharp}$-equivalent is a consequence of the other assumptions in the case of a non trivial rule. But this property may not hold for trivial rules. For instance, taking the same notations and assumptions as in Exa. 8, we have $q_a^b \sim_{\mathcal{Q}^b} q_b^b$. Then we consider the trivial rule:

$$r = A_1(x^-) \xrightarrow{k} A_1(x),$$

which can be used in order to free the site $x$ of any agent of type $A$. This way, one can free the site $x$ of the agent with the identifier 1 in $q_a^b$ and get the state $A_1(x_u, y_u^{A_2@x}, z_u)$, $A_2(x_p^{A_1@y}, y_p, z_p)$. Then, one can free the site $x$ of an agent in $q_b^b$ and get either the state $A_1(x_u, y_p^{A_2@x}, z_p)$, $A_2(x_p^{A_1@y}, y_u, z_u)$ or the state $A_1(x_u^{A_2@y}, y_p, z_p)$, $A_2(x_p, y_u^{A_1@x}, z_u)$. Neither of these last two states are $\sim_{\mathcal{Q}^b}^{\sharp}$-equivalent to the state $A_1(x_u, y_u^{A_2@x}, z_u)$, $A_2(x_p^{A_1@y}, y_p, z_p)$.

So as to ensure that the pair $(\sim_{\mathcal{Q}^b}^{\sharp}, \sim_{\mathcal{L}^b}^{\sharp})$ is admissible for abstracting the system $S^b$, we require that at time $t=0$, $\sim_{\mathcal{Q}^b}^{\sharp}$-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, any $\sim_{\mathcal{Q}^b}^{\sharp}$-equivalent state is; and (ii) two given $\sim_{\mathcal{Q}^b}^{\sharp}$-equivalent non standard states $q_1^b, q_2^b$ have the same initial probability (that is to say $\pi_0^b(q_1^b) = \pi_0^b(q_2^b)$).

**Proposition 6.** The pair $(\sim_{\mathcal{Q}^b}^{\sharp}, \sim_{\mathcal{L}^b}^{\sharp})$ of binary equivalence relations is admissible for abstracting the system $S^b$.

We give the following lemmas before proving Prop. 4.

**Lemma 5.** 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 $\mathcal{L}^b$. Let $\psi = (\psi_l, \psi_\sigma, \psi_\lambda)$ be an fragment shuffling such that:

- $r_1 = r_2$;

- $r_1$ is a non trivial rule;

- $q_2^b = \bar{\psi}(q_1^b)$;

- $\phi_2$ maps any pair $(A, i) \in \text{dom}(\phi_1)$ of agent type/identifier, to the identifier $\psi_l(A, \phi_1(A, l))$ whenever the agent of type $A$ and identifier $i$ in $E_\ell$ has an empty interface;
- $\phi_2$ maps any pair $(A, i) \in \text{dom}(\phi_1)$ of agent type/identifier, to the identifier $\psi_l(A, \psi_\sigma(A, \phi_1(A, l), y))$ where $y$ is the name of a site occurring in the interface of the agent with type $A$ and identifier $l$ in $E_\ell$ otherwise (by definition of fragment shuffling, the result does not depend on the choice of the site $y$).

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}) = \overline{\psi^*}(\text{clean}q_1^b[E_r]_{\phi_1}), $$

where $\psi^* = (\psi_l^*, \psi_\sigma^*, \psi_\lambda^*)$ such that: $\psi_l^*$ extends the definition of $\psi_l$ with $\psi^*(A, \bar{i}) = i$ for any pair $(A, \bar{i}) \in \mathcal{A} \times \overline{\mathcal{N}}$, and $\psi_\sigma^*$ and $\psi_\lambda^*$ extend the definition of $\psi_\sigma$ and $\psi_\lambda$ with $\psi_\sigma^*(A, \bar{i}, x) = \psi_\lambda^*(A, \bar{i}, x) = \bar{i}$, for any triple $(A, \bar{i}, x) \in \mathcal{A} \times \overline{\mathcal{N}} \times \mathcal{S}$.

*Proof (sketch).* The proof of Lem. 4 can be lifted so as to prove Lem. 5, by using Prop. 5.

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

Now we can prove Prop. 6.

*Proof (Prop. 6).* 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$. Then for each non standard state, the set of agent permutations and of site permutations is finite. It follows that the class $[q^b]_{\mathcal{Q}^b}$ is finite.

2. Let $q_1^b$ and $q_2^b$ be two non standard states such that $q_1^b \sim_{\mathcal{Q}^b} q_2^b$.

Let us prove first that, for any rule $r = E_\ell \xrightarrow{k} E_r$ the sum $\mathcal{W}(r, q_1^b)$ of the expression $w^b(q_1^b, \lambda_1^b)$ for any transition label $\lambda_1^b \in \mathcal{L}^b$ such that $r$ is the first component of the tuple $\lambda_1^b$ and $\lambda_1^b \in \mathcal{L}^b(q_1^b)$, is equal to the sum $\mathcal{W}(r, q_2^b)$ of the expression $w^b(q_2^b, \lambda_2^b)$ for any transition label $\lambda_2^b \in \mathcal{L}^b$ such that $r$ is the first component of the tuple $\lambda_2^b$ and $\lambda_2^b \in \mathcal{L}^b(q_2^b)$.

- if $r$ is a trivial rule:

we have:

$$ \mathcal{W}(r, q_1^b) = \frac{k \cdot \mathcal{X}(E_\ell, q_1^b)}{\text{sym}(E_\ell)}, $$

where $\mathcal{X}(E_\ell, q_1^b)$ is the number of embedding of $E_\ell$ into $q_1^b$. That is to say that $\mathcal{X}(E_\ell, q_1^b)$ is the number of instances of a given type of agent (whenever the rule $r$ is a trivial deletion rule), or the number of bonds of a given type (whenever the rule $r$ is a trivial dissociation rule), or the number of a given type of pairs of free sites. (whenever the rule $r$ is a trivial complexation rule). In all cases, we have: $\mathcal{X}(E_\ell, q_1^b) = \mathcal{X}(E_\ell, q_2^b)$. Thus $\mathcal{W}(r, q_1^b) = \mathcal{W}(r, q_2^b)$.

- if $r$ is a non trivial rule:

since $q_1^b \sim_{\mathcal{Q}^b} q_2^b$, there exists a fragment shuffling $\psi$ such that $q_2^b = \overline{\psi}(q_1^b)$. 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$ maps any pair $(A, i) \in \text{dom}(\phi_1)$ of agent type/identifier, to the identifier $\psi_l(A, \phi_1(A, l))$ whenever the agent of type A and identifier $i$ in $E_\ell$ has an empty interface;

* $\phi_2$ maps any pair $(A, i) \in \text{dom}(\phi_1)$ of agent type/identifier, to the identifier $\psi_l(A, \psi_\sigma(A, \phi_1(A, l), y))$ where $y$ is the name of a site occurring in the interface of the agent with type A and identifier $l$ in $E_\ell$ otherwise (by definition of fragment shuffling, the result does not depend on the choice of the site $y$);

* $\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$ and $\lambda'_2$ allocate the identifier of newly created agents the same way) and $(r, q'_2, \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$ of the form $(r, q'_1, \phi'_1, \phi'_1)$. We denote $\lambda'_2 = f_\psi(\lambda'_1) = (r, q'_2, \phi'_2, \phi'_2)$.

By Lem. 5, we have: **clean** $(q'_2[E_r]_{\phi_2}) \equiv \bar{\psi}^*(\text{clean}(q'_1[E_r]_{\phi_1}))$, where $\psi^*$ is defined as in Lem. 5.

So the sets **shift** (clean $(q'_1[E_r]_{\phi_1})$) and **shift** (clean $(q'_2[E_r]_{\phi_2})$) have the same number of elements, which ensures that $w^b(q'_1, \lambda'_1) = w^b(q'_2, \lambda'_2)$. By summing over all non standard transition labels in $\mathcal{L}^b$, it follows that $a(q'_1) = a(q'_2)$.

3. For any $q'_1, q'_2 \in \mathcal{Q}^b$, $q'_1 \sim_{\mathcal{Q}^b} q'_2 \wedge q'_1 \in \mathcal{I}^b \implies q'_2 \in \mathcal{I}^b \wedge \pi'_0(q'_1) = \pi'_0(q'_2)$ (by assumption);

4. Let $\lambda'_1, \lambda'_2 \in \mathcal{L}^b$ be two transition labels such that $\lambda'_1 \sim_{\mathcal{L}^b} \lambda'_2$. We write $\lambda'_1 = (r_1, q'_1, \phi'_1, \phi'_1)$ and $\lambda'_2 = (r_2, q'_2, \phi'_2, \phi'_2)$. Let $q'_1, q'_2 \in \mathcal{Q}^b$ be two non standard states such that $q'_1 \xrightarrow{\lambda'_1} q'_1'$, and $q'_2 \xrightarrow{\lambda'_2} q'_2'$. We have $\lambda'_1 \sim_{\mathcal{L}^b} \lambda'_2$, so by definition of $\sim_{\mathcal{L}^b}$, we have $q'_1 \sim_{\mathcal{Q}^b} q'_2$ and $q'_1 \sim_{\mathcal{Q}^b} q'_2$.

Then, by definition of $\sim_{\mathcal{L}^b}$, we have $r_1 = r_2$. We write $r_1 = E_\ell \xrightarrow{k} E_r$.

- Whenever the rule $r_1$ is a trivial rule, then no agent is created. Thus both sets **shift** (clean $(q'_1[E_r]_{\phi_1})$) and **shift** (clean $(q'_2[E_r]_{\phi_2})$) are singletons and we have:

$$w^b(q'_1, \lambda'_1) = \frac{k}{\text{sym}(E_\ell)} = w^b(q'_2, \lambda'_2).$$

- Otherwise the cardinal of the set **shift** (clean $(q'_1[E_r]_{\phi_1})$) can be written as $f((c(A), d(A), h(a))_{A \in \mathcal{A}})$ where, for any agent type $A \in \mathcal{A}$, $c(A)$ denotes the number of agents of type $A$ that has been created by the rule, $d(A)$ denotes the number of agents that has been removed by the rule, and $h(A)$ denotes the number of agents that belongs to $q'_1$, for any agent type $A \in \mathcal{A}$.
We notice that the family $(c(A), d(A), h(a))_{A \in \mathcal{A}}$ of triples is preserved by fragment shuffling, so we have:

$$w^b(q_1^b, \lambda_1^b) = \frac{k}{\mathrm{sym}(E_\ell) \cdot f((c(A), d(A), h(A))_{A \in \mathcal{A}})} = w^b(q_2^b, \lambda_2^b)$$

In both case, we have: $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 $Q^b$ such that $q_1^{b'} \sim_{Q^b}^{\sharp} q_2^{b'}$. Let $q_*^b \in Q^b$ be a non standard state, and $\lambda_*^b \in \mathcal{L}^b$ be a non standard transition label. We will prove that the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b}^{\sharp} q_*^b, \lambda^b \sim_{\mathcal{L}^b}^{\sharp} \lambda_*^b, q^b \xrightarrow{\lambda^b} q_1^{b'}\}$ and the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b}^{\sharp} q_*^b, \lambda^b \sim_{\mathcal{L}^b}^{\sharp} \lambda_*^b, q^b \xrightarrow{\lambda^b} q_2^{b'}\}$ are in bijection. Let us write $\lambda_*^b = (r_*, q_*^b, \phi_*, \phi_*^b)$.

- In the case when the rule $r_*$ is a trivial complexation:

The cardinal of the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b}^{\sharp} q_*^b, \lambda^b \sim_{\mathcal{L}^b}^{\sharp} \lambda_*^b, q^b \xrightarrow{\lambda^b} q_1^{b'}\}$ is equal to the number ways a non standard states $\sim_{Q^b}^{\sharp}$-equivalent to $q_*^b$ can be obtained by removing a bond of the same type of the one that has been added by the rule $r_*$, in the non standard state $q_1^{b'}$ (the comparison between the $\sim_{Q^b}^{\sharp}$-equivalence classes of $q_1^{b'}$ and $q_*^b$ gives us the kind of fragments (aka non standard fragments up to $\sim_{Q^b}^{\flat}$-equivalence) that should contain the sites to be freed). This number depends only on the number of embeddings of each non standard fragments into $q_1^{b'}$. Because $q_1^{b'} \sim_{Q^b}^{\sharp} q_2^{b'}$, for each non standard fragment $F^b$, the number of embeddings between $F^b$ and $q_1^{b'}$ is equal to the number of embeddings between $F^b$ and $q_2^{b'}$. As a consequence the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b}^{\sharp} q_*^b, \lambda^b \sim_{\mathcal{L}^b}^{\sharp} \lambda_*^b, q^b \xrightarrow{\lambda^b} q_1^{b'}\}$ and the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b}^{\sharp} q_*^b, \lambda^b \sim_{\mathcal{L}^b}^{\sharp} \lambda_*^b, q^b \xrightarrow{\lambda^b} q_2^{b'}\}$ have the same cardinal.

- In the case when the rule $r_*$ is a trivial dissociation:

The cardinal of the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b}^{\sharp} q_*^b, \lambda^b \sim_{\mathcal{L}^b}^{\sharp} \lambda_*^b, q^b \xrightarrow{\lambda^b} q_1^{b'}\}$ is equal to the number ways a non standard states $\sim_{Q^b}^{\sharp}$-equivalent to $q_*^b$ can be obtained by adding a bond that could have been removed by the rule $r_*$, in the non standard state $q_1^{b'}$. This number depends only on the number of embeddings of each non standard fragments into $q_1^{b'}$. Because $q_1^{b'} \sim_{Q^b}^{\sharp} q_2^{b'}$, for each non standard fragment $F^b$, the number of embeddings between $F^b$ and $q_1^{b'}$ is equal to the number of embeddings between $F^b$ and $q_2^{b'}$. As a consequence the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b}^{\sharp} q_*^b, \lambda^b \sim_{\mathcal{L}^b}^{\sharp} \lambda_*^b, q^b \xrightarrow{\lambda^b} q_1^{b'}\}$ and the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b}^{\sharp} q_*^b, \lambda^b \sim_{\mathcal{L}^b}^{\sharp} \lambda_*^b, q^b \xrightarrow{\lambda^b} q_2^{b'}\}$ have the same cardinal.

- In the case when the rule $r_*$ is a trivial dissociation:

The cardinal of the set $\{(q^b, \lambda^b) \mid q^b \sim_{Q^b}^{\sharp} q_*^b, \lambda^b \sim_{\mathcal{L}^b}^{\sharp} \lambda_*^b, q^b \xrightarrow{\lambda^b} q_1^{b'}\}$ is equal to the number ways a non standard states $\sim_{Q^b}^{\sharp}$-equivalent to $q_*^b$ can be obtained by adding an agent of the type of those that can be
removed by $r_*$ in the non standard state $q_1^{b'}$. The non standard state $q_\star^b$ gives us constraints about the internal states of the site of this agent, and the number and the type of the bonds to put between this agent and the others. Anyway, the cardinal of the set $\{(q^b, \lambda^b) | q^b \sim_{Q^b}^{\sharp} q_\star^b, \lambda^b \sim_{L^b}^{\sharp} \lambda_\star^b, q^b \xrightarrow{\lambda^b} q_1^{b'}\}$ depends only on the number of embeddings of each non standard fragments into $q_1^{b'}$. Because $q_1^{b'} \sim_{Q^b}^{\sharp} q_2^{b'}$, for each non standard fragment $F^b$, the number of embeddings between $F^b$ and $q_1^{b'}$ is equal to the number of embeddings between $F^b$ and $q_2^{b'}$. As a consequence the set $\{(q^b, \lambda^b) | q^b \sim_{Q^b}^{\sharp} q_\star^b, \lambda^b \sim_{L^b}^{\sharp} \lambda_\star^b, q^b \xrightarrow{\lambda^b} q_1^{b'}\}$ and the set $\{(q^b, \lambda^b) | q^b \sim_{Q^b}^{\sharp} q_\star^b, \lambda^b \sim_{L^b}^{\sharp} \lambda_\star^b, q^b \xrightarrow{\lambda^b} q_2^{b'}\}$ have the same cardinal.

- In the case when the rule is not trivial. The proof of Prop. 4.(5) can be lifted to that case, by using Lem. 5 instead of Lem. 4.

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

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

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

Now we give more intuitive explanations about the fragments-based semantics. We shall notice that the elements of the quotient of the set of mixtures by the binary equivalence $\sim_{Q^b}^\sharp$ can be seen as multiset of fragments. Then each non standard mixture $q$ can be decomposed into a set of non standard fragments. By gathering the fragments which are $\sim_{Q^b}^\sharp$-equivalent, we get a multiset of fragments. Furthermore the equivalence relation $\sim_{L^b}^\sharp$ identifies the labels of the transitions which consist in the application of the same rule to the same fragments (and along the same embeddings) within a given mixture.

The following theorem summarizes the result of this section.

**Theorem 6.** Let be an ACM which satisfies Def. 12. Let be a set of fragments that is defined according to Def. 2.3. Then the derived fragment-based semantics is a sound and complete abstraction of the population-based semantics.

*Proof.* By The. 5, $S$ is a sound and complete abstraction of $S^b$. We have proved that $S^\sharp$ is a sound and complete abstraction of $S^b$. Moreover for any two non standard states, $q_1^b \sim_{Q^b} q_2^b$ implies that $q_1^b \sim_{Q^b}^{\sharp} q_2^b$ and for any two non standard states, $\lambda_1^b \sim_{L^b} \lambda_2^b$ implies that $\lambda_1^b \sim_{L^b}^{\sharp} \lambda_2^b$. Moreover, given $q_1^b$ and $q_2^b$ such that $q_1^b \sim_{Q^b} q_2^b$, we have $q_1^b \sim_{Q^b}^{\sharp} q_2^b$. Then:

$$ \mathrm{card}([q_1^b]_{Q^b}^{\sharp}) \cdot \mathrm{card}([q_2^b]_{Q^b}^{\sharp}) = \mathrm{card}([q_2^b]_{Q^b}^{\sharp}) \cdot \mathrm{card}([q_1^b]_{Q^b}^{\sharp}). $$

Thus our abstraction between $S^b$ and $S^\sharp$ can be factored by our abstraction between $S^b$ and $S$.

<figure><img src="image_21.png" /></figure>
<table><thead><tr><th>Model</th><th>early EGF</th><th>EGF/Insulin cross talk</th><th>SFB</th></tr></thead><tbody><tr><td>Species</td><td>356</td><td>2899</td><td>~ 2.10<sup>19</sup></td></tr><tr><td>Differential fragments</td><td>38</td><td>208</td><td>~ 2.10<sup>5</sup></td></tr><tr><td>Stochastic fragments</td><td>356</td><td>247</td><td>~ 2.10<sup>19</sup></td></tr></tbody></table>

**Fig. 13.** Reduction factors for differential fragments [28] and stochastic fragments. We try these reduction methods on three models. The first one, taken from [2], models the early events of the EGF pathway; the second one, taken from [11, table 7], describes the cross-talk between another model of the early events of the EGF pathway and the insulin receptor; whereas the third one is a version of our pilot study on a larger section of the EGF pathway [17, 2, 45, 6].

# 6 Conclusions and future work

Advances in measurement technology for molecular biology will unravel more and more intricacies of the temporal logic in signaling pathways. With this higher resolution, the combinatorial problem that we set out to solve will become more dramatic. The proposed theoretical framework provides a rigorous means to reduce this combinatorial complexity by exploiting the local context on which most protein-protein interactions are conditioned.

More specifically, we show in this paper how to quotient with no error the state space of stochastic bio-molecular systems. The work is motivated by the question whether the quotients used to derive the correct differential semantics is correct in the stochastic semantics as well. We prove that this does not hold always. To show this in a general setting, we develop an abstraction algebra over the weighted labeled transition systems corresponding to the three levels of descriptive granularity. We instantiate this generic framework with a particular specification language, namely the rule-based language Kappa. The proposed approach of quotioning the state space to obtain stochastic fragments is simple and scalable because it is based directly on the specification. In particular, it exploits and extends the notion of a contact map of a rule set. This is of utmost importance because any aggregation method that relies on the enumeration of the state space or even on the enumeration of all reachable molecular species is doomed due to the combinatorial blow-up.

Comparison (eg see Fig. 13) of the obtained dimensionality reduction between the differential fragments and stochastic fragments, shows that the deterministic semantics is less sensitive to species aggregation and thus allows for a coarser fragmentation than the exact stochastic semantics. Indeed only the model of the cross-talk between the early EGF pathway and the insulin receptor has been reduced (this reduction was made possible because two sites in a given protein were completely independent). This emphasizes that stochastic semantics is much harder to reduce than differential semantics. Moreover, control in signaling pathways seems to be too fine grained for allowing exact reduction for their stochastic semantics. Yet, it is very interesting to use our framework in the case when binding and unbinding between sites are made without any test [33]. In this case, the completeness property ensures that the conditional probability that the
system is in a given configuration knowing the number of bonds (for each type
of bonds) is an invariant of the system (providing that we start with isolated
proteins), that depends only on the number of symmetries in configurations.

A practical aspect of automatically deriving stochastic fragments of a rule
set is the following one. Fragments represent abstract species and as such they
can be fed into any general purpose stochastic simulator for chemical kinetics. In
the present paper, we focused on the derivation of the fragments-based seman-
tics, without trying to give an explicit and easily implementable formulation.
Nevertheless, we believe that we can get interesting and practical algorithm for
a fragments-based stochastic simulator, by using the kind of heuristics that are
described in [19, 10]. The idea is to over estimate rule activities by counting com-
ponent wise the number of embedding between each pattern component of rules
and fragments; then each time a computation step is selected, we compute the
probability that this choice is due to the over-count (ie that is a false positive);
in such a case, we remain in the same configuration while advancing time. The
soundness of this approach has been proved in [19].

We plan to address the following issues in our future work. Although we
prove that differential fragments are not a sound abstraction for the stochastic
semantics of bio-molecular systems, we want to address the question whether
one can bound the error if they are nevertheless used in the stochastic setting.
This is of particular interest in the light of the dramatic dimensionality reduc-
tion achieved by differential fragments. For such an approximation property we
need to define a measure of closeness between two stochastic processes or two
transition systems. An approach appealing to us, is the definition of a metric (or
pseudometric) on probability measures [42]. The concept forms also the basis
of [24] and its definition of approximate bisimulation for probabilistic processes.
In systems biology research the Kantorovich distance between measures [42] is
already used in [49] to compare and calibrate simple stochastic models. Having
a distance measure between the exact and the approximate semantics in place,
one can then ask traditional questions of parametric sensitivity of this distance.
Thus, although the herein proposed method and the method in [28] for fragmen-
tation do not depend on kinetic rates, it is anticipated that any such approximate
fragmentation (with a predetermined error bound) will only hold for particular
intervals of kinetic rates.

Another interesting avenue for further work is the combination of stochastic
and differential fragments for the simulation of multi-scale bio-molecular sys-
tems. In particular, systems with very high and very low abundant molecular
agents call for the design of hybrid simulation algorithms [41] that combine dif-
ferential and stochastic semantics.
References

1. Christel Baier and Holger Hermanns. Weak bisimulation for fully probabilistic processes, 1999.

2. Michael L. Blinov, James R. Faeder, Byron Goldstein, and William S. Hlavacek. A network model of early events in epidermal growth factor receptor signaling that accounts for combinatorial complexity. *BioSystems*, 83:136-151, January 2006.

3. Michael L. Blinov, James R. Faeder, and William S. Hlavacek. BioNetGen: software for rule-based modeling of signal transduction based on the interactions of molecular domains. *Bioinformatics*, 20:3289-3292, 2004.

4. Chiara Bodei, Pierpaolo Degano, and Corrado Priami. Constructing specific sos semantics for concurrency via abstract interpretation. In *SAS '98: Proceedings of the 5th International Symposium on Static Analysis*, pages 168-183, London, UK, 1998. Springer-Verlag.

5. Gunter Bolch, Stefan Greiner, Hermann de Meer, and Kishor S. Trivedi. *Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications*. WileyBlackwell, 2nd edition edition, May 2006.

6. Frances A. Brightman and David A. Fell. Differential feedback regulation of the mapk cascade underlies the quantitative differences in egf and ngf signalling in pc12 cells. *FEBS Letters*, 482(3):169-174, October 2000.

7. Peter Buchholz. Exact and ordinary lumpability of finite Markov chains. *Journal of Applied Probability*, 31:59-75, 1994.

8. Luca Cardelli. Brane calculi. In *Proceedings of BIO-CONCUR'03, Marseille, France*, volume 180 of *Electronic Notes in Theoretical Computer Science*. Elsevier, 2003.

9. Alessio Coletta, Roberta Gori, and Francesca Levi. Approximating probabilistic behaviors of biological systems using abstract interpretation. *ENTCS*, 229(1):165-182, 2009.

10. Joshua Colvin, Michael I. Monine, James R. Faeder, William S. Hlavacek, Daniel D. Von Hoff, and Richard G. Posner. Simulation of large-scale rule-based models. *Bioinformatics*, 25(7):910-917, 2009.

11. Holger Conzelmann, Dirk Fey, and Ernst D. Gilles. Exact model reduction of combinatorial reaction. *BMC Syst Biol*, 2(78):342-351, 2008.

12. Agostino Cortesi, Gilberto Filé, Francesco Ranzato, Roberto Giacobazzi, and Catuscia Palamidessi. Complementation in abstract interpretation. *ACM Trans. Program. Lang. Syst.*, 19(1):7-47, 1997.

13. Patrick Cousot. *Méthodes itératives de construction et d'approximation de points fixes d'opérateurs monotones sur un treillis, analyse sémantique de programmes (in French)*. Thèse d'État ès sciences mathématiques, Université Joseph Fourier, Grenoble, France, 21 March 1978.

14. Patrick Cousot and Radhia Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In *Conference Record of the Fourth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages*, pages 238-252, 1977.

15. Patrick Cousot and Radhia Cousot. Systematic design of program analysis frameworks. In *Conference Record of the Sixth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages*, pages 269-282, San Antonio, Texas, 1979. ACM Press, New York, NY.

16. Patrick Cousot and Radhia Cousot. Abstract interpretation frameworks. *Journal of Logic and Computation*, 2(4):511-547, 1992.
17. Vincent Danos, Jérôme Feret, Walter Fontana, Russ Harmer, and Jean Krivine. Rule-based modelling of cellular signalling, invited paper. In *Proceedings of the Eighteenth International Conference on Concurrency Theory, CONCUR '2007, Lisbon, Portugal*, volume 4703 of *Lecture Notes in Computer Science*, pages 17–41, Lisbon, Portugal, 3–8 September 2007. Springer, Berlin, Germany.

18. Vincent Danos, Jérôme Feret, Walter Fontana, Russel Harmer, and Jean Krivine. Rule-based modelling, symmetries, refinements. In *Proceedings of Formal Methods in Systems Biology (FMSB'08)*, LNBI, 2008.

19. Vincent Danos, Jérôme Feret, Walter Fontana, and Jean Krivine. Scalable simulation of cellular signaling networks. In Zhong Shao, editor, *APLAS*, volume 4807 of *Lecture Notes in Computer Science*, pages 139–157. Springer, 2007.

20. Vincent Danos, Jérôme Feret, Walter Fontana, and Jean Krivine. Abstract interpretation of reachable complexes in biological signalling networks. In *Proceedings of the 9th International Conference on Verification, Model Checking and Abstract Interpretation (VMCAI'08)*, volume 4905, pages 42–58, 2008.

21. Vincent Danos and Jean Krivine. Formal molecular biology done in CCS. In *Proceedings of BIO-CONCUR'03, Marseille, France*, volume 180 of *Electronic Notes in Theoretical Computer Science*, pages 31–49. Elsevier, 2003.

22. Vincent Danos and Cosimo Laneve. Core formal molecular biology. *Theoretical Computer Science*, 325:69–110, 2003.

23. Josée Desharnais, Abbas Edalat, and Prakash Panangaden. Bisimulation for labelled Markov processes. *Inf. Comput.*, 179(2):163–193, 2002.

24. Josée Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. Metrics for labelled Markov processes. *Theoretical computer science*, 318(3):323–354, 2004.

25. Alessandra Di Pierro and Herbert Wiklicky. Probabilistic abstract interpretation and statistical testing. In *Proceedings of the Second Joint International Workshop on Process Algebra and Probabilistic Methods, Performance Modeling and Verification (PAPM-PROBMIV'02)*, pages 211–212. Springer-Verlag, 2002.

26. Laurent Doyen, Thomas A. Henzinger, and Jean-François Raskin. Equivalence of labeled Markov chains. *Int. J. Found. Comput. Sci.*, 19(3):549–563, 2008.

27. Steven Eker, Merrill Knapp, Keith Laderoute, Patrick Lincoln, José Meseguer, and Kemal Sonmez. Pathway logic: Symbolic analysis of biological signaling. In *Proceedings of the Pacific Symposium on Biocomputing*, pages 400–412, January 2002.

28. Jérôme Feret, Vincent Danos, Jean Krivine, Russ Harmer, and Walter Fontana. Internal coarse-graining of molecular systems. *Proceedings of the National Academy of Sciences*, 106(16):6453–6458, April 2009.

29. Daniel T. Gillespie. Exact stochastic simulation of coupled chemical reactions. *J Phys Chem*, 81(25):2340–2361, 1977.

30. William S. Hlavacek, James R. Faeder, Michael L. Blinov, Alan S. Perelson, and Byron Goldstein. The complexity of complexes in signal transduction. *Biotechnol. Bio-eng.*, 84:783–794, 2005.

31. William S. Hlavacek, James R. Faeder, Michael L. Blinov, Richard G. Posner, Michael Hucka, and Walter Fontana. Rules for Modeling Signal-Transduction Systems. *Science's STKE*, 2006(344), 2006.

32. John Kemeny and James L. Snell. *Finite Markov Chains*. Van Nostrand, 1960.

33. Heinz Koepp, Linus Schumacher, and Vincent Danos. A statistical analysis of receptor clustering using random graphs. In *Proceedings of the sixth International Workshop on Computational Systems Biology (WCSB)*, volume 48, pages 95–98, Aarhus, Denmark, June 10-12 2009. TICSP.
34. Kim G. Larsen and Arne Skou. Bisimulation through probabilistic testing (preliminary report). In *POPL '89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages*, pages 344–352, New York, NY, USA, 1989. ACM.

35. Larry Lok and Roger Brent. Automatic generation of cellular reaction networks with moleculizer 1.0. *Nat Biotechn*, 1:131–136, 2005.

36. Donald A. McQuarrie. Stochastic approach to chemical kinetics. *Journal of Applied Probability*, 4(3):413–478, 1967.

37. Robin Milner. *Communicating and mobile systems: the π-calculus*. Cambridge University Press, Cambridge, 1999.

38. David Monniaux. Abstract interpretation of probabilistic semantics. In *Proceeding of the Seventh International Static Analysis Symposium (SAS'00)*, number 1824 in LNCS, pages 322–339. Springer Verlag, 2000.

39. David Monniaux. An abstract Monte-Carlo method for the analysis of probabilistic programs (extended abstract). In *Proceedings of the 28th Symposium on Principles of Programming Languages (POPL'01)*, pages 93–101. ACM, 2001.

40. Elaine Murphy, Vincent Danos, Jerome Feret, Russell Harmer, and Jean Krivine. Rule based modelling and model refinement. In Huma Lodhi and Stephen Mungleton, editors, *Elements of Computational Systems Biology*. Wiley Book Series on Bioinformatics, 2009.

41. Jürgen Pahle. Biochemical simulations: stochastic, approximate stochastic and hybrid approaches. *Brief Bioinform*, 10(1):53–64, 2009.

42. Svetlozar T. Rachev. *Probability metrics and the stability of stochastic models*. Probability and Mathematical Statistics. Wiley, New York, 1991.

43. Aviv Regev, Ekaterina M. Panina, William Silverman, Luca Cardelli, and Ehud Shapiro. BioAmbients: an abstraction for biological compartments. *Theoretical Computer Science*, 325(1):141–167, 2004.

44. Aviv Regev, William Silverman, and Ehud Shapiro. Representation and simulation of biochemical processes using the π-calculus process algebra. In R. B. Altman, A. K. Dunker, L. Hunter, and T. E. Klein, editors, *Pacific Symposium on Biocomputing*, volume 6, pages 459–470, Singapore, 2001. World Scientific Press.

45. Birgit Schoeberl, Claudia Eichler-Jonsson, Ernst D. Gilles, and Gertraud Müller. Computational modeling of the dynamics of the map kinase cascade activated by surface and internalized egf receptors. *Nat Biotechnol*, 20(4):370–375, April 2002.

46. Bruce E. Shapiro, Andre Levchenko, and Eric Mjolsness. Automatic model generation for signal transduction with application to MAP kinase pathways. In H. Kirtano, editor, *Foundations of Systems Biology*, chapter 1. MIT Press, 2001.

47. Ana Sokolova and Erik P. de Vink. On relational properties of lumpability. In *Proceedings of the 4th PROGRESS symposium on embedded systems*, 2003.

48. Ty M. Thomson. *Models and analysis of yeast mating response: tools for model building, from documentation to time-dependent stimulation*. PhD thesis, Massachusetts Institute of Technology (MIT), Cambridge MA, USA, 2008.

49. David Thorsley and Eric Klavins. Model reduction of stochastic processes using Wasserstein pseudometrics. In *Proceedings of the 2008 American Control Conference*, pages 1374–1381, June 11–13 2008.

50. Christopher T. Walsh. *Posttranslation Modification of Proteins: Expanding Nature's Inventory*. Roberts and Co. Publisher, 2006.

51. Darren J. Wilkinson. *Stochastic Modelling for Systems Biology*. Chapman & Hall, 2006.