REFLEXIVE UND TRANSITIVE ABSCHLUSS EINES GERICHTETES AZYKLISCHES GRAPHES
 | ||
|
Logics towards POMDP with and/or without rewards
Energy consumption in Ad-Hoc and Sensor Networks
Stochastic Interfaces
An eclipse environment for Modest (finished)
Analysis of an Airbag Control Unit (finished)
Reflexiver und transitiver Abschluss eines gerichteten azyklischen Graphen
Reflexiver und transitiver Abschluss eines gerichteten azyklischen Graphen
Inhalt
Der reflexive und transitive Abschluss eines Graphen ist wichtig für viele verschiedene Informatik-Probleme. Zum Beispiel ist in CCS die schwache Transitionsrelation genau der reflexive und transitive Abschluss der internen Transitionen. Diese schwache Transitionsrelation benötigt man, um zu Entscheiden ob zwei System schwach Bisimilar sind. Das Problem ist, dass
die Berechnung der Abschlusses theoretisch komplex ist.
Vor kurzem wurde ein neuer, effizienter Algorithmus für die Berechnung von schwacher Bisimulation für azyklische Modelle entwickelt. Leider braucht man für diesen Algorithmus die schwache Transitionsrelation des Modells und deswegen bleibt die theoretische Komplexität schlecht.
Das Ziel dieses Arbeits ist, zu untersuchen, ob es einen Abschlussalgorithmus gibt, der für azyklische Modelle (praktisch oder theoretisch) "besser" ist als die gewöhnlichen Algorithmen, die die Azyklizität nicht ausnutzen.
Vorraussetzungen
Programmieren 1
Verifikation oder Nebenläufige Programmierung
Interesse an Graphentheorie
Status
Verfügbar
Kontakt
Verweise
 | Transitiver Abschluss (Wikipedia) |
| Milner, "Communication and Concurrency" |
| Aho, Hopcraft, Ullman, "The Design and Analysis of Computer Algorithms" |
| Crouzen, Hermanns, Zhang, "On the Minimization of Acyclic Models", CONCUR 2008 |