Logic and Algebra in Unfolded Petri Nets : on a Duality Between Concurrency and Causal Dependence

• Autorzy: Bernardinello Luca , Ferigato Carlo , Pomello Lucia

Identyfikatory

DOI

10.3233/FI-2020-1871

• Języki publikacji: EN

Abstrakty

EN

An orthogonality space is a set endowed with a symmetric and irreflexive binary relation (an orthogonality relation). In a partially ordered set modelling a concurrent process, two such binary relations can be defined: a causal dependence relation and a concurrency relation, and two distinct orthogonality spaces are consequently obtained. When the condition of N-density holds on both these orthogonality spaces, we study the orthomodular poset formed by closed sets defined according to Dacey. We show that the condition originally imposed by Dacey on the orthogonality spaces for obtaining an orthomodular poset from his closed sets is in fact equivalent to N-density. The requirement of N-density was as well fundamental in a previous work on orthogonality spaces with the concurrency relation. Starting from a partially ordered set modelling a concurrent process, we obtain dual results for orthogonality spaces with the causal dependence relation in respect to orthogonality spaces with the concurrency relation.

Słowa kluczowe

EN

mathematical logic; Petri nets; partially ordered sets; orthogonalization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 39--56
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Bernardinello Luca

• DISCo, Università degli studi di Milano - Bicocca, Milano, Italy

autor

Ferigato Carlo

• European Commission, Joint Research Centre (JRC), Ispra (VA), Italy

autor

Pomello Lucia

• DISCo, Università degli studi di Milano - Bicocca, Milano, Italy

Bibliografia

• [1] Lodaya K, Mukund M, Ramanujam R, Thiagarajan PS. Models and logics for true concurrency. Sādhanā, 1992. 17(1):131-165. doi:10.1007/BF02811341.
• [2] Mauri G, Brambilla M. On the Logic of Concurrency and Conflict. Informatik-Fachberichte, 1982. 52:258-268. doi:10.1007/978-3-642-68353-4_43.
• [3] Józef Winkowski. An algebraic approach to concurrency. Lecture Notes in Computer Science, 1979.
• [4] Petri CA. Non-Sequential Processes. Technical Report ISF-77-5, GMD Bonn, 1977. Translation of a lecture given at the IMMD Jubilee Colloquium on ‘Parallelism in Computer Science’, Universität Erlangen-Nürnberg. June 1976.
• [5] Best E, César Fernández. Nonsequential Processes. Springer-Verlag, 1988. ISBN-0387190309, 9780387190303.
• [6] Bernardinello L, Pomello L, Rombolà S. Closure Operators and Lattices Derived from Concurrency in Posets and Occurrence Nets. Fundamenta Informaticae, 2010. 105(3). doi:10.3233/FI-2010-365.
• [7] Pták P, Pullmanová S. Orthomodular Structures as Quantum Logics. Kluwer Academic Publishers, 1991. ISBN-0-7923-1207-4, 80-224-0242-7.
• [8] Bernardinello L, Ferigato C, Pomello L. Between Quantum Logic and Concurrency. Proceedings of the 9th International Workshop on Quantum Physics and Logic, 2012. arXiv:1407.8427.
• [9] Dacey JC. Orthomodular spaces and additive measurement. Caribbean Journal of Science and Mathematics, 1969. 1(51).
• [10] Goltz U, Reisig W. The non-sequential behaviour of Petri nets. Information and Control, 1983. 57(2):125-147. doi:10.1016/S0019-9958(83)80040-0. URL http://www.sciencedirect.com/science/article/pii/S0019995883800400.
• [11] Janicki R. Nets, sequential components and concurrency relations. Theoretical Computer Science, 1984. 29(1):87-121. doi:10.1016/0304-3975(84)90014-8.
• [12] Foulis DJ, Randall CH. Operational Statistics I. Basic Concepts. Journal of Mathematical Physics, 1972. 13(13). URL https://doi.org/10.1063/1.1665890.
• [13] Goldblatt R. Orthogonality and Spacetime Geometry. Springer-Verlag, 1987. doi:10.1007/978-1-4684-6345-3. ISBN-978-0-387-96519-2.
• [14] Birkhoff G. Lattice Theory. American Mathematical Society; 3rd Ed., 1979. ISBN-978-0-8218-1025-5.
• [15] Puerto A. Concurrency-Preserving Minimal Process Representation. In: Höfner P, Pous D, Struth G (eds.), Relational and Algebraic Methods in Computer Science - 16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings, volume 10226 of Lecture Notes in Computer Science. ISBN 978-3-319-57417-2, 2017 pp. 242-257. doi:10.1007/978-3-319-57418-9_15.
• [16] Bernardinello L, Ferigato C, Pomello L. An algebraic model of observable properties in distributed systems. Theoretical Computer Science, 2003. 290(1):637-668. URL https://doi.org/10.1016/S0304-3975(02)00046-4.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).