IMPLEMENTIERUNG EINES PREFLOW-ALGORITHMUS FÜR MARKOVKETTEN
Eine vollständige formale Semantik für die Web Service Beschreibungssprache BPEL 2.0
Verteilte Java Anwendungen: Kann das gut gehen?
Reflexive und transitive Abschluss eines gerichtetes azyklisches Graphes
Implementierung eines Preflow-Algorithmus für Markovketten
Eine Implementierung mit PEPP
Interactive Simulator for MoDeST (abgeschlossen)
Die richtige Ordnung in "Compositional Aggregation" (laufend)
Präzision von MANET-Simulatoren
Diskrete Ereignissimulation (laufend)
Abbildung von StoCharts nach MoDeST (abgeschlossen)
Energieverbrauch in Ad-Hoc und Sensor-Netzwerken (abgeschlossen)
Axiomatisierung von "Branching Bisimulation" mit Divergenz (abgeschlossen)
Value Passing MoDeST (abgeschlossen)
Automatische Abbildung von MoDeST Spezifikationen auf UPPAAL (abgeschlossen)

Titel der Arbeit

Implementierung eines Preflow-Algorithmus für Markovketten (abgeschlossen)


Inhalt

 

Starke Simulation auf Markovketten (MKen) wurde in [BEM00] mit Hilfe von

Weight-Funktionen eingeführt. Für zwei Zustände s und s' der Kette, sind folgende Aussagen äquivalent:

  • Es gibt eine Weight-Funktion zwischen s und s'

  • Der Maximumfluss des Netzwerkes über s und s' hat den Wert 1.

Der Maximumfluss lässt sich dabei effizient mit dem Preflow-Algorithmus [GT88] berechnen.

Basierend auf dieser Beobachtung, kann daher ein Algorithmus entwickelt werden, um die Starke Simulation fuer MKen zu bestimmen. In aktueller Forschungsarbeit haben wir gezeigt, dass mit Hilfe von Parametric-Preflow Methoden [GGT89] diese Starke Simulation viel effizienter berechnet werden kann.

 

In dieser Arbeit geht es daher darum, Algorithmen für

  • Parametric preflow

  • Starke Simulation über MKen

zu implementieren, und die erzielten Resultate durch praktische Experimente zu stützen.

 

 


Vorraussetzungen

C++ Erfahrungen.


Status

Abgeschlossen


Kontakt:

Lijun Zhang


Kommentar

Eine verwandte Masterarbeit ist verfuegbar


Verweise

[GT88]:A. Goldberg and R. Tarjan. A New Approach to the Maximum Flow Problem. Journal of the Association for Computing Machinery, 35:921--940, 1988.
[GGT89]: Gallo, G., Grigoriadis, M.D., & Tarjan, R.E. (1989), `A fast parametric maximum flow algorithm and applications', SIAM J. Computing 18, 30--55.
[BEM00]: C. Baier, B. Engelen, M. Majster-Cederbaum: Deciding Bisimilarity and Similarity for Probabilistic Processes, Journal of Computer and System Sciences 60, pp 187-231, 2000