Norm Functions for Probabilistic Bisimulations with Delays

Christel BaierChristel Baier, Mariëlle StoelingaMariëlle Stoelinga

DOI Link

Christel Baier, Mariëlle Stoelinga
Norm Functions for Probabilistic Bisimulations with Delays
3rd International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), volume 1784 of Lecture Notes in Computer Science, 1--16, 2000. Springer

Details
Bibtex

KurzfassungAbstract
We consider action-labelled systems with non-deterministic and probabilistic choice. Using the concept of norm functions [17], we introduce two types of bisimulations (called (strict) normed bisimulation equivalence) that allow for delays when simulating a transition and are strictly between strong and weak bisimulation equivalence à la [26,36,37]. Using a suitable modification of the prominent splitter/partitioning technique [25,30], we present polynomial-time algorithms that constructs the quotient space of the (strict) normed bisimulation equivalence classes.
Forschungsgruppe:Research Group: Verifikation und formale quantitative Analyse„Verifikation und formale quantitative Analyse“ befindet sich nicht in der Liste (Computational Logic, Automatentheorie, Wissensverarbeitung, Knowledge-Based Systems, Knowledge Systems, Wissensbasierte Systeme, Logische Programmierung und Argumentation, Algebra und Diskrete Strukturen, Knowledge-aware Artificial Intelligence, Algebraische und logische Grundlagen der Informatik) zulässiger Werte für das Attribut „Forschungsgruppe“.Algebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-46432-8_1.

@inproceedings{BS2000,
  author    = {Christel Baier and Mari{\"{e}}lle Stoelinga},
  title     = {Norm Functions for Probabilistic Bisimulations with Delays},
  booktitle = {3rd International Conference on Foundations of Software Science
               and Computation Structures (FoSSaCS)},
  series    = {Lecture Notes in Computer Science},
  volume    = {1784},
  publisher = {Springer},
  year      = {2000},
  pages     = {1--16},
  doi       = {10.1007/3-540-46432-8_1}
}