Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Dependable and Optimal Cyber-Physical Systems Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Configuration- and Residual-Based Transition Systems for Event Structures with Asymmetric Conflict

verfasst von : Eike Best, Nataliya Gribovskaya, Irina Virbitskaite

Erschienen in: SOFSEM 2017: Theory and Practice of Computer Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In order to associate a transition system with an event structure, it is customary to use configurations, constructing a transition system by repeatedly adding executable events. It is also possible to use residuals, constructing a transition system by repeatedly deleting non-executable events. The present paper proposes a systematic investigation of how the two methods are interrelated. The focus will be on asymmetric versions of prime, bundle, and dual event structures. For each of them, configuration-based and residual-based transition system semantics will be defined. The pairwise bisimilarity of the resulting transition systems will be proved, considering interleaving, multiset, and pomset semantics.

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 Completeness of Hoare Logic Relative to the Standard Model
Nächstes Kapitel Hardness of Deriving Invertible Sequences from Finite State Machines
Fußnoten
1
For a set \(Y \subseteq X\) and a relation \(r\subseteq X\times X\), \(r_Y\) denotes the restriction of r to Y.
 
2
A relation \(r\subseteq X\times X\) is acyclic if it has no “cycles” of the form \(e_0\ r\ e_1\ r\ \ldots \ r\ e_n\ r\ e_0\), with \(n\ge 1\) and \(e_i\in X\) for all \(0\le i\le n\).
 
3
A relation \(r\subseteq X\times X\) is well-founded if it has no infinite descending chains, i.e., \(\langle e_i\rangle _{i\in \mathbb {N}}\) such that \(e_{i+1}\ r\ e_i\), \(e_i\ne e_{i+1}\), for all \(i\in \mathbb {N}\).
 
4
Stability ensures that two distinct events of a bundle set are in mutual disabling.
 
5
Notice that in [8], for asymmetric bundle/dual event structures the removal operator has been defined in a different way, without removing conflict sets. All the events in a trace t and bundles \(W\mapsto e\) such that \(W\cap \overline{t}\ne \emptyset \) are removed. However, the events conflicting with some event in t are retained simply making them impossible by adding empty bundles. There, the removal operator has been formally defined as follows: \(\mathcal {E}{\setminus } [t]=(E'\), \(\mapsto '\), \(\rightsquigarrow \cap (E'\times E')\), L, \(l\mid _{E'})\), where \(E'= E{\setminus }\overline{t}\) and \(\mapsto '= \big (\!\!\mapsto {\setminus }\{(W,e)\in \ \mapsto \mid W\cap \overline{t}\ne \emptyset \}\big )\) \(\cup \) \(\{(\emptyset ,e)\mid e\in E'\), \(e\rightsquigarrow e'\), for some \(e'\in \overline{t}\}\). We say in advance that the “residual” transition systems constructed on the base of the removal operator from [8] and our removal operator are isomorphic. This implies that all bisimilarity results obtained in our paper are valid for event structures treated within the process algebra PA in the work [8].
 
6
We allow a single arrow between two states to denote multiple transitions. For instance, the arrow from \(\mathcal {E}^p\) to \(\mathcal {E}_{\emptyset }\) in \( TE _{pom}(\mathcal {E}^p)\) (Fig. 3) denotes two transitions.
 
Literatur
1.
Baldan, P., Corradini, A., Montanari, U.: Contextual petri nets, asymmetric event structures, and processes. Inf. Comput. 171(1), 1–49 (2001)MathSciNetCrossRefMATH
2.
3.
4.
van Glabbeek, R.J., Goltz, U.: Refinement of actions and equivalence notions for concurrent systems. Acta Informatica 37, 229–327 (2001)MathSciNetCrossRefMATH
5.
van Glabbeek, R.J., Plotkin, G.D.: Configuration structures, event structures and petri nets. Theor. Comput. Sci. 410(41), 4111–4159 (2009)MathSciNetCrossRefMATH
6.
7.
Gutierrez, J., Wooldridge, M.: Equilibria of concurrent games on event structures. In: Proceedings of CSL-LICS 2014, pp. 46:1–46:10 (2014)
8.
Katoen, J.-P.: Quantitative and qualitative extensions of event structures. Ph.D. thesis. Twente University (1996)
9.
Langerak, R.: Bundle event structures: a non-interleaving semantics for LOTOS. In: Formal Description Techniques V, IFIP Transactions, C-10 (1993)
10.
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). doi:10.​1007/​3-540-63141-0_​22 CrossRef
11.
Loogen, R., Goltz, U.: Modelling nondeterministic concurrent processes with event structures. Fundamenta Informatica XIV, 39–74 (1991)MathSciNetMATH
12.
Majster-Cederbaum, M., Roggenbach, M.: Transition systems from event structures revisited. Inf. Process. Lett. 67(3), 119–124 (1998)MathSciNetCrossRefMATH
13.
14.
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). doi:10.​1007/​3-540-48068-4_​20 CrossRef
15.
Pinna, G.M., Poigné, A.: On the nature of events: another perspectives in concurrency. Theor. Comput. Sci. 138(2), 425–454 (1995)MathSciNetCrossRefMATH
16.
Winskel, G.: Events in computation. Ph.D. thesis. University of Edinburgh (1980)
17.
18.
Winskel, G., Nielsen, M.: Models for concurrency. In: Handbook of Logic in Computer Science, vol. 4 (1995)
19.
Metadaten
Titel
Configuration- and Residual-Based Transition Systems for Event Structures with Asymmetric Conflict
verfasst von
Eike Best
Nataliya Gribovskaya
Irina Virbitskaite
Copyright-Jahr
2017
Buch
SOFSEM 2017: Theory and Practice of Computer Science

Print ISBN: 978-3-319-51962-3

Electronic ISBN: 978-3-319-51963-0

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-51963-0_11

Premium Partner

    Bildnachweise