Circular Causality in Event Structures

• Autorzy: Bartoletti M. , Cimoli T. , Pinna G. M. , Zunino R.

Identyfikatory

DOI

10.3233/FI-2014-1101

• Języki publikacji: EN

Abstrakty

EN

We propose a model of events with circular causality, in the form of a conservative extension of Winskel’s event structures. We study the relations between this new kind of event structures and Propositional Contract Logic. Provable atoms in the logic correspond to reachable events in our event structures. Furthermore, we show a correspondence between the configurations of this new brand of event structures and the proofs in a fragment of Propositional Contract Logic.

Słowa kluczowe

EN

event structures; contracts; intuitionistic logic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 3/4
• Strony: 219--259
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Bartoletti M.

• Dipartimento di Matematica e Informatica, Universitá degli Studi di Cagliari, Italy

autor

Cimoli T.

• Dipartimento di Matematica e Informatica, Universitá degli Studi di Cagliari, Italy

autor

Pinna G. M.

• Dipartimento di Matematica e Informatica, Universitá degli Studi di Cagliari, Italy

autor

Zunino R.

• Dipartimento di Matematica, Universitá degli Studi di Trento and COSBI, Italy

Bibliografia

• [1] Abadi, M., Lamport, L.: Composing Specifications, ACM Transactions on Programming Languages and Systems, 15(1), 1993.
• [2] Abadi, M., Plotkin, G. D.: A Logical View of Composition, Theoretical Computer Science, 114(1), 1993.
• [3] Baldan, P., Corradini, A.,Montanari, U.: Contextual Petri Nets, Asymmetric Event Structures, and Processes, Inf. Comput., 171(1), 2001, 1–49.
• [4] Bartoletti, M., Cimoli, T., Pinna, G. M.: Lending Petri nets and contracts, Proc. FSEN, 2013, To appear.
• [5] Bartoletti, M., Cimoli, T., Zunino, R.: A theory of agreements and protection, Proc. POST, 2013, To appear.
• [6] Bartoletti, M., Tuosto, E., Zunino, R.: Contract-oriented Computing in CO2 , Scientific Annals in Computer Science, 22(1), 2012, 5–60.
• [7] Bartoletti, M., Zunino, R.: A Calculus of Contracting Processes, LICS, 2010.
• [8] Boudol, G.: Flow Event Structures and Flow Nets, Semantics of Systems of Concurrent Processes, 469, Springer, 1990.
• [9] Cimoli, T.: A theory of agreements and protection, Ph.D. Thesis, Dipartimento di Matematica e Informatica, University of Cagliari, 2013.
• [10] Fairtlough,M., Mendler, M.: Propositional Lax Logic, Information and Computation, 137(1), 1997.
• [11] Hildebrandt, T. T.,Mukkamala, R. R.: Declarative Event-BasedWorkflow as Distributed Dynamic Condition Response Graphs, Proc. PLACES, 69, 2010.
• [12] Leroy, X., Grall, H.: Coinductive big-step operational semantics, Inf. Comput., 207(2), 2009, 284–304.
• [13] Maier, P.: Compositional Circular Assume-Guarantee Rules Cannot Be Sound and Complete, Proc. FoSSaCS, 2003.
• [14] Nielsen, M., Plotkin, G. D., Winskel, G.: Petri Nets, Event Structures and Domains, Part I, Theor. Comput. Sci., 13, 1981, 85–108.
• [15] Penczek,W.: Model-Checking for a Subclass of Event Structures, Proc. TACAS, 1217, Springer, 1997.
• [16] Pfenning, F.: Structural Cut Elimination - I. Intuitionistic and Classical Logic, Information and Computation, 157(1/2), 2000, 84–141.
• [17] Simon, L., Bansal, A., Mallya, A., Gupta, G.: Co-Logic Programming: Extending Logic Programming with Coinduction, Proc. ICALP, 2007.
• [18] Simon, L., Mallya, A., Bansal, A., Gupta, G.: Coinductive Logic Programming, in: Logic Programming, Springer, 2006, 330–345.
• [19] Statman, R.: Intuitionistic propositional logic is polynomial-space complete, Theoretical Computer Science, 9, 1979, 67–72.
• [20] Viswanathan, M., Viswanathan, R.: Foundations for Circular Compositional Reasoning, ICALP, 2001.
• [21] Winskel, G.: Event Structures, Advances in Petri Nets, 1986.
• [22] Winskel, G.: An Introduction to Event Structures, REX Workshop, 1988.