# zbMATH — the first resource for mathematics

Relational structures model of concurrency. (English) Zbl 1147.68054
Summary: The paper deals with the foundations of concurrency theory. We show how structurally complex concurrent behaviours can be modelled by relational structures $${(X, \diamondsuit, \sqsubset)}$$, where $$X$$ is a set (of event occurrences), and $${\diamondsuit}$$ (interpreted as commutativity) and $${\sqsubset}$$ (interpreted as weak causality) are binary relations on $$X$$. The paper is a continuation of the approach initiated by H. Gaifman and V. Pratt [“Partial order models of concurrency and the computation of functions”, in: Proceedings of LICS’87, 72–85 (1987)], L. Lamport [J. Assoc. Comput. Mach. 33, 313–326 (1986; Zbl 0627.68017)], U. Abraham, S. Ben-David and M. Magodor [“On global-time and inter-process communication”, in: Semantics for concurrency, Workshops in Computing. Springer, Heidelberg, 311–323 (1990)] and R. Janicki and M. Koutny [“Invariants and paradigms of concurrency theory”, Lect. Notes Comput. Sci. 506, 59–74 (1991)], substantially developed in [R. Janicki and M. Koutny, Theor. Comput. Sci. 112, 5–52 (1993; Zbl 0814.68061)] and [R. Janicki and M. Koutny, Acta Inf. 34, 367–388 (1997; Zbl 0934.68047)], and recently generalized by G. Guo and R. Janicki [“Modelling concurrent behaviours by commutativity and weak causality relations”, Lect. Notes Comput. Sci. 2422, 178–191 (2002)] and R. Janicki [Lect. Notes Comput. Sci. 3407, 84–98 (2005; Zbl 1109.68073)]. For the first time the full model for the most general case is given.

##### MSC:
 68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text:
##### References:
 [1] Abraham, U., Ben-David, S., Magodor, M.: On global-time and inter-process communication. In: Semantics for Concurrency, Workshops in Computing, pp. 311–323. Springer, Heidelberg (1990) [2] Anger, F.D.: On Lamport’s interprocess communication model. ACM TOPLAS 11(3), 404–417 (1989) · doi:10.1145/65979.65982 [3] Baldan, P., Busi, N., Corradini, A., Pinna, M.: Domain and event structure semantics for petri nets with read and inhibitor arcs. Theor. Comput. Sci. 323, 129–189 (2004) · Zbl 1078.68103 · doi:10.1016/j.tcs.2004.04.001 [4] Begstra J.A., et al. (eds.): The Handbook of Process Algebras. Elsevier, Amsterdam (2000) [5] Best, E., de Boer, F., Palamedissi, C.: Partial order and SOS semantics for linear constraint programs. In: Lecture Notes in Computer Science, vol. 1282, pp. 256–273. Springer, Heidelberg (1997) [6] Best, E., Devillers, R., Koutny, M.: Petri Net Algebra. Springer, Heidelberg (2001) [7] Best, E., Koutny, M.: Petri net semantics of priority systems. Theor. Comput. Sci. 94, 141–158 (1992) · Zbl 0753.68059 [8] Best, E., Koutny, M.: Operational and denotational semantics for the box algebras. Theor. Comput. Sci. 211, 1–83 (1999) · Zbl 0912.68126 · doi:10.1016/S0304-3975(97)00180-1 [9] Brookes, S.D., Hoare, C.A.R., Roscoe, A.W.: A theory of communicating systems. J. ACM 31, 560–599 (1984) · Zbl 0628.68025 · doi:10.1145/828.833 [10] Degano, P., Montanari, U.: Concurrent histories; a basis for observing distributed systems. J. Comput. Syst. Sci. 34, 422–467 (1987) · Zbl 0619.68017 · doi:10.1016/0022-0000(87)90032-8 [11] Diekert, V., Rozenberg, G. (eds.) The Book of Traces. World Scientific, Singapore (1995) [12] Gaifman, H., Pratt, V.: Partial order models of concurrency and the computation of functions. In: Proceedings of LICS’87, pp. 72–85 [13] Guo, G., Janicki, R.: Modelling Concurrent Behaviours by Commutativity and Weak Causality Relations. In: Proceedings of AMAST’02. Lecture Notes in Computer Science, vol. 2422, pp. 178–191 (2002) · Zbl 1275.68105 [14] Fishburn, P.C.: Intransitive indifference with unequal indifference intervals. J. Math. Psych. 7, 144–149 (1970) · Zbl 0191.31501 · doi:10.1016/0022-2496(70)90062-3 [15] Janicki, R.: A generalisation of a relational structures model of concurrency. In: Proceedings of ICTAC’04. Lecture Notes in Computer Science, vol. 3407, pp. 84–98 (2005) · Zbl 1109.68073 [16] Janicki, R., Koutny, M.: Invariants and paradigms of concurrency theory. In: Proceedings of PARLE’91. Lecture Notes in Computer Science, vol. 506, pp. 59–74 (1991) [17] Janicki, R., Koutny, M.: Order structures and generalisation of Szpilrajn’s theorem. In: Proceedings of FSTTCS’93. Lecture Notes in Computer Science, vol. 761, pp. 348–357 (1993) · Zbl 0924.06005 [18] Janicki, R., Koutny, M.: Structure of concurrency. Theor. Comput. Sci. 112, 5–52 (1993) · Zbl 0814.68061 · doi:10.1016/0304-3975(93)90238-O [19] Janicki, R., Koutny, M.: Semantics of inhibitor nets. Inf. Comput. 123(1), 1–16 (1995) · Zbl 1096.68678 · doi:10.1006/inco.1995.1153 [20] Janicki, R., Koutny, M.: Fundamentals of modelling concurrency using discrete relational structures. Acta Informatica 34, 367–388 (1997) · Zbl 0934.68047 · doi:10.1007/s002360050090 [21] Janicki, R., Koutny, M.: On causality semantics of nets with priorities. Fundam. Inf. 38, 222–255 (1999) · Zbl 1058.68540 [22] Janicki, R., Lauer, P.E.: Specification and Analysis of Concurrent Systems: The COSY Approach. Springer, Heidelberg (1992) · Zbl 0765.68007 [23] Juhás, G., Lorenz, R., Mauser, S.: Synchronous + Concurrent = Earlier Than + Not Later Than. In: Proceedings of ACSD’06 (Application of Concurrency To System Design), pp. 261–272. IEEE Press, New York (2006) [24] Juhás, G., Lorenz, R., Neumair, C.: Synthesis of controlled behaviour with modules of signal nets. In: Proceedings of ATPN’04. Lecture Notes in Computer Science, vol. 3099, pp. 233–257. Springer, Heidelberg (2004) · Zbl 1094.68585 [25] Katz, S., Peled, D.: Defining conditional independence using collapses. In: Semantics for Concurrency, Workshops in Computing, pp. 262–290. Springer, Heidelberg (1990) · Zbl 0769.68082 [26] Klaudel, H., Pommereau, F.: A class of composable and preemptible high-level petri nets witn and application to a multi-tasking system. Fundam. Inf. 50, 33–55 (2002) · Zbl 1003.68094 [27] Kleijn, H.C.M., Koutny, M.: Process semantics of P/T-nets with inhibitor arcs. In: Lecture Notes in Computer Science, vol. 1825, pp. 261–281. Springer, Heidelberg (2000) · Zbl 0986.68088 [28] Kleijn, H.C.M., Koutny, M.: Process semantics of general inhibitor nets. Inf. Comput. 190, 18–69 (2004) · Zbl 1101.68699 · doi:10.1016/j.ic.2003.11.002 [29] Lamport, L.: The mutual exclusion problem: Part I–A theory of interprocess communication; Part II–Statements and solutions. J. ACM 33(2), 313–326 (1986) · Zbl 0627.68017 · doi:10.1145/5383.5384 [30] Lamport, L.: What it means for a concurrent programm to satisfy a specification: why no one has specified priority. In: Proceedings of the 12th ACM Symposium on Programming Languages, pp. 78–83 (1985) [31] Mazurkiewicz, A.: Trace theory. In: Lecture Notes in Computer Science, vol. 225, pp. 297-324. Springer, Heidelberg (1986) [32] Milner, R.: Operational and algebraic semantics of concurrent processes. In: van Leuween, J. (ed.) Handbook of Theoretical Computer Science, vol. 2, pp. 1201-1242. Elsevier, Amsterdam (1993) · Zbl 0900.68217 [33] Pietkiewicz-Koutny, M.: The synthesis problem for elementary net systems. Fundam. Inf. 40(2,3), 310–327 (1999) · Zbl 0942.68083 [34] Pinna, G.M.: Event structures with disabling/enabling relation and event automata. Funadam. Inf. 73(3), 409–430 (2006) · Zbl 1110.68088 [35] Reisig, W.: Elements of Distributed Algorithms. Springer, Heidelberg (1998) · Zbl 0907.68130 [36] Roux, O.H., Lime, D.: Time petri nets with inhibitor arcs. Formal semantics and state space complexity. In: Proceedings of ATPN’04. Lecture Notes in Computer Science, vol. 3099, pp. 370–390. Springer, Heidelberg (2004) · Zbl 1094.68594 [37] Shields, M.W.: On the non-sequential behaviours of systems possessing a general free-choice-property, CSR-92-81. Department of Computer Science, University of Edinburgh (1981) [38] Szpilrajn, E.: Sur l’extension de l’ordre partial. Fundam. Math. 16, 386–389 (1930) · JFM 56.0843.02 [39] Vogler, W.: Timed testing of concurrent systems. Inf. Comput. 121, 149–171 (1995) · Zbl 0833.68048 · doi:10.1006/inco.1995.1130 [40] Vogler, W.: Partial order semantics and inhibitor arcs. In: Lecture Notes in Computer Science, vol. 1295, pp. 508–517. Springer, Heidelberg (1997) · Zbl 0941.68091 [41] Wollowski, R., Beister, J.: Precise petri net modelling of critical races in asynchronous arbiters and synchronizers. In: Proceedings of 1st Workshop on Hardware Design and Petri Nets, Lisbon, pp. 46-65 (1998) [42] Wollowski, R., Beister, J.: Comprehensive causal specification of asynchronous controller and arbiter behaviour. In: Yakovlev, A., Gomes, L., Lavagno, L. (eds.) Hardware Design and Petri Nets. Kluwer, Dordrecht (2000) · Zbl 0986.68786
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.