Closed Sets in Occurrence Nets with Conflicts

• Autorzy: Bernardinello L. , Ferigato C. , Haar S. , Pomello L.

Identyfikatory

DOI

10.3233/FI-2014-1079

• Języki publikacji: EN

Abstrakty

EN

The semantics of concurrent processes can be defined in terms of partially ordered sets. Occurrence nets, which belong to the family of Petri nets, model concurrent processes as partially ordered sets of occurrences of local states and local events. On the basis of the associated concurrency relation, a closure operator can be defined, giving rise to a lattice of closed sets. Extending previous results along this line, the present paper studies occurrence nets with forward conflicts, modelling families of processes. It is shown that the lattice of closed sets is orthomodular, and the relations between closed sets and some particular substructures of an occurrence net are studied. In particular, the paper deals with runs, modelling concurrent histories, and trails, corresponding to possible histories of sequential components. A second closure operator is then defined by means of an iterative procedure. The corresponding closed sets, here called ‘dynamically closed’, are shown to form a complete lattice, which in general is not orthocomplemented. Finally, it is shown that, if an occurrence net satisfies a property called B-density, which essentially says that any antichain meets any trail, then the two notions of closed set coincide, and they form a complete, algebraic orthomodular lattice.

Słowa kluczowe

EN

concurrency theory; partial order semantics; closure operators; orthomodular lattices

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 133, nr 4
• Strony: 323--344
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Bernardinello L.

• DISCo, Università degli studi di Milano - Bicocca viale Sarca 336 U14, Milano, Italia

autor

Ferigato C.

• JRC, Joint Research Centre of the European Commission, via E. Fermi, 1 21027 Ispra, Italia

autor

Haar S.

• LSV, CNRS & ENS de Cachan, avenue du Presidént Wilson 61, 94235 CACHAN Cedex, France

autor

Pomello L.

• DISCo, Università degli studi di Milano - Bicocca viale Sarca 336 U14, Milano, Italia

Bibliografia

• [1] E. G. Beltrametti and G. Cassinelli. The logic of quantum mechanics, volume 15 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, Mass., 1981.
• [2] L. Bernardinello, C. Ferigato, and L. Pomello. An algebraic model of observable properties in distributed systems. Theoretical Computer Science, 290:637–668, 2003.
• [3] Luca Bernardinello, Lucia Pomello, and Stefania Rombolà. Closure operators and lattices derived from concurrency in posets and occurrence nets. Fundamenta Informaticae, 105:211–235, 2010.
• [4] E. Best and C. Fernandez. Nonsequential Processes–A Petri Net View, volume 13 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1988.
• [5] G. Birkhoff. Lattice Theory. American Mathematical Society; 3rd Ed., 1979.
• [6] Rudolf Carnap. Introduction to Symbolic Logic and its applications. Dover Publications, Inc., 1958.
• [7] H. Casini. The logic of causally closed spacetime subsets. Class. Quantum Grav., 19:6389–6404, 2002.
• [8] Z. Cegła, W. Jadczyk. Causal logic of Minkowski space. Commun. Math. Phys., 57:213–217, 1977.
• [9] B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, 1990.
• [10] S. Haar. Occurrence net logic. Fundamenta Informaticae, 43:105–127, 2000.
• [11] G. Kalmbach. Orthomodular Lattices. Academic Press, New York, 1983.
• [12] C. A. Petri. Nets, time and space. Theoretical Computer Science, 153(1):3–48, 1996.