nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

From Event-Oriented Models to Transition Systems

verfasst von : Eike Best, Nataliya Gribovskaya, Irina Virbitskaite

Erschienen in: Application and Theory of Petri Nets and Concurrency

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Two structurally different methods of associating transition system semantics to event-oriented models of distributed systems are distinguished in the literature. One of them is based on configurations (event sets), the other on residuals (model fragments). In this paper, a variety of models is investigated, ranging from extended prime event structures to configuration structures, and it is shown that the two semantics lead to isomorphic results. This strengthens prior work where bisimilarity (but not necessarily isomorphism) is achieved for a smaller range of models. Thanks to the isomorphisms obtained here, a wide range of facts known from the literature on configuration-based transition systems can be extended to residual-based ones.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Geometric Characterisation of Event/State Separation

Nächstes Kapitel Simplification of CTL Formulae for Efficient Model Checking of Petri Nets

Nur mit Berechtigung zugänglich

E.g., see [1, 2, 10, 11, 13‐16, 24, 28].

E.g., see [3, 6, 7, 16, 17, 19, 22, 25].

Recalled below in Sect. 1.1.

One of which is also shown in Sect. 1.1.

In an event structure, an event is called non-executable or impossible if it does not occur in any configuration of the structure, i.e. the event is never executed.

As explained in Sect. 1.1 on the example described there.

If the transitivity of \(\rightarrow \) is assumed, the arrow from \(*\) to c could be omitted, of course.

Even if this was technically not always straightforward.

The general idea of retaining an appropriate amount of structure during residual semantics (or, for that matter, unfolding semantics, when applied, e.g., to a process algebra) is not novel, nor claimed to be so. However, its application to the transition semantics of event structures is hoped to shed some new light onto this general idea.

An event is enabled once all of its causal predecessors have occurred.

An event is enabled once at least one of its causal predecessors have occurred.

It was noted in [1] that, as far as finite configurations are concerned, this does not lead to an increase in expressive power.

We shall use the notation for the other models through the paper.

Arbach, Y., Karcher, D., Peters, K., Nestmann, U.: Dynamic causality in event structures. In: Graf, S., Viswanathan, M. (eds.) FORTE 2015. LNCS, vol. 9039, pp. 83–97. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19195-9_6CrossRef

Armas-Cervantes, A., Baldan, B., Garcia-Banuelos, L.: Reduction of event structures under history preserving bisimulation. J. Log. Algebr. Methods Program. 85(6), 1110–1130 (2016)MathSciNetCrossRef

Baier, C., Majster-Cederbaum, M.: The connection between event structure semantics and operational semantics for TCSP. Acta Inform. 31, 81–104 (1994)MathSciNetCrossRef

Baldan, P., Corradini, A., Gadducci, F.: Domains and event structures for fusions. In: LICS, pp. 1–12 (2017)

Best, E., Gribovskaya, N., Virbitskaite, I.: Configuration- and residual-based transition systems for event structures with asymmetric conflict. In: Steffen, B., Baier, C., van den Brand, M., Eder, J., Hinchey, M., Margaria, T. (eds.) SOFSEM 2017. LNCS, vol. 10139, pp. 132–146. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-51963-0_11CrossRefMATH

Boudol, G.: Flow event structures and flow nets. In: Guessarian, I. (ed.) LITP 1990. LNCS, vol. 469, pp. 62–95. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-53479-2_4CrossRef

Crafa, S., Varacca, D., Yoshida, N.: Event structure semantics of parallel extrusion in the pi-calculus. In: Birkedal, L. (ed.) FoSSaCS 2012. LNCS, vol. 7213, pp. 225–239. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28729-9_15CrossRefMATH

Fecher, H., Majster-Cederbaum, M.: Event structures for arbitrary disruption. Fundam. Inform. 68(1–2), 103–130 (2005)MathSciNetMATH

van Glabbeek, R.J.: History preserving process graphs. Report, Stanford University. http://boole.stanford.edu/rvg/pub/abstracts/history

10.

van Glabbeek, R.J.: On the expressiveness of higher dimensional automata. Theor. Comput. Sci. 356(3), 265–290 (2006)MathSciNetCrossRef

11.

van Glabbeek, R.J., Goltz, U.: Refinement of actions and equivalence notions for concurrent systems. Acta Inform. 37, 229–327 (2001)MathSciNetCrossRef

12.

van Glabbeek, R.J., Plotkin, G.D.: Configuration structures. In: Proceedings of the LICS, pp. 199–209 (1995)

13.

van Glabbeek, R., Plotkin, G.: Event structures for resolvable conflict. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 550–561. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28629-5_42CrossRef

14.

van Glabbeek, R.J., Plotkin, G.D.: Configuration structures, event structures and Petri nets. Theor. Comput. Sci. 410(41), 4111–4159 (2009)MathSciNetCrossRef

15.

Hoogers, P.W., Kleijn, H.C.M., Thiagarajan, P.S.: An event structure semantics for general Petri nets. Theor. Comput. Sci. 153, 129–170 (1996)MathSciNetCrossRef

16.

Katoen, J.-P.: Quantitative and qualitative extensions of event structures. Ph.D. thesis, Twente University (1996)

17.

Katoen, J.-P., Langerak, R., Latella, D.: Modeling systems by probabilistic process algebra: an event structures approach. In: IFIP Transactions, vol. C-2, pp. 253–268 (1993)

18.

Keller, R.M.: Formal verification of parallel programs. Commun. ACM 19(7), 371–384 (1976)MathSciNetCrossRef

19.

Langerak, R.: Bundle event structures: a non-interleaving semantics for LOTOS. In: Formal Description Techniques V. IFIP Transactions, vol. C-10, pp. 331–346 (1993)

20.

Langerak, R., Brinksma, E., Katoen, J.-P.: Causal ambiguity and partial orders in event structures. In: Mazurkiewicz, A., Winkowski, J. (eds.) CONCUR 1997. LNCS, vol. 1243, pp. 317–331. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63141-0_22CrossRef

21.

Li, B., Koutny, M.: Unfolding CSPT-nets. In: Proceedings of the International Workshop on Petri Nets and Software Engineering (PNSE 2015), Brussels, Belgium, pp. 207–226, June 2015

22.

Loogen, R., Goltz, U.: Modelling nondeterministic concurrent processes with event structures. Fundam. Inform. 14(1), 39–74 (1991)MathSciNetMATH

23.

Majster-Cederbaum, M., Roggenbach, M.: Transition systems from event structures revisited. Inf. Process. Lett. 67(3), 119–124 (1998)MathSciNetCrossRef

24.

Nielsen, M., Plotkin, G., Winskel, G.: Petri nets, event structures and domains. Theor. Comput. Sci. 13(1), 85–108 (1981)MathSciNetCrossRef

25.

Nielsen, M., Thiagarajan, P.S.: Regular event structures and finite Petri nets: the conflict-free case. In: Esparza, J., Lakos, C. (eds.) ICATPN 2002. LNCS, vol. 2360, pp. 335–351. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-48068-4_20CrossRefMATH

26.

Pratt, V.: Chu spaces and their interpretation as concurrent objects. In: van Leeuwen, J. (ed.) Computer Science Today. LNCS, vol. 1000, pp. 392–405. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0015256CrossRef

27.

Winskel G.: Events in computation. Ph.D. thesis, University of Edinburgh (1980)

28.

Winskel, G.: Event structures. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) ACPN 1986. LNCS, vol. 255, pp. 325–392. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-17906-2_31CrossRef

29.

Winskel, G.: An introduction to event structures. In: de Bakker, J.W., de Roever, W.-P., Rozenberg, G. (eds.) REX 1988. LNCS, vol. 354, pp. 364–397. Springer, Heidelberg (1989). https://doi.org/10.1007/BFb0013026CrossRef

30.

Winskel, G., Nielsen, M.: Models for concurrency. In: Handbook of Logic in Computer Science, vol. 4 (1995)

31.

Winskel, G.: Distributed probabilistic and quantum strategies. Electron. Notes Theor. Comput. Sci. 298, 403–425 (2013)MathSciNetCrossRef

Titel: From Event-Oriented Models to Transition Systems
verfasst von: Eike Best
Nataliya Gribovskaya
Irina Virbitskaite
Verlag: Springer International Publishing
Buch: Application and Theory of Petri Nets and Concurrency
Print ISBN: 978-3-319-91267-7

Electronic ISBN: 978-3-319-91268-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-91268-4_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"