Shift equivalence and derivation traces

From a truly concurrent perspective two derivations should be considered as equivalent when they apply the same productions to the “same” subgraph of a certain graph, even if the order in which the productions are applied may be different. The basic idea of equating derivations which differ only for the order of independent production applications is formalized in the literature through the notion of shift equivalence [14,36,4]. The shift equivalence is based on the possibility of sequentializing a parallel direct derivation (the analysis

construction) and on the inverse construction (synthesis), which is possible only in the case of sequential independence. The union of the shift and abstraction equivalences will yield the (concatenable) truly concurrent equivalence, whose equivalence classes are the (concatenable) derivation traces.

Let us start by defining the key notion of sequential independence.

Definition 3.3.6 (sequential independence)

A derivations δ₁; δ₂, consisting of two direct derivations δ₁ : G ⇒_q0,g1 X and δ₂ : X ⇒_q⁰⁰_,g2 H (as in Figure 3.9) is sequentially independent if g₂(L₂) ∩ h₁(R₁) ⊆ g₂(l₂(K₂)) ∩ h₁(r₁(K₁)); in words, if the images in X of the left-hand side of q⁰⁰ and of the right-hand side of q⁰ overlap only on items that are preserved by both derivation steps. In categorical terms, this condition can be expressed by requiring the existence of two arrows s : L2 → D1 and u : R1→ D2such that d1◦ s = g2 and b2◦ u = h1.

Example 3.3 (sequential independence)

Consider the derivation of Figure 3.5. The first two direct derivations are not sequential independent; in fact, the edge 3 : req of graph G1 is in the image of both the right-hand side of the first production and the left-hand side of the second one, but it is in the context of neither the first nor the second direct derivation. On the contrary, in the same figure both the derivation from G1

to G3 and that from G2 to G4 are sequential independent. 2 Notice that, differently from what happens for other formalisms, such as Petri nets or term rewriting, two rewriting steps δ₁and δ₂do not need to be applied at completely disjoint matches to be independent. The graphs to which δ₁ and δ₂are applied can indeed overlap on something that is preserved by both rewriting steps. According to the interpretation of preserved items as read-only resources, this fact can be expressed by saying that graph rewriting allows for the concurrent access to read resources.

The next well-known result states that every parallel direct derivation can be sequentialized in an arbitrary way as the sequential application of the compo-nent productions, and, conversely, that every sequential independent derivation can be transformed into a parallel direct derivation. These constructions, in general non-deterministic, are used to define suitable relations among deriva-tions (see, e.g., [14,37,5]). Unlike the usual definition of analysis and synthesis, we explicitly keep track of the permutation of the applied productions induced by the constructions. Therefore we first introduce some notation for permuta-tions.

L1

The identity permutation on n is denoted by Πⁿ_id. The composition of two permutations Π₁ and Π₂ on n, denoted by Π₁◦ Π₂, is their composition as functions, while the concatenation of two permutations Π₁ on n₁ and Π₂ on n2, denoted by Π1| Π2, is the permutation on n1+ n2 defined as

Π1| Π2(x) =

 Π1(x) if 1 ≤ x ≤ n1

Π2(x − n1) + n1 if n1< x ≤ n2

Concatenation and composition of permutations are clearly associative.

Proposition 3.3.8 (analysis and synthesis)

Let ρ : G ⇒_q H be a parallel direct derivation using q = q₁+ . . . + q_k : (L ← K^l → R). Then for each partition hI = {i^r ₁, . . . , i_n}, J = {j₁, . . . , j_m}i of k (i.e., I ∪ J = k and I ∩ J = ∅) there is a constructive way—in general non-deterministic—to obtain a sequential independent derivation ρ⁰ : G ⇒_q⁰ X ⇒q⁰⁰ H, called an analysis of ρ, where q⁰ = qi₁ + . . . + qi_n, and q⁰⁰ = qj₁ + . . . + qj_m as in Figure 3.9. If ρ and ρ⁰ are as above, we shall write ρ ≡^an_Π ρ⁰, where Π is the permutation on k defined as Π(ix) = x for x ∈ n, and Π(jx) = n + x for x ∈ m.

Conversely, let ρ : G ⇒_q⁰ X ⇒_q⁰⁰ H be a sequential independent derivation.

Then there is a constructive way to obtain a parallel direct derivation ρ⁰ = G ⇒_q⁰_+q⁰⁰ H, called a synthesis of ρ. In this case, we shall write ρ ≡^syn_Π ρ⁰,

where Π = Π^#ρ_id . 2

Informally, two derivations are shift equivalent if one can be obtained from the other by repeatedly applying the analysis and synthesis constructions. The next definition emphasizes the fact that the sets of productions applied in two

shift equivalent derivations are related by a permutation which is constructed inductively starting from the permutations introduced by analysis and synthe-sis.

Definition 3.3.9 (shift equivalence)

Derivations ρ and ρ⁰ are shift equivalent via permutation Π, written ρ ≡^sh_Π ρ⁰, if this can be deduced by the following inference rules:

(SH−id)

ρ ≡^sh

Π^#ρ_id ρ

(SH−∅) d ◦ b⁻¹= idG

G ≡^sh_∅ Gh∅,∅,∅,b,di

⇒_∅ G

(SH−an)

ρ ≡^an_Π ρ⁰ ρ ≡^sh_Π ρ⁰

(SH−syn)

ρ ≡^syn_Π ρ⁰

ρ ≡^sh_Π ρ^{0 (SH−sym)}

ρ ≡^sh_Π ρ⁰

ρ⁰≡^sh_Π−1ρ ^(SH−trans)

ρ ≡^sh_Π ρ⁰, ρ⁰ ≡^sh_Π0 ρ⁰⁰ ρ ≡^sh_Π0◦Πρ⁰⁰

(SH−comp)

ρ1≡^sh_Π

1 ρ⁰₁, ρ2≡^sh_Π

2 ρ⁰₂, τ (ρ1) = σ(ρ2) ρ1; ρ2≡^sh_Π

1|Π2 ρ⁰₁; ρ⁰₂

Note that by (SH − ∅) an empty direct derivation is shift equivalent to the identity derivation G if and only if the induced isomorphism is the identity.

The shift equivalence is the equivalence relation ≡^sh defined as ρ ≡^sh ρ⁰ iff ρ ≡^sh_Π ρ⁰ for some permutation Π.

It is worth stressing that the shift equivalence abstracts both from the order in which productions are composed inside a single direct parallel step and from the order in which independent productions are applied at different direct derivations.

Example 3.4 (shift equivalence)

Figure 3.10 shows a derivation ρ⁰ which is shift equivalent to derivation ρ of Figure 3.5. It is obtained by applying the synthesis construction to the

sub-derivation of ρ from G₁ to G₃. 2

Despite the unusual definition, borrowed from [18], it is easy to check that the shift equivalence just introduced is the same as in [14,4,15]. From the defini-tions of the shift equivalence and of the analysis and synthesis construcdefini-tions, it follows that ρ ≡^shρ⁰implies that ρ and ρ⁰ have the same order and the same source and target graphs (i.e., #ρ = #ρ⁰, σ(ρ) = σ(ρ⁰), and τ (ρ) = τ (ρ⁰);

by the way, this guarantees that rules (SH − comp) and (SH − trans) are well-defined. The shift equivalence can be extended in a natural way to decorated derivations.

5:S

Figure 3.10: A derivation ρ⁰ in grammar C-S, shift-equivalent to derivation ρ of Figure 3.5.

Definition 3.3.10

The shift equivalence on decorated derivations, denoted with the same symbol

≡^sh, is defined by hm, ρ, M i ≡^shhm, ρ⁰, M i if ρ ≡^shρ⁰.

Equivalence ≡^shdoes not subsume abstraction equivalence, since, for example, it cannot relate derivations starting from different but isomorphic graphs. We introduce a further equivalence on decorated derivations, obtained simply as the union of ≡^abs and ≡^sh, and we call it truly-concurrent (or tc-) equivalence, since in our view it correctly equates all derivations which are not distinguish-able from a true concurrency perspective, at an adequate degree of abstraction from representation details. A small variation of this equivalence is introduced as well, called ctc-equivalence, where the first “c” stays for “concatenable”.

Equivalence classes of (c)tc-equivalent decorated derivations are called (con-catenable) derivation traces, a name borrowed from [38].

Definition 3.3.11 (truly-concurrent equivalences and traces)

Two decorated derivations ψ and ψ⁰ are ctc-equivalent via permutation Π, written ψ ≡^c_Πψ⁰, if this can be deduced by the following inference rules:

(CTC−abs) ψ ≡^absψ⁰ called the concatenable truly concurrent (ctc-) equivalence. Equivalence classes

of derivations with respect to ≡^care denoted as [ψ]_cand are called concatenable derivation traces. A derivation trace is an equivalence class of derivations with respect to the truly-concurrent (tc-) equivalence ≡ defined by the following rules:

(TC−ctc)

ψ ≡^c_Πψ⁰

ψ ≡_Πψ^{0 (TC−iso)}

ψ ≡Πψ⁰ αdiscrete decor. deriv. s.t.ψ⁰; αis defined ψ ≡_Πψ⁰; α

Equivalently, we could have defined tc-equivalence as ψ ≡Π ψ⁰ if and only if ψ ≡^c_Π hmψ⁰, ρψ⁰, M⁰i, for some isomorphism M⁰ : Can(τ (ψ⁰)) → τ (ψ⁰). In-formally, differently from ctc-equivalence, tc-equivalence does not take into account the decorations of the target graphs of derivations, that is their end-ing interface, and this is the reason why derivation traces are not concatenable.

Derivation traces will be used in Section 3.6 to define an event structure se-mantics for a graph grammar.

Concatenable derivation traces, instead, are naturally equipped with an oper-ation of sequential composition, inherited from concrete decorated derivoper-ations, which allows us to see them as arrows of a category having abstract graphs as objects. Such category is called the category of concatenable derivation traces (or the abstract truly concurrent model of computation) of the grammar.

Definition 3.3.12 (category of concatenable derivation traces) The category of concatenable derivation traces of a grammar G, denoted by Tr[G], is the category having abstract graphs as objects, and concatenable derivation traces as arrows. In particular, if ψ : G ⇒^∗_G H then [ψ]c is an arrow from [G] to [H]. The identity arrow on [G] is the ctc-equivalence class of a discrete derivation hi, G, ii, where i is any isomorphism from Can(G) to G.

The composition of arrows [ψ]_c : [G] → [H] and [ψ⁰]_c : [H] → [X] is defined as [ψ ; ψ⁰⁰]_c : [G] → [X], where ψ⁰⁰∈ [ψ⁰]_c is a decorated derivation such that ψ ; ψ⁰⁰ is defined.

Category Tr[G] is well-defined because so is the sequential composition of ar-rows: in fact, if ψ1 ≡^c ψ2 and ψ⁰₁ ≡^c ψ₂⁰ then (if defined) ψ1; ψ₁⁰ ≡^c ψ2; ψ⁰₂ (hence the attribution “concatenable”). As for abstract derivations, whenever τ (ψ) ' σ(ψ⁰), it is always possible to concatenate the corresponding traces, namely one can always find a derivation ψ⁰⁰∈ [ψ⁰]c such that ψ ; ψ⁰⁰is defined.