Abstract
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 in Gaifman and Pratt (Proceedings of LICS’87, pp 72–85, 1987), Lamport (J ACM 33:313–326, 1986), Abraham et al. (Semantics for concurrency, workshops in computing. Springer, Heidelberg, pp 311–323, 1990) and Janicki and Koutny (Lect Notes Comput Sci 506:59–74, 1991), substantially developed in Janicki and Koutny (Theoretical Computer Science 112:5–52, 1993) and Janicki and Koutny (Acta Informatica 34:367–388, 1997), and recently generalized in Guo and Janicki (Lect Notes Comput Sci 2422:178–191, 2002) and Janicki (Lect Notes Comput Sci 3407:84–98, 2005). For the first time the full model for the most general case is given.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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)
Anger, F.D.: On Lamport’s interprocess communication model. ACM TOPLAS 11(3), 404–417 (1989)
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)
Begstra J.A., et al. (eds.): The Handbook of Process Algebras. Elsevier, Amsterdam (2000)
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)
Best, E., Devillers, R., Koutny, M.: Petri Net Algebra. Springer, Heidelberg (2001)
Best, E., Koutny, M.: Petri net semantics of priority systems. Theor. Comput. Sci. 94, 141–158 (1992)
Best, E., Koutny, M.: Operational and denotational semantics for the box algebras. Theor. Comput. Sci. 211, 1–83 (1999)
Brookes, S.D., Hoare, C.A.R., Roscoe, A.W.: A theory of communicating systems. J. ACM 31, 560–599 (1984)
Degano, P., Montanari, U.: Concurrent histories; a basis for observing distributed systems. J. Comput. Syst. Sci. 34, 422–467 (1987)
Diekert, V., Rozenberg, G. (eds.) The Book of Traces. World Scientific, Singapore (1995)
Gaifman, H., Pratt, V.: Partial order models of concurrency and the computation of functions. In: Proceedings of LICS’87, pp. 72–85
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)
Fishburn, P.C.: Intransitive indifference with unequal indifference intervals. J. Math. Psych. 7, 144–149 (1970)
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)
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)
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)
Janicki, R., Koutny, M.: Structure of concurrency. Theor. Comput. Sci. 112, 5–52 (1993)
Janicki, R., Koutny, M.: Semantics of inhibitor nets. Inf. Comput. 123(1), 1–16 (1995)
Janicki, R., Koutny, M.: Fundamentals of modelling concurrency using discrete relational structures. Acta Informatica 34, 367–388 (1997)
Janicki, R., Koutny, M.: On causality semantics of nets with priorities. Fundam. Inf. 38, 222–255 (1999)
Janicki, R., Lauer, P.E.: Specification and Analysis of Concurrent Systems: The COSY Approach. Springer, Heidelberg (1992)
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)
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)
Katz, S., Peled, D.: Defining conditional independence using collapses. In: Semantics for Concurrency, Workshops in Computing, pp. 262–290. Springer, Heidelberg (1990)
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)
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)
Kleijn, H.C.M., Koutny, M.: Process semantics of general inhibitor nets. Inf. Comput. 190, 18–69 (2004)
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)
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)
Mazurkiewicz, A.: Trace theory. In: Lecture Notes in Computer Science, vol. 225, pp. 297-324. Springer, Heidelberg (1986)
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)
Pietkiewicz-Koutny, M.: The synthesis problem for elementary net systems. Fundam. Inf. 40(2,3), 310–327 (1999)
Pinna, G.M.: Event structures with disabling/enabling relation and event automata. Funadam. Inf. 73(3), 409–430 (2006)
Reisig, W.: Elements of Distributed Algorithms. Springer, Heidelberg (1998)
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)
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)
Szpilrajn, E.: Sur l’extension de l’ordre partial. Fundam. Math. 16, 386–389 (1930)
Vogler, W.: Timed testing of concurrent systems. Inf. Comput. 121, 149–171 (1995)
Vogler, W.: Partial order semantics and inhibitor arcs. In: Lecture Notes in Computer Science, vol. 1295, pp. 508–517. Springer, Heidelberg (1997)
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)
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)
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by NSERC of Canada Grant.
Rights and permissions
About this article
Cite this article
Janicki, R. Relational structures model of concurrency. Acta Informatica 45, 279–320 (2008). https://doi.org/10.1007/s00236-008-0071-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00236-008-0071-6