Über abstrakte Charakterisierungen von Bisimulation


Roggenbach, Markus


[img]
Preview
PDF
10_1.pdf - Published

Download (687kB)

URL: https://ub-madoc.bib.uni-mannheim.de/10
URN: urn:nbn:de:bsz:180-madoc-100
Document Type: Doctoral dissertation
Year of publication: 1998
The title of a journal, publication series: None
Publishing house: Universität Mannheim
Evaluator: Majster-Cederbaum, Mila
Date of oral examination: 1 January 1970
Publication language: German
Institution: School of Business Informatics and Mathematics > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
Subject: 510 Mathematics
Subject headings (SWD): Theoretische Informatik , Semantik , Nebenläufigkeit
Individual keywords (German): Bisimulation , Modelle parallelen Rechnens , Ereignisstruktur
Keywords (English): 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.
Translation of the abstract: 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. (English)
Additional information:




Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




Metadata export


Citation


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item