Equivalences on Phase Type Processes

Wolf, Verena

Vorschau

PDF
thesisA4.pdf - Veröffentlichte Version
Download (1MB)

URL:	https://ub-madoc.bib.uni-mannheim.de/1911
URN:	urn:nbn:de:bsz:180-madoc-19111
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2008
Titel einer Zeitschrift oder einer Reihe:	None
Ort der Veröffentlichung:	Mannheim
Verlag:	Univ.
Hochschule:	Universität Mannheim
Gutachter:	Majster-Cederbaum, Mila
Datum der mündl. Prüfung:	15 April 2008
Sprache der Veröffentlichung:	Deutsch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Praktische Informatik II (Majster-Cederbaum -2005, Em)
Fachgebiet:	004 Informatik
Fachklassifikation:	CCS: F.1.1 F.4.3 F.1.2 I.6.4 G.3 ,
Normierte Schlagwörter (SWD):	Homogener abzählbarer Markov-Prozess , Mathematisches Modell , Parallelschaltung , Prozess <Informatik>
Freie Schlagwörter (Deutsch):	Prozess-Algebra , nebenläufig, Verifikation , Bisimulation , Spur-Äquivalenz
Freie Schlagwörter (Englisch):	Markov chain , process algebra , parallel composition , bisimulation , stochastic
Abstract:	In this thesis, we introduce Phase Type Processes (PTPs), a novel stochastic modeling approach that can express probabilistic and nondeterministic choices as well as random delays following phase type distributions, a generalization of exponential distributions. Action-labeled transitions are used to react on external stimuli and they are clearly separated from phase type transitions. The semantics of PTPs are defined in terms of path probabilities with respect to schedulers that resolve nondeterministic choices based on the timed process history. The main emphasis of this work is to analyze a variety of notions of equivalence for PTPs and classify them with respect to their distinguishing power. Amongst others, we define bisimulation, trace and testing equivalence as well as extensions of failure trace equivalence. Moreover, the contribution includes a discussion of parallel composition in the context of a partial memoryless property and the examination of a mapping from PTPs to the subclass of single phased processes in which all random delays are exponentially distributed.
Übersetzter Titel:	Equivalences on Phase Type Processes (Englisch)
Übersetzung des Abstracts:	Die vorliegende Arbeit analysiert und diskutiert einen neuartigen Ansatz zur Modellierung stochastischer Systeme, der auf sogenannten Phasentyp-Prozessen (PTPs) basiert. PTPs bieten die Möglichkeit von probablistischen Verzweigungen und Zustandsübergängen, die entweder mit einer zufälligen zeitlichen Verzögerung stattfinden oder eine (unverzögerte) atomare Aktion repräsentieren. Die Verzögerung eines zeitbehafteten Übergangs wird durch eine phasentyp-verteilte Zufallsvariable beschrieben. Phasentypverteilungen stellen eine Verallgemeinerung von Exponentialverteilungen dar und besitzen nur eine partielle Gedächtnislosigkeit. Atomare Aktionen ermöglichen eine Interaktion mit der Systemumgebung und ihre Ausführung ist klar getrennt von den Phasentypübergängen. Die Semantik eines PTPs wird durch die Definition eines Wahrscheinlichkeitsraumes über Ausführungssequenzen angegeben. Diese Sequenzen folgen den Regeln eines Schedulers, einer Instanz zur Auflösung nichtdeterministischer Entscheidungen basierend auf der Prozessvergangenheit. Der Schwerpunkt dieser Arbeit liegt auf der Analyse einer Vielzahl von Äquivalenzbegriffen für PTPs, die entsprechend ihrer Unterscheidungsfeinheit klassifiziert werden. Unter anderem werden Bisimulations-, Spur- und Testäquivalenz, sowie Erweiterungen der Spuräquivalenz definiert. Weiterhin beinhaltet die Arbeit eine Diskussion der parallelen Komposition von PTPs und die Untersuchung eines Operators, der PTPs auf Ein-Phasentyp-Prozesse abbildet. Unter Verwendung des Operators und der Tatsache, dass Ein-Phasentyp-Prozesse die volle Gedächtnislosigkeit besitzen, werden mögliche Auswege aus der Problematik der parallelen Komposition im Kontext einer partiellen Gedächtnislosigkeit diskutiert. (Deutsch)
Zusätzliche Informationen: