Polynomial Algebraic Event Structures And Their Approximation And Approximate Equivalences

In recent years, concurrent systems have been widely used in many fields. Event structures are commonly recognized as models of concurrent systems. The interest of event structures is increasing, and a large number of scholars have devoted themselves to this field.Since the actions of event structures are abstract, no detailed description of system behavior can be offered and could not use approximation technique. When interacting with the physical world, accurate measurement is impossible and truncation error is in-evitable. So the error can not be ignored. Meanwhile, the better accuracy of the solution does not mean better. Time and space complexity should be taken into account. Thus exact solution is not possible and is not necessary. On the one hand, within the given er-ror, we can use approximation technique to give a simplified system. On the other hand, the error between the original system and the simplified system measure the similarity between the two systems. That is to say, exact equivalences are restrictive and not robust, compared with approximate equivalences.Another problem is the reduction of event structures. Various semantic equivalences in the linear time-branching time spectrum are used to simplify labelled transition sys-tems. But the theory of using semantic equivalences to simplify event structures is not complete.In order to solve those problems, this paper proposes a generalized event structure, polynomial algebraic event structure, by refining the abstract events into polynomial al-gebra.The contributions are as follows.1) This paper gives the definition of polynomial algebraic event structures. And the traditional event structure can be regarded as a special case of polynomial algebraic event structure.2) This paper shows that flow event structures are more suitable for modeling pro-grams (low-level codes), than other event structures (prime event structures, stable event structures, bundle event structures and extended bundle event structures).3) Interleaving and step semantics are discussed in this paper. With the help of configurations, we introduce interleaving transition systems and step transition systems, so as to use linear time-branching time equivalences on event structures.4) In the study of linear time-branching time equivalences, reachability, trace, fail-ures, singleton failures and bisimulation are discussed. Based on previous researches, the set of all traces and singleton failures (SF) pairs is used to characterize SF equiva-lence. This paper proposes a revised version of singleton failures (RSF) pair, and show that the set of all RSF pairs alone can characterize SF equivalence, in other words, RSF equivalence and SF equivalence are equivalent. It is proved that RSF equivalence algo-rithm is the most efficient one among all SF equivalence algorithms. Additionally, two examples are presented to show that the workload is reduced compared to traditional SF equivalence algorithm.5) To alleviate the computational complexity and minimize event structures, events structures can be simplified by numerous numerical approximation methods, including taylor expansion, the best first order approximation and piecewise linear interpolation Alternatively, event structure can be endowed with Baire metric. By using Hausdorff distance, trace distance and bisimulation distance are defined, which quantify the approx-imate relationship between event structures.6) Using weak Baire metric and HausdorfF distance, this paper proposes a general-ized framework of event structures approximation by developing the notions of approxi-mate interleaving (reachability, trace, failures, singleton failures and bisimulation) equiv-alence and approximate step (reachability, trace, failures, singleton failures and bisimula-tion) equivalence. The framework captures the traditional exact equivalence as a special case. Approximate language equivalence is coarser than approximate singleton failures equivalence, and approximate reachability equivalence is coarser than approximate bisim-ulation equivalence, just like the hierarchy of the exact ones. The main conclusion is that these approximate equivalences satisfy the transitive property, consequently, they can be successively used in the process of event structures approximation.In conclusion, polynomial algebraic event structures offer a more satisfactory de-scription of events. At the same time, we can make full use of approximations of numeri-cal computation and Baire metric tool to minimize polynomial algebraic event structures. Polynomial algebraic event structures and their approximation and approximate equiva-lences are powerful support to develop concurrent systems.