In contrast to the standard physical theories which model systems by the continuum, Petri proposed a combinatorial representation of a spacetime — concurrent structures (with occurrence nets as a special case thereof) in which notions corresponding to the relativistic concepts of world line and causal cone can be defined by means of the concurrency and causal dependence relations, repectively. As a result, the density notion of the continuum model is replaced by several properties — so called concurrency axioms (including K-density, N-density, etc.). K-density is based on the idea that at any time instant, any sequential subprocess of a concurrent structure must be in some state or changing its state. N-density can be viewed as a sort of local density. Furthermore, it has turned out that concurrency axioms allow avoiding inconsistency between syntactic and semantic representations of processes and, thereby, to exclude unreasonable processes represented by the concurrent structures.
Petri’s occurrence nets model system behaviors by occurrences of local states (also
called conditions) and of events which are partially ordered. The partial order is
interpreted as a kind of causal dependency relation. Also, occurrence nets are endowed
with a symmetric, but in general non-transitive, concurrency relation — absence of the
causality. Poset models do not discriminate between conditions and events. The power
and limitations of concurrency axioms in the context of occurrence nets [
It is known that some aspects of concurrent behavior (e.g., the specification of
priorities, error recovery, inhibitor nets, treatment of simultaneity, etc.) are to some extent
problematic to be dealt with using only partially ordered causality based models. One
way to cope with the problems is to utilize the model of a so called relational
structure — a set of elements (systems events) with a number of different kind relations
on it. The authors of the papers [
In this paper, we intend to get a better understanding of the space-time nature of concurrency axioms, by establishing their interrelations and revealing their algebraic lattice views, in the context of a subclass of relational structures with completely distinct, irreflexive relations on countable sets of elements. 2
Introduce some notions and notations which will be useful throughout the text.
Sets and relations. Given a set X and a relation R ⊆ X × X, • R is cyclic iff there exists a sequence of distinct elements x1, . . . , xk ∈ X (k > 1) such that xj R xj+1 (1 ≤ j ≤ k − 1) and xk R x1, • R is acyclic iff it is not cyclic, • R is antisymmetric iff (x R x′) ∧ (x 6= x′) ⇒ ¬(x′ R x), for all x, x′ ∈ X, • R is transitive iff (x R x′) ∧ (x′ R x′′) ⇒ (x R x′′), for all x, x′, x′′ ∈ X, • R is irreflexive iff ¬(x R x), for all x ∈ R, • Rα = R ∪ id (the reflexive closure of R), • Rβ = R ∪ R−1 (the symmetric closure of R), • Rγ = Rβ ∪ id (the reflexive and symmetric closure of R), • Rδ = (R \ id) \ (R \ id)2 (the irreflexive, intransitive relation), if R is a transitive relation, and Rδ = R, otherwise,
Notice that if a relation R is irreflexive and transitive, then it is acyclic and antisymmetric, i.e. a (strict) partial order, and, moreover, Rδ is the immediate predecessor relation.
Given elements x, x1, x2 ∈ X, subsets A ⊆ X′ ⊆ X, and a relation R ⊆ X × X, • [x1 R x2] = {x ∈ X | x1 Rα x Rα x2}, • Rx = {x′ ∈ X | x′ Rδ x}, xR = {x′ ∈ X | x Rδ x′}, • RA = {x′ ∈ X | ∃x ∈ A : (x′ Rα x)}, AR = {x′ ∈ X | ∃x ∈ A : (x Rα x′)}, • RA = {x′ ∈ X | ∀x ∈ A : (x′ R x)}, AR = {x′ ∈ X | ∀x ∈ A : (x R x′)}, • A is a (maximal) R-clique of X′ iff A is a (maximal) set containing only pairwise (R ∪ id|X′ )-related elements of X′, • A is an R-closed set of X′ iff ARR = (AR)R = A. The family of all the R-closed sets of X′ is denoted by RCl(X′).
Partially ordered sets and lattices. A partially ordered set (poset) is a set together with a partial order ≤, i.e. a binary relation which is reflexive, transitive and antisymmetric. The powerset P(X) of a set X together with inclusion ⊆ is a poset.
X it holds: 1. A ⊆ C(A) (C is extensive), 2. A ⊆ B ⇒ C(A) ⊆ C(B) (C is monotonic), 3. C(C(A)) = C(A) (C is idempotent).
Let A ⊆ X ⊆ P(X), and P = (X , ⊆) be a poset. Then, • R ∈ X is an upper bound (lower bound) of A if A ⊆ R (R ⊆ A) for all A ∈ A.
T ∈ X is called the least upper bound (l.u.b.) of A if it is an upper bound, and T ⊆ R, for all upper bounds R of A; T is the greatest lower bound (g.l.b.) of A if it is a lower bound, and R ⊆ T , for all lower bounds R of A, • P is a lattice iff every two elements in X have both a g.l.b. (denoted ∧) and a l.u.b.
(denoted ∨), • a lattice P is complete iff every subset of X has both a l.u.b. and a g.l.b., • a complete lattice P is algebraic iff for all x ∈ X it holds x = W{k ∈ K(P) | k ⊆ x}, where K(P) ⊆ X denotes the set of compact elements of P. An element k ∈ X is said to be compact in the lattice P iff, for every S ⊆ X such that k ⊆ W S, it holds that k ⊆ W T , for some finite T ⊆ S. 3
In this section, we define a slight modification of the model of relational structures
whose subclasses are put forward and studied in the papers [
Definition 1. A relational structure is a tuple S = (E, V1, . . . , Vn) (n ≥ 1), where • E is a countable set of elements, • V1, . . . , Vn ⊆ E × E are irreflexive relations such that • S1≤i≤n Viβ = (E × E) \ id, • Viβ ∩ Vjβ = ∅, for all 1 ≤ i 6= j ≤ n.
Clearly, Winskel’s event structures with forward hereditary conflict [
From now on, we shall use P , Q and R to denote the relations on E of the form SV ∈V V , where V ⊆ {Vi, Vj | 1 ≤ i, j ≤ n, Vi and Vj possess the same relation properties}.
Consider the definitions of auxiliary properties of relational structures which will be useful in further considerations. We shall call a relational structure S • P -finite iff any P -clique of E is finite, • P -degree-finite iff | Pe ∪ eP | < ∞, for all e ∈ E, • P -degree-restricted iff Pe1 ∩ Pe2 6= ∅ ⇒ |Pe1| = |Pe2| = 1, for all e1, e2 ∈ E, • P -discrete iff | [e1 P e2] ∩ E′ | < ∞, for all e1, e2 ∈ E and P -cliques E′ of E, • P -interval-finite iff |[e1 P e2]| < ∞, for all e1, e2 ∈ E, • ▽P QR-free iff in any maximal (P ∪ Q ∪ R)-clique of E, there are no distinct elements e1, e2, and e3 such that e1 P e2 Q e3 R e1.
From now on we shall consider only P -discrete relational structures, whenever P is a transitive relation, and call them simply relational structures. 4
The notion of K-density and other concurrency axioms introduced by Petri [
Define concurrency axioms as properties of relational structures.
• Ee is KP Q-dense iff for any maximal P -clique E′ of Ee and for any maximal Qclique E′′ of Ee, E′ ∩ E′′ is a (unique) maximal (P ∩ Q)-clique of Ee, • Ee is KP Q-crossing iff for any maximal P -clique E′ of Ee and for any maximal
Q-clique E′′ of Ee, E′ ∩ PE′′ 6= ∅ and E′ ∩ E′′P 6= ∅, • Ee is ⊲⊳P Q-dense iff whenever (e0 P e1 Q e2) and (e0 Q e3 P e2), then (e0 P δ e2) =⇒ (e3 P e1), for all distinct elements e0, e1, e2, e3 ∈ Ee, • Ee is ⊲⊳βP Q-dense iff whenever (e0 P β e1 Qβ e2) and (e0 Qβ e3 P β e2), then (e0 P δβ e2) =⇒ (e3 P β e1), for all distinct elements e0, e1, e2, e3 ∈ Ee, • S is KP Q-dense (KP Q-crossing, ⊲⊳ P Q-dense, ⊲⊳βP Q-dense, respectively) iff any maximal w.r.t. E clique Ee of (P ∪ Q) is KP Q-dense (KP Q-crossing, ⊲⊳P Q-dense, ⊲⊳βP Q-dense, respectively).
The following results state the relationships between the properties defined so far.
S is ⊲⊳βP Q-dense ⇐⇒ S is ⊲⊳P Q-dense.
Example 2. Consider the relational structures S2–S6 shown in Fig. 2. It is easy to see that S2 = (E2, V ′, V ′′), with the transitive or symmetric relation V ′ and the symmetric relation V ′′, is ⊲⊳βV ′V ′′ - and ⊲⊳V ′V ′′ -dense. On the other hand, the relational structure S3 = (E3, V ′, V ′′, V ′′′), with the transitive or symmetric relation V ′ and the symmetric relation V ′′′, is neither ⊲⊳V ′V ′′′ - nor ⊲⊳βV ′V ′′′ -dense because in the maximal (V ′ ∪ V ′′′)-clique {e2, e3, e4, e5, e7, e8, e9, e10} of E3 there are distinct elements e2, e3, e4, e5 such that (e2 V ′ e3 V ′′′ e4), (e2 V ′′′ e5 V ′ e4), and (e2 (V ′)δ e4) but ¬(e5 V ′ e3). The relational structure S4 = (E4, V ′, V ′′) with the non-transitive and non-symmetric relation V ′ and the symmetric relation V ′′, is ⊲⊳V ′V ′′ -dense but not ⊲⊳βV ′V ′′ -dense. Indeed, in the maximal (V ′ ∪ V ′′)-clique {e1, . . . , e6} of E4 there are elements e1, e2, e3, e4 such that (e2 (V ′)β e1 (V ′′)β e3), (e2 (V ′′)β e4 (V ′)β e3), and (e2 ((V ′)δ)β e3) but ¬(e4 (V ′)β e1). The same holds for the relational structure S5 = (E5, V ′, V ′′) with the transitive or symmetric relation V ′ and the asymmetric relation V ′′. Truly, in the maximal (V ′ ∪ V ′′)-clique {e1, . . . , e4} of E5 there are distinct elements e1, e2, e3, e4 such that (e1 (V ′)β e2 (V ′′)β e4), (e1 (V ′′)β e3 (V ′)β e4), and (e1 ((V ′)δ)β e4) but ¬(e3 (V ′)β e2). The relational structure S6 = (E6, V ′, V ′′) with the non-transitive and non-symmetric relation V ′ is ⊲⊳βV ′V ′′ -dense but not ⊲⊳V ′V ′′ dense. In fact, in the maximal (V ′ ∪ V ′′)-clique {e1, . . . , e4} of E there are distinct elements e1, e2, e3, e4 such that (e1 V ′ e2 V ′′ e4), (e1 V ′′ e3 V ′ e4), and (e1 V ′δ e4) but ¬(e3 V ′ e2).
Proposition 2. Let S be a ⊲⊳βP Q-dense relational structure with distinct relations P and Q, and let P be a transitive relation. Then,
Example 3. First, consider the relational structures S2 = (E2, V ′, V ′′) and S3 = (E3, V ′, V ′′, V ′′′) shown in Fig. 2. We know that S2, with the transitive relation V ′ and the symmetric relation V ′′, is ⊲⊳βV ′V ′′ -dense (see Example 2). It is easy to check that S2 is KV ′V ′′ -dense and KV ′V ′′ -crossing. On the other hand, the relational structure S3, with the transitive relation V ′ and the symmetric relation V ′′, is not ⊲⊳βV ′V ′′′ -dense (see Example 2) It is easy to verify that S3 is KV ′V ′′′ -crossing. However, S3 is not KV ′V ′′′ dense because in the maximal (V ′ ∪ V ′′′)-clique Ee = {e2, e3, e4, e5, e7, e8, e9, e10} of E3 the intersection of the maximal V ′-clique {e2, e4, e7, e10} of Ee with the maximal V ′′′-clique {e3, e5} of Ee is empty. Next, contemplate the relational structures S7 = (E7, V ′, V ′′) and S8 = (E8, V ′, V ′′) depicted in Fig. 3. The relational structure S7 with the transitive relation V ′ and the symmetric relation V ′′, is ⊲⊳βP Q-dense but neither KV ′V ′′ -dense nor KV ′V ′′ -crossing since in the maximal (V ′ ∪ V ′′)-clique Ee = {e1, e2, . . .} of E7 the intersection of the maximal V ′-clique E′ = {e2·k+1 | k ≥ 0} of Ee with the maximal V ′′-clique E′′ = {e2·k | k ≥ 1} of Ee is empty, and, moreover, the intersection of E′ with E′′V ′ is also empty, because E′′V ′ = E′′. Further, the relational structure S8, with the non-transitive relation V ′ and the symmetric relation V ′′, is ⊲⊳βV ′V ′′ -dense and KV ′V ′′ -crossing but not KV ′V ′′ -dense because in the maximal (V ′ ∪ V ′′)-clique Ee = {e1, e2, . . .} of E8 the intersection of the maximal V ′-clique {e2·k+1 | k ≥ 0} of Ee with the maximal V ′′-clique {e2·k | k ≥ 1} of Ee is empty.
S is KP Q-dense ⇐⇒ S is ⊲⊳βP Q-dense.
Example 4. First, again consider the relational structures S2 = (E2, V ′, V ′′) and S3 = (E3, V ′, V ′′, V ′′′) shown in Fig. 2. We know that S2, with the transitive relation V ′ and the symmetric relation V ′′, is ⊲⊳βV ′V ′′ -dense (see Example 2) and KV ′V ′′ -dense (see Example 3). Notice that S2 is V ′- and V ′′-finite. On the other hand, the relational structure S3, with the transitive relation V ′ and the symmetric relation V ′′, is neither ⊲⊳βV ′V ′′′ -dense (see Example 2) nor KV ′V ′′ -dense (see Example 3). Moreover, S3 is V ′- and V ′′-finite. Next, contemplate the relational structures S8 = (E8, V ′V ′′) and S9 = (E9, V ′, V ′′) depicted in Fig. 3. We know from Example 3 that S8, with the transitive relation V ′ and the symmetric relation V ′′, is ⊲⊳βV ′V ′′ -dense but not KV ′V ′′ dense. At the same time, S8 is neither V ′- nor V ′′-finite. The relational structure S9, with the non-transitive relation V ′ and the symmetric relation V ′′, is KV ′V ′′ -dense but not ⊲⊳βV ′V ′′ -dense because in the maximal (V ′ ∪ V ′′)-clique {e1, . . . , e5} of E9, there are distinct elements e1, e2, e3, e4 such that e1 V ′ e2 V ′′ e4, e1 V ′′ e3 V ′ e4, and e1 V ′ e4 but ¬(e3 V ′ e2).
distinct relations P , Q, and R,
S is KP Q-dense ⇐⇒ S is KPeQe -dense, where Pe = (P ∪ R) and Qe = (Q ∪ R).
Example 5. Consider the relational structures S10–S13, with the transitive relation V ′ and the symmetric relations V ′′ and V ′′′, shown in Fig. 4. It is easy to check that S10 = (E10, V ′, V ′′, V ′′′) is KV ′′V ′′′ -dense, ▽V ′V ′′V ′′′ -free, and KVe ′′Ve ′′′ -dense, where Ve ′′ = V ′ ∪ V ′′ and Ve ′′′ = V ′ ∪ V ′′′. Clearly, S9 is V ′-, V ′′- and V ′′′finite. It is not difficult to see that the relational structure S11 = (E11, V ′, V ′′, V ′′′) is KV ′′V ′′′ -dense, and V ′′- and V ′′′-finite. However, S11 is neither ▽V ′V ′′V ′′′ -free, because e1 V ′ e4 V ′′ e5 V ′′′ e1, nor KVe ′′Ve ′′′ -dense, because the intersection of the maximal Ve ′′-clique {e3, e4, e7} of Ee and the maximal Ve ′′′-clique {e1, e3, e6} of Ee is not a maximal V ′-clique of Ee where Ve ′′ = V ′ ∪ V ′′, Ve ′′′ = V ′ ∪ V ′′′, and Ee = {e1, . . . , e7} is the only maximal Ve ′′ ∪ Ve ′′′-clique of E11. The relational structure S12 = (E12, V ′, V ′′, V ′′′) is ▽V ′V ′′V ′′′ -free but neither KV ′V ′′′ -dense, because the intersection of the maximal V ′-clique {e1, e4} of Ee′ with the maximal V ′′′-clique {e2, e3} of Ee′ is empty, nor KVe ′Ve ′′′ -dense, because the intersection of maximal Ve ′clique {e1, e4, e5} of Ee′′ and maximal Ve ′′′-clique {e2, e3, e5} of Ee′′ is not a maximal V ′′-clique of Ee′′, where Ee′ = {e1, e2, e3, e4} is the maximal (V ′ ∪ V ′′′)-clique of E12, E′ = {e1, e2, e3, e4, e5} is the maximal (Ve ′ ∪ Ve ′′′)-clique of E12, Ve ′ = V ′ ∪ V ′′, e and Ve ′′′ = V ′′ ∪ V ′′′. We can see that S13 = (E13, V ′, V ′′, V ′′′) is KVe ′Ve ′′ -dense but neither V ′- nor V ′′- nor V ′′′-finite, where Ve ′ = V ′ ∪ V ′′′ and Ve ′′ = V ′′ ∪ V ′′′. Clearly, the maximal V ′V ′′-clique {b1, b2, b3, . . . , c1, c2, c3, . . .} of E13 is not KV ′V ′′ -dense. Hence, S13 is not KV ′V ′′ -dense. 5
In the papers [
• Ee is P Q-encountering iff for any maximal P -clique E′ of Ee and for any maximal Q-clique E′′ of Ee, E′ ∩ EQ′′′Q 6= ∅, for some finite E′′′ ⊆ E′′, • Ee is weak KP Q-dense iff for any maximal P -clique E′ of Ee and for any maximal
any Q-closed set A of Ee, • Ee is P Q-algebraic iff (QCl(Ee), ⊆) is an algebraic lattice, • S is P Q-encountering (weak KP Q-dense, P Q-algebraic, respectively) iff any maximal (P ∪Q)-clique Ee of E is P Q-encountering (weak KP Q-dense, P Q-algebraic, respectively).
Fig. 5.
The following fact will be helpful to obtain weak KP Q-density as a necessary condition of P Q-algebraicity.
Theorem 3. Given a ⊲⊳P Q-dense relational structure S with a transitive relation P and a symmetric relation Q,
Example 6. Consider the relational structures S14 = (E14, V ′, V ′′) and S15 = (E15, V ′, V ′′) with the transitive relation V ′ and the symmetric relation V ′′, shown in Fig. 5. One can easily check that S14 is V ′V ′′-encountering, ⊲⊳V ′V ′′ - and KV ′V ′′ dense. On the other hand, S15 is V ′V ′′-encountering and, obviously, not ⊲⊳V ′V ′′ -dense. Moreover, as the maximal V ′-clique {e1, e4} and the maximal V ′′-clique {e2, e3} of E15 are disjoint, S14 is not KV ′V ′′ -dense. We know from Example 3 that the relational structure S7 depicted in Fig. 3 is ⊲⊳V ′V ′′ -dense but not KV ′V ′′ -dense. Furthermore, S7 is not V ′V ′′-encountering, because for the maximal V ′-clique E′ = {e1, e3, e5, . . .} and the maximal V ′′-clique E′′ = {e2, e3, e6, . . .} of E7, we have E′ ∩ E′′′ V ′′V ′′ = E′ ∩ E′′′ = ∅ for any finite E′′′ ⊆ E′′.
Finally, the following theorem describes interconnections between the properties of KP Q-density and weak KP Q-density, and P Q-algebraicity of a relational structure.
tional structure S with a transitive relation P and a symmetric relation Q, (i) S is KP Q-dense =⇒ S is P Q-algebraic, (ii) S is weak KP Q-dense ⇐= S is P Q-algebraic.
Example 7. Contemplate the V ′-degree-restricted relational structures S16–S18, with the transitive relation V ′ and the symmetric relation V ′′, depicted in Fig. 6. The relational structure S16 = (E16, V ′, V ′′) is, obviously, V ′-degree-finite, V ′-intervalfinite and KV ′V ′′ -dense. Since it is finite, it is V ′V ′′-algebraic. Next, consider the V ′-degree-finite relational structure S17 = (E17, V ′, V ′′) with the maximal V ′-clique E′ = {e2·i+1 | i ≥ 0} of E17 and the maximal V ′′-clique E′′ = {e2·j | j ≥ 1 ∧ j 6= 2} of E17. Since E′ ∩ E′′ = ∅, S17 is not KV ′V ′′ -dense. Moreover, S17 is not weak KV ′V ′′ -dense, because A = {e3} is a V ′′-closed set of E17 such that A ⊆ E′. Furthermore, A is not compact in the lattice (V ′′Cl(E17), ⊆). This implies that ∅ is the only compact element less than A. As W ∅ = ∅ 6= A, S17 is not V ′V ′′-algebraic. Finally, consider the non-V ′-degree-finite relational structure S18. One can easily check that S18 is KV ′V ′′ -dense and V ′-interval-finite. As the V ′′-closed set A = {e1} is not compact in the lattice (V ′′Cl(E18), ⊆), S18 is not V ′V ′′-algebraic.