Using Category Theory to Explore and Model Label Event Structures ()
1. Introduction
A concurrent system that consists of several simultaneously executing components allows carrying out multiple tasks at the same time, which can accelerate the computational work of software substantially. To model concurrent system, Labeled Event Structures (LES) were proposed and evolved in research [1] [2] . However, a concurrent system usually involves many concurrently interactive components; the exhibition of a large number of different behaviors typically occurs, which may introduce difficulties to the development of concurrent systems [3] . In particular, the notable difficulties include the state-space explosion, unpredictable composition, and others [4] . To tackle this kind of challenge, the formal method is considered to be a way, which can provide systems with known safety properties [5] . Usually, a formal specification can be used to check for particular types of errors and as inputs for model checking. Category theory is a formal method, which has been used to model and verify concurrent systems. Category theory has been proposed as a framework to offer specification structure. It has a rich body of theory to reason objects and their relations. Moreover, category theory adopts a correct-by-construction approach by which components can be specified, proved and composed in the way of preserving their properties.
Researches [6] [7] used category theory to model concurrent systems. As a continuation, we propose to use category theory to explore and model LES for concurrent systems in this paper. Specifically, we propose an approach to construct categorical object, morphism, product, and sum for LES. To explain our work, a vending machine example is designed by LES, and modeled by category theory. The rest of this paper is organized as follows. Section 2 introduces related work to this paper. Section 3 introduces background knowledge required to understand the remaining content of the paper. Section 4 provides a vending machine example modeled by LES, which is used for the explanation of the proposed categorical modeling. Section 5 shows how to construct categorical structures from LES. Section 6 illustrates how to use the proposed categorical approach to model the vending machine example. Section 7 concludes this paper.
2. Related Work
2.1. Labeled Event Structure
LES is a mathematical model with true concurrency that describes a process in terms of relations between sets of events it generates. Loogen and Goltz used LES to analyze and model nondeterministic concurrent processes [8] . de León, Haar and Longuet proposed a theoretical framework based on LES for testing and verifying observable behaviors of concurrent systems from true concurrency models like Petri nets or networks of automata [9] . Castellan, Clairambault, Rideau and Winskel introduced a detailed, self-contained update to concurrent games on event structures which were preserved by composition with a copycat strategy, and the construction of a bicategory of these strategies [10] . Bruni, Melgratti and Montanari proposed a definition of a particular class of graph grammars that are expressive enough to model name passing calculi while simplifying the denotational domain construction, and applied this technique to derive event structure semantic [11] .
2.2. Category Theory
For modeling concurrency, category theory is used to model, analyze, and compare Transition System, Trace Language, Event Structure, Petri nets, and other classical models of concurrency [12] [13] [14] . Sisiaridis, Kuchta and Markowitch proposed a framework for implementing Godement calculus and cartesian closed comma categories for information security management in the detection of threats and attacks in communication systems [15] . Paper [16] introduces a formal language model which formalized agent-environment interaction in a multi-agent framework called Conversational Grammar Systems (CGS). This system provided a model with a high degree of flexibility. Based on eco-grammar systems, the formal model used in this paper can be defined as an evolutionary multi-agent system. Category theory is applied to study relationships between geometrical models for concurrency and classical models [17] . Abdel Gawad outlined and summarized four new potential applications of category theory to OOP research are presented the use of operads to model Java sub-typing [18] .
3. Background
In this section, background and work related to our research are introduced.
3.1. Labeled Event Structure
An event structure expresses how these events are related to each other. In general event structures that are widely used, a concurrent system or a process can be represented as tuples
.
Definition 1. An event structure is a tuple
consisting of
・ a set of events E,
・ the consistency predicate
, the set of conflict-free finite subsets of E, and
・ the enabling relation
which satisfies the following properties:
・ consistency of Con:
and
・
.
.
, that is, if X enables e so does any conflict-free superset Y of X.
Example 1. There is a transition system with states
, where S0 is the initial state, and transitions
. The graphical representation of the transition system is show in Figure 1.
This transition system can be represented by LES as follows:
3.2. Category Theory
Category theory focuses on the relationships (morphisms) between objects instead of their representations; the morphisms can determine the nature of interactions established between the objects.
Definition 2. A category consists of the following data:
・ Objects: A, B, C, etc.
・ Arrows (Morphisms): f, g, h, etc.
・ For each arrow f, there are given objects: dom(f), cod(f) called domain as well as codomain of f, and f: A → B indicates that A = dom(f), B = cod(f).
・ Given arrows f: A → B and g: B → C with cod(f) = dom(g), there is an given arrow:
called composite of f and g.
・ For each object A, there is an given arrow: 1A: A → A called identity arrow of A.
These data need to satisfy the following laws:
・ Associativity:
for all f: A → B, g: B → C, h: C → D.
・ Unit:
for all f: A → B.
Example 2. Let (S; ≤) be a partially-ordered set (poset). Define the category C in which: each member x of S is an object of C; and each relation x ≤ y of (S; ≤) is a morphism x → y of C.
We can verify that C is a category as follows:
・ For every object x, there is an identity morphism x → x, corresponding to reflexivity, x ≤ x, in the poset.
・ The morphisms (x → y) and (y → z) form a composition pair:
; corresponding to transitivity, x ≤ y, y ≤ z, and x ≤ z, in the poset.
・ Composition is associative:
and
,
because of
Definition 3. Let A and B be objects in a category Cat. Then a product of A and B consists of:
・ an object, A × B,
・ morphisms, often called projections,
and
, and
・ the property that, for any object C and morphisms
,
, there is a unique morphism
such that Figure 2 commutes. That is
and
.
Definition 4. Let A and B be objects in a category Cat. Then a sum (or coproduct) of A and B consists of:
・ an object, A + B,
・ morphisms, often called inclusions or canonical projections,
and
, and
・ the property that, for any object C and morphisms
and
, there is a unique morphism
such that Figure 3 commutes. That is
and
.
4. An Overview of a Vending Machine Example
In this paper, we use a vending machine example to illustrate how to construct categories and the corresponding structures for models specified by LES which is defined and specified in section 3.
Example 3. There is a vending machine and a person. The vending machine can offer coke and pepsi. Each time, the vending machine accepts a coin first, then dispenses a bottle of coke or pepsi according to the person’s choice.
In this example, the vending machine and the person are modeled as two processes. When the person inserts a coin and vending machine accepts the coin, this interaction can be represented by the shared event coin in person and vending machine. When person chooses coke or pepsi and vending machine accepts it, this interaction can be represented by the shared event coke or pepsi in person and vending machine. After that, the communications between person and vending machine terminate.
By using LES, the communications between person and vending machine in the example can be modeled as follows:
5. Construct Categorical Structures for LES Models
In this section, we use category theory to construct structures for LES models. We first define categorical object and morphism for constructing categories for LES models, then we construct product and sum based on the categories, and we use the vending machine example in Section 3 to explain the categorical structures.
5.1. Object
An object is like an event structure, but simpler. Formally, an object (E, R) consists of a set of events, E, and an ordering relation
. If events e1 and e2 are related by R (that is,
),
that indicates “e1 precedes e2” or “e1 happens before e2”.
The relation R is a partial order: reflexive, antisymmetric, and transitive. If
, it is not possible to have both
and
, but it is possible that neither is true.
An object can be represented by a forest diagram such as Figure 4. For example:
For this object,
,
R is reflexive, transitive. In Figure 3, we omit reflexive and transitive arrows. Note that some pairs of events, e.g., a and c, are unrelated: this means simply that there are no constraints on their order of occurrence.
5.2. Morphism
Let
and
be objects. There is a morphism
if and only if
and
. In words:
・ Every event e that belongs to E1 also belongs to E2.
・ Every ordered pair
in O1 also belongs to O2.
There is an identity morphism for every object (E, R) because
and
. Similarly, compositions of morphism exist by transitivity of
. Consequently, the objects and morphisms combined forma category CP.
If there is a morphism
, which indicates O1 is contained by O2 or simply O2 contains O1. This terminology is consistent with a set “containing” its subsets.
Figure 4. Graphical representation of object.
Also, if there is a morphism
, then it must be unique, because there is only one way that a set can be a subset of another set.
There exist some special cases:
・ Traces are objects: the trace
,
can be represented as object a → b→ c.
・ If trace t1 is a prefix of trace t2, there is a morphism
.
・ Event trees are objects: the object shown above in Figure 3 has a tree with c as root.
・ There is a morphism from any path in a tree to the tree itself.
5.3. Sum (Coproduct)
If S and T are objects, we define their sum(coproduct) S + T to be the smallest object that contains both S and T. The sum can be defined by set union as follows:
Definition 5. Let
and
, then
・ By definition, S + T contains S. Consequently, there is a morphism
. Similarly, there is a morphism
.
・ Let X be another object and suppose there is a morphism
, then X contains S. Similarly, if there is a morphism
, then X contains T. Thus X contains both S and T. Since S + T is the smallest object containing both S and T, it follows that X must contain S + T and therefore there is a morphism
. The morphism h is unique.
To illustrate the sum S + T, Figure 5 describes the sum and it commutes.
We can use sum to build branching structures, which can be explained by using Example 4 as follows:
Example 4. Given (E1, R1) and (E2, R2), where
・
,
.
・
,
.
Then, there is a sum
which can be represented by Figure 6.
In general, when S + T is formed, we assume that the event structures S and T belong to the same process. If e occurs in both structures, it refers to the same event.
Figure 6. The sum
.
5.4. Product
The purpose of the product is to combine concurrent processes, each defined by an object, i.e., event structure. To do this, two kinds of event must be distinguished:
Let
and
be objects corresponding to concurrent processes and let
. Then:
・ If
, it indicates that e is a communication event and e must occur simultaneously in both processes.
・ Otherwise,
, and e belongs to process P only. In this case, e is an independent event.
Product of P1 and P2 can be constructed as follows:
・ Let
be the set of events that communicate, namely the communication set. The communication set is as large as possible, which means that the only events that cannot be added to it are not communication events.
・ The ordering relation R × is the union
restricted to elements of E ×. Formally,
So, the definition of product is provided as follows:
Definition 6. Let
and
, then
・ By construction, S × T contains only events that occur in S and T and is therefore contained in both of them. Thus the projections
and
are well-defined.
・ Assuming that there is an object X and morphisms
and
. Then X must be contained in both S and T. Therefore it must also be contained in S × T which is the largest object contained in both S and T. Hence the morphism
exists and is unique.
To illustrate the sum S × T, Figure 7 describes the product and it commutes.
We can use product to build largest communication structures, which can be explained by using Example 5 as follows:
Example 5. Let
and
defined as in Figure 8, in which the c’s are communicating events and the e’s are independent events:
Then the product P × Q has the events
and the ordering is just
. The processes execute as shown, with time increasing from left to right, synchronizing at c1 and c2. The execution independent events, such as e3, are ignored, as they don’t affect the communications. So, independent events are abstracted out of the system.
6. Use Categorical Structures to Model the Vending Machine
In Section 4, this paper provided a vending machine in Example 3 which is modeled by LES. In this section, we use categorical structures defined in Section 5 to model the vending machine example.
The objects of the vending machine are listed as follows:
,
,
The morphisms between objects are listed as follows, where identities and composites are ignored:
The diagram of the category of the vending machine is illustrated in Figure 9.
In Figure 9, there exist some products and sums, where a product represents the largest communication structure of two objects and a sum represents the branching structure of two objects.
Figure 9. Category of the vending machine.
・ Products of the category of the vending machine are listed as follows:
The above-mentioned products are just some in the category, while there are other products that are not listed specifically in above.
・ Sums of the category of the vending machine are listed as follows:
The above-mentioned sums are just some in the category, while there are other sums that are not listed specifically in above.
7. Conclusion
In view of the difficulties in the development of concurrent systems, the present work proposes a new approach to model LES based on the category theory, which helps to explore the communication events and relationship among them. Specifically, categorical object, morphism, product, and sum are constructed for events and relationships. To explain the work, a vending machine example is designed by LES, and the communications between vending machines and persons are modeled by category theory. By adopting the categorical approach, we can explore and model concurrent systems designed by LES with categorical structures, which can be specified, proved and composed formally with preserving their properties. In Future, we will explore the usage of more categorical structures, such as limit/colimit and natural transformation in LES which may be useful for the formalization and verification of communications.
Acknowledgements
We thank the editor and the referee for their comments. Research of M. Zhu and J. Li is funded by the Shandong University of Technology grants 4041-416069 and 4041-417010. The support is greatly appreciated.