Event Structures for Arbitrary Disruption

• Autorzy: Fecher H. , Majster-Cederbaum M.
• Języki publikacji: EN

Abstrakty

EN

In process algebras that allow for some form of disruption, it is important to state when a process terminates. One option is to include a termination action Ö. Another approach is that the `final' executed action of a process terminates the process. The semantics of the former approach has been investigated in the literature in detail, e.g. by providing consistent true-concurrency and operational descriptions. The `final' executed action termination approach, which is more adequate for modelling, still lacks the existence of a detailed true concurrent description. In order to give a true concurrency model of such a termination view, we introduce a new class of event structures. This type of event structures models disabling by indicating sets of precursor events. We show that the introduced class of event structures has more expressive power with respect to event traces than the common event structures. We also give a classification of the expressive power in terms of sets of event traces. A consistency result of an operational and a denotational semantics is shown.

Słowa kluczowe

EN

event structures; disruption; termination; expressive power; process algebras

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 68, nr 1/2
• Strony: 103--130
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Fecher H.

• Christian Albrecht Universität zu Kiel Technische Fakultät, Institut für Informatik, Hermann-Rodewaldstr. 3, 24118 Kiel, Germany

autor

Majster-Cederbaum M.

• Universität Mannheim Fakultät für Mathematik und Informatik, D7, 27, 68131 Mannheim, Germany

Bibliografia

• [1] Abramsky, S., Jung, A.: Domain Theory, in: Handbook of Logic in Computer Science (S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, Eds.), vol. 3, Clarendon Press, 1994, 1–168.
• [2] Baeten, J. C. M., Bergstra, J. A.: Mode Transfer in Process Algebra, Report CSR 00-01, Vakgroep Informatica, Technische Universiteit Eindhoven, 2000.
• [3] Baeten, J. C. M., Bergstra, J. A., Klop, J. W.: Syntax and defining equations for an interrupt mechanism in process algebra, Fundamenta Informaticae, 9, 1986, 127–168.
• [4] Baier, C., Majster-Cederbaum, M. E.: The Connection between an Event Structure Semantics and an Operational Semantics for TCSP, Acta Informatica, 31, 1994, 81–104.
• [5] de Bakker, J., de Roever, W.-P., Rozenberg, G., Eds.: Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, vol. 354 of LNCS, Springer-Verlag, 1989.
• [6] Baldan, P., Busi, N., Corradini, A., Pinna, G. M.: Functional Concurrent Semantics for Petri Nets with Read and Inhibitor Arcs, CONCUR 2000 – Concurrency Theory (C. Palamidessi, Ed.), LNCS, vol. 1877 of LNCS, Springer-Verlag, 2000, 442–457.
• [7] Baldan, P., Corradini, A.,Montanari, U.: Contextual Petri Nets, Asymmetric Event Structures, and Processes, Information and Computation, 171, 2001, 1–49.
• [8] Bergstra, J. A., Fokkink,W., Ponse, A.: Process Algebra with Recursive Operations, in: Bergstra et al. [10], 333–389.
• [9] Bergstra, J. A., Klop, J.W.: Process Algebra for Synchronous Communication, Information and Control, 60, 1984, 109–137.
• [10] Bergstra, J. A., Ponse, A., Smolka, S. A., Eds.: Handbook of Process Algebra, North-Holland, 2001.
• [11] Bolognesi, T., Brinksma, E.: Introduction to the ISO Specification Language LOTOS, Computer Networks and ISDN Systems, 14, 1987, 25–59.
• [12] Boudol, G., Castellani, I.: Permutation of transitions: an event structure semantics for CCS and SCCS, in: de Bakker et al. [5], 411–427, 411–427.
• [13] Bravetti, M., Gorrieri, R.: Deciding and Axiomatizing Weak ST Bisimulation for a Process Algebra with Recursion and Action Refinement, ACMTCL: ACM Transactions on Computational Logic, 3, 2002.
• [14] Diertens, B.: New Features in PSF I – Interrupts, Disrupts, and Priorities, Report P9417, Programming Research Group - University of Amsterdam, 1994.
• [15] Engels, A., Cobben, T.: Interrupt and Disrupt in MSC: Possibilities and Problems, Proceedings for the 1st Workshop of the SDL Forum Society on SDL and MSC (Y. Lahav, A. Wolisz, J. Fischer, E. Holz, Eds.), Informatikberichte, number 104 in Informatikberichte, Humboldt-Universitt zu Berlin, 1998.
• [16] Fecher, H.: Action Refinement in End-Based Choice Settings, Ph.D. Thesis, Universität Mannheim, 2003.
• [17] Glabbeek, R. v., Plotkin, G. D.: Configuration Structures, Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, 1995, 199–209.
• [18] Gorrieri, R., Rensink, A.: Action Refinement, in: Bergstra et al. [10], 1047–1147.
• [19] Gunawardena, J.: A Generalized Event Structure for the Muller Unfolding of a Safe Net, CONCUR ’93 (E. Best, Ed.), LNCS, vol. 715 of LNCS, Springer-Verlag, 1993, 278–292.
• [20] Hoogers, P. W., Kleijn, H. C. M., Thiagarajan, P. S.: An event structure semantics for general Petri nets, Theoretical Computer Science, 153, 1996, 129–170.
• [21] Katoen, J.-P.: Quantitative and Qualitative Extension of Event Structures, Ph.D. Thesis, Enschede: Centre for Telematics and Information Technology, P.O. Box 217 - 7500 AE Enschede - The Netherlands, 1996.
• [22] Langerak, R.: Transformations and Semantics for LOTOS, Ph.D. Thesis, Department of Computer Science, University of Twente, 1992.
• [23] Langerak, R.: Bundle Event Structures: A Non-Interleaving Semantics for LOTOS, Formal Description Techniques, V (M. Diaz, R. Groz, Eds.), Elsevier, 1993, 331–346.
• [24] Majster-Cederbaum, M., Roggenbach, M.: Transition systems from event structures revisited, Information Processing Letters, 67, 1998, 119–124.
• [25] Milner, R.: Communication and Concurrency, International Series in Computer Science, Prentice Hall, 1989.
• [26] Nielsen,M., Plotkin, G.,Winskel, G.: Petri Nets, Event Structures and Domains, Part I, Theoretical Computer Science, 13, 1981, 85–108.
• [27] Pinna, G. M., Poigne, A.: Event Automata as a Generic Model of Reactive Systems, KORSO: Methods, Languages, and Tools for the Construction of Correct Software (M. Broy, S. Jähnichen, Eds.), LNCS, vol. 1009 of LNCS, Springer-Verlag, 1995, 74–91.
• [28] Pinna, G. M., Poigné, A.: On the nature of events: another perspective in concurrency, Theoretical Computer Science, 138 (2), 1995, 425–454.
• [29] Winskel, G.: An Introduction to Event Structures, in: de Bakker et al. [5], 364–397, 364–397.