|
Über abstrakte Charakterisierungen von Bisimulation
Roggenbach, Markus
|
URL:
|
https://ub-madoc.bib.uni-mannheim.de/10
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-100
|
|
Dokumenttyp:
|
Dissertation
|
|
Erscheinungsjahr:
|
1998
|
|
Titel einer Zeitschrift oder einer Reihe:
|
None
|
|
Verlag:
|
Universität Mannheim
|
|
Gutachter:
|
Majster-Cederbaum, Mila
|
|
Datum der mündl. Prüfung:
|
1 Januar 1970
|
|
Sprache der Veröffentlichung:
|
Deutsch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
|
|
Fachgebiet:
|
510 Mathematik
|
|
Normierte Schlagwörter (SWD):
|
Theoretische Informatik , Semantik , Nebenläufigkeit
|
|
Freie Schlagwörter (Deutsch):
|
Bisimulation , Modelle parallelen Rechnens , Ereignisstruktur
|
|
Freie Schlagwörter (Englisch):
|
bisimulation , concurrency , semantics , event structures
|
|
Abstract:
|
Bisimulation wurde von Milner (1980) und Park (1981) auf Transitionssystemen eingefuehrt, um Prozesse zu identifizieren, die aus Sicht eines externen Beobachters nicht zu unterscheiden sind. Ausgehend von dieser Idee werden neue Bisimulationsbegriffe auch auf anderen Modellen parallelen Rechnens betrachtet, deren Definition von der Syntax her der urspruenglichen Definition von Bisimulation zumeist aehnlich sieht. Daraus erwaechst die Fragestellung: Was haben diese neuen Bisimulationen mit dem urspruenglichen Begriff zu tun, gibt es mehr als einen nur syntaktischen Zusammenhang zwischen ihnen, laesst sich ein gemeinsamer Ueberbegriff, eine abstrakte Charakterisierung finden? In der Literatur finden sich verschiedene Ansaetze fuer eine abstrakte Charakterisierung von Bisimulation: Degano, De Nicola und Montanari (1993) verwenden spezielle Baeume, Malacaria (1995) arbeitet mit Methoden der Algebra, Aczel und Mendler (1989) einerseits und Joyal, Nielsen und Winskel (1994) andereseits nutzen Begriffe der Kategorientheorie. Wir vergleichen in dieser Arbeit die beiden letztgenannten Ansaetze. Zum einen suchen wir nach direkten Zusammenhaengen zwischen den abstrakten Charakterisierungen. Zum anderen fragen wir uns, ob sich konkrete Bisimulationen auf unterschiedlichen Modellen parallelen Rechnens mittels der abstrakten Charakterisierungen darstellen lassen. Beide Vergleiche lassen den Schluss zu, dass die Charakterisierung von Aczel von den untersuchten Konzepten das umfassendste ist. Von daher beantworten wir die Frage, was eine Bisimulation ist, mit dem Begriff der AM-Bisimulation: Eine Bisimulation zwischen zwei Objekten ist ein Transitionssystem, welches das beobachtbare "Verhalten" wiedergibt, das beiden Objekten gemeinsam ist.
|
|
Übersetzung des Abstracts:
|
Bisimulation was introduced by Milner (1980) and Park (1981) in order to identify processes that cannot be distinguished by an external agent. Since then a large variety of notions of "bisimulation" have been studied, e.g. on labelled transition systems, on event structures, on petri nets. By now a series of different attempts have been made to give a uniform characterization of what should be considered as a bisimulation, mostly in algebraic and/or categorical framework. The purpose of this Ph.D.Thesis is to investigate how the coalgebraic approach of Aczel and Mendler (1989), which we call AM-bisimulation, and the categorical notion P-bisimulation and path-P-bisimulation of Joyal, Nielsen, and Winskel (1994) are related. We give translations between all three concepts: While it is always possible to turn a path-P-bisimulation into an AM-bisimulation, our construction for the reverse direction depends on several conditions. P-bisimilarity implies path-P-bisimilarity, but the concepts are equal only under strong conditions. Next we study how suitable the concepts AM-bisimulation, path-P-bisimulation and P-bisimulation are to encompass concrete notions of bisimulation on transition systems, synchronization trees, event structures, transition systems with independence. >From both studies, the more theoretical one on translations and the more concrete one on modelling, it turns out that looking for a unifying view of bisimulation AM-bisimulation seems to be the most promising concept of the three. Further on it gives a new perspective on the phenomen "bisimulation": While Milner introduces bisimulation as a relation which he interprets as "a kind of invariant holding between a pair of dynamic systems", AM-bisimulation itself is a dynamic system.
(Englisch)
|
|
Zusätzliche Informationen:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)