Event Structures with Disabling/Enabling Relation and Event Automata

• Autorzy: Pinna G.M.
• Języki publikacji: EN

Abstrakty

EN

In recent years the consideration that events in evolutions of concurrent systems can happen with different histories has received ground. In particular the possibility that part of the history can be abstracted away or identified, like in the collective tokens philosophy for Petri Nets, has gained the stage. The various brands of event structures considered in literature are tailored to a fixed interpretation with respect to the history of an event. We investigate the adequateness of event structures with a disabling/enabling relation, to settle a common ground for the history dependent and history independent interpretations, and we establish a relationship between event automata and these notions of event structures.

Słowa kluczowe

EN

event structures; event automata; models for concurrency

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 3
• Strony: 409--430
• Opis fizyczny: bibliogr. 24 poz.

Twórcy

autor

Pinna G.M.

• Dipartimento di Matematica e Informatica, Universita di Cagliari, Via Ospedale 72, 09124 Cagliari, Italy,

Bibliografia

• [1] Badouel, E., Darondeau, P.: Theory of Regions., Lectures on Petri Nets I: Basic Models, Advances in Petri Nets (W. Reisig, G. Rozenberg, Eds.), Lecture Notes in Computer Science, vol. 1491 of Lecture Notes in Computer Science, Springer Verlag, 1998, 529-586.
• [2] Baldan, P.: Modelling concurrent computations: from contextual Petri nets to graph grammars, Ph.D. Thesis, Department of Computer Science, University of Pisa, 2000, Available as technical report n. TD-1/00.
• [3] Baldan, P., Busi, N., Corradini, A., Pinna, G. M.: Functorial Concurrent Semantics for Petri Nets with Read and Inhibitor Arcs, CONCUR'00 Conference Proceedings (C. Palamidessi, Ed.), Lecture Notes in Computer Science, vol. 1877 of Lecture Notes in Computer Science, Springer Verlag, 2000, 442-457.
• [4] Baldan, P., Busi, N., Corradini, A., Pinna, G. M.: Domain and Event Structure Semantics for Petri Nets with Read and Inhibitor Arcs, Theoretical Computer Science, 323(1-3), 2004, 129-189.
• [5] Baldan, P., Corradini, A., Montanari, U.: Contextual Petri nets, asymmetric event structures and processes, Information and Computation, 171(1), 2001, 1-49.
• [6] Bernardinello, L.: Synthesis of Net Systems, Proceedings of the 14th Confrence on the Application and Theory of Petri Nets (M. Ajmone Marsan, Ed.), Lecture Notes in Computer Science, vol. 691 of Lecture Notes in Computer Science, Springer Verlag, 1993, 89-105.
• [7] Busi, N., Pinna, G. M.: Synthesis of nets with inhibitor arcs, CONCUR'97 Conference Proceedings (A. Mazurkiewicz, J. Winkowski, Eds.), Lecture Notes in Computer Science, vol. 1243 of Lecture Notes in Computer Science, Springer Verlag, 1997, 151-165.
• [8] Busi, N., Pinna, G. M.: Contextual Event Structure and Petri Nets with Read and Inhibitor Arcs, 1999, Manuscript.
• [9] Busi, N., Pinna, G. M.: Process Semantics for Place/Transition Nets with Inhibitor and Read Arcs, Fundamenta Informaticae, 40(2-3), 1999, 165-197.
• [10] Degano, P., Priami, C.: Causality for Mobile Processes, Proceedings of ICALP'95 (Z. Fülöp, F. Gécseg, Eds.), 1995, 660-671.
• [11] Ehrenfeucht, A., Rozenberg, G.: Partial (Set) 2-Structures. Part I: Basic Notions and the Representation Problem. Part II: State Spaces of Concurrent Systems, Acta Informatica, 27(4), 1989, 315-368.
• [12] Gaifman, H.: Modeling concurrency by partial orders and nonlinear transition systems., Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, REX Workshop (J. W. de Bakker, W. P. de Roever, G. Rozenberg, Eds.), Lecture Notes in Computer Science, vol. 354 of Lecture Notes in Computer Science, Springer verlag, 1989, 467-488.
• [13] Gaifman, H., Pratt, V. R.: Partial Order Models of Concurrency and the Computation of Functions, Proceedings of the 2nd Symposium on Logic in Computer Science (D. Gries, Ed.), IEEE Computer Society, 1987, 72-85.
• [14] van Glabbeek, R. J., Plotkin, G. D.: Configuration Structures, Proceedings of 10th Annual IEEE Symposium on Logic in Computer Science (D. Kozen, Ed.), IEEE Computer Society Press, June 1995, 199-209.
• [15] van Glabbeek, R. J., Plotkin, G. D.: Event Structures for Resolvable Conflict., Proceedings of MFCS '04 (J. Fiala, V. Koubek, J. Kratochv´ıl, Eds.), Lecture Notes in Computer Science, vol. 3153 of Lecture Notes in Computer Science, Springer, 2004, 550-561.
• [16] Gunawardena, J.: Causal automata., Theoretical Computer Science, 101(2), 1992, 265-288.
• [17] Gunawardena, J.: A Generalized Event Structure for the Muller Unfolding of a Safe Net., CONCUR'93 Conference Proceedings (E. Best, Ed.), Lecture Notes in Computer Science, vol. 715 of Lecture Notes in Computer Science, Springer Verlag, 1993, 278-292.
• [18] Hoogers, P. W., Kleijn, H. C. M., Thiagarajan, P. S.: An event structure semantics for general Petri nets, Theoretical Computer Science, 153(1-2), 1996, 129-170.
• [19] Janicki, R., Koutny,M.: Semantics of Inhibitor Nets., Information and Computation, 123, 1995, 1-16.
• [20] Nielsen, M., Rozenberg, G., Thiagarajan, P.: Elementary transition systems, Theoretical Computer Science, 96(1), 1992, 3-33.
• [21] Pinna, G.M.: Event Structures for the Collective Tokens Philosophy of Inhibitor Nets, MFCS'05 Conference Proceedings (J. Je¸drzejowicz, A. Szepietowski, Eds.), Lecture Notes in Computer Science, vol. 3618 of Lecture Notes in Computer Science, Springer Verlag, 2005, 720-732.
• [22] Pinna, G. M., Poigné, A.: On the nature of events, MFCS'92 Conference Proceedings (I. M. Havel, V. Koubek, Eds.), Lecture Notes in Computer Science, vol. 629 of Lecture Notes in Computer Science, Springer Verlag, 1992, 430-441.
• [23] Pinna, G.M., Poigné, A.: On the nature of events: another perspective in concurrency, Theoretical Computer Science, 138(2), 1995, 425-454.
• [24] Winskel, G.: Event Structures, Petri Nets: Applications and Relationships to Other Models of Concurrency (W. Brauer, W. Reisig, G. Rozenberg, Eds.), Lecture Notes in Computer Science, vol. 255 of Lecture Notes in Computer Science, Springer Verlag, 1987, 325-392.