Equivalences on Phase Type Processes

Wolf, Verena

Preview

PDF
thesisA4.pdf - Published
Download (1MB)

URL:	https://ub-madoc.bib.uni-mannheim.de/1911
URN:	urn:nbn:de:bsz:180-madoc-19111
Document Type:	Doctoral dissertation
Year of publication:	2008
The title of a journal, publication series:	None
Place of publication:	Mannheim
Publishing house:	Univ.
University:	Universität Mannheim
Evaluator:	Majster-Cederbaum, Mila
Date of oral examination:	15 April 2008
Publication language:	German
Institution:	School of Business Informatics and Mathematics > Praktische Informatik II (Majster-Cederbaum -2005, Em)
Subject:	004 Computer science, internet
Classification:	CCS: F.1.1 F.4.3 F.1.2 I.6.4 G.3 ,
Subject headings (SWD):	Homogener abzählbarer Markov-Prozess , Mathematisches Modell , Parallelschaltung , Prozess <Informatik>
Individual keywords (German):	Prozess-Algebra , nebenläufig, Verifikation , Bisimulation , Spur-Äquivalenz
Keywords (English):	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.
Translation of the title:	Equivalences on Phase Type Processes (English)
Translation of the abstract:	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. (German)
Additional information: