Closure Operators and Lattices Derived from Concurrency in Posets and Occurrence Nets

• Autorzy: Bernardinello L. , Pomello L. , Rombola S.
• Języki publikacji: EN

Abstrakty

EN

Partially ordered sets (posets), and among them occurrence nets, are a natural formal tool for studying concurrent processes. In a poset, the concurrency relation between elements is explicit. Starting from this relation, and applying standard techniques of lattice theory, one can build a complete lattice whose elements are subsets of the given poset. We study structural properties of such closed subsets, and of the lattice they form. In particular, we show that, if a poset is Ndense, then the lattice of closed subsets is orthomodular. A characterization of K-density, valid for posets, is given on the basis of a relation between lines, or chains, and closed sets. In the case of occurrence nets, we give a characterization of the closed subsets, and define the related notion of "causally closed subset"; a constructive characterization of such subsets is given, which justifies their interpretation as causally closed subprocesses of the occurrence net. We show that, for K-dense occurrence nets, closed subsets and causally closed subsets coincide. By using causally closed subsets, we give another characterization of K-density, related to the algebraicity of the lattice of closed sets.

Słowa kluczowe

EN

non-sequential processes; partial order semantics; closure operators; orthomodularity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 105, nr 3
• Strony: 211--235
• Opis fizyczny: Bibliogr. 20 poz., wykr.

Twórcy

autor

Bernardinello L.

autor

Pomello L.

autor

Rombola S.

• DISCo, Universita degli studi di Milano–Bicocca, viale Sarca 336 U14, Milano, Italia,

Bibliografia

• [1] Abramsky, S.: Petri Nets, Discrete Physics, and Distributed Quantum Computation, Concurrency, Graphs and Models (P. Degano, R. De Nicola, J. Meseguer, Eds.), 5065, Springer-Verlag, 2008.
• [2] Abramsky, S., Jung, A.: Domain Theory, Handbook of Logic in Computer Science, Clarendon Press, 1994.
• [3] Beltrametti, E. G., Cassinelli, G.: The logic of quantum mechanics, vol. 15 of Encyclopedia of Mathematics and its Applications, Addison-Wesley, Reading, Mass., 1981.
• [4] Bernardinello, L., Ferigato, C., Pomello, L., Rombolà, S.: Closure Operators Associated to Partially Ordered Sets, Workshop on Non-Classical Models for Automata and Applications (NCMA), Oesterreichische Computer Gesellschaft, 2009.
• [5] Bernardinello, L., Pomello, L., Rombolà, S.: Orthomodular Lattices in Occurrence Nets, in: Petri Nets 2009 (G. Franceschinis, K. Wolf, Eds.), vol. 5606 of LNCS, Springer-Verlag, 2009, 163-182.
• [6] Bernardinello, L., Pomello, L., Rombolà, S.: Orthomodular Lattices Induced by the Concurrency Relation, in: Proc. Fifth Workshop on Developments in Computational Models. (S. B. Cooper, V. Danos, Eds.), vol. 9 of EPTCS, 2009.
• [7] Best, E., Fernandez, C.: Nonsequential Processes-A Petri Net View, vol. 13 of EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1988.
• [8] Birkhoff, G.: Lattice Theory, American Mathematical Society; 3rd Ed., 1979.
• [9] Bombelli, L., Lee, J., Meyer, D., Sorkin, R.: Spacetime as a causal set, Phys. Rev. Lett., 60, 1985, 521-524.
• [10] Casini, H.: The logic of causally closed spacetime subsets, Class. Quantum Grav., 19, 2002, 6389-6404.
• [11] Cegła, W. Jadczyk, Z.: Causal logic of Minkowski space, Commun. Math. Phys., 57, 1977, 213-217.
• [12] Davey, B. A., Priestley, H. A.: Introduction to Lattices and Order, Cambridge University Press, 1990.
• [13] Fernandez, C., Thiagarajan, P. S.: A Lattice Theoretic View of K-Density, in: Advances in Petri Nets 1984, vol. 188 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 1985, 139-153.
• [14] Kalmbach, G.: Orthomodular Lattice, Academic Press, New York, 1983.
• [15] Nielsen, M., Plotkin, G. D., Winskel, G.: Petri Nets, Event Structures and Domains, Part I, Theoretical Computer Science, 13, 1981, 85-108.
• [16] Petri, C. A.: 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¨at Erlangen-Nürnberg. June 1976.
• [17] Petri, C. A.: Nets, Time and Space, Theoretical Computer Science, 153(1), 1996, 3-48.
• [18] Petri, C. A.: On the Physical Basis of Information Flow - Abstract, in: Applications and Theory of Petri Nets, vol. 5062 of LNCS, Springer, 2008.
• [19] Pták, P. Pulmannová, P.: Orthomodular Structures as Quantum Logics, Kluwer Academic Publishers, 1991.
• [20] Wolfram, S.: A New Kind of Science, Wolfram Media, 2002.