Andrea Turrini ; Holger Hermanns - Cost Preserving Bisimulations for Probabilistic Automata

lmcs:1050 - Logical Methods in Computer Science, December 18, 2014, Volume 10, Issue 4 - https://doi.org/10.2168/LMCS-10(4:11)2014
Cost Preserving Bisimulations for Probabilistic AutomataArticle

Authors: Andrea Turrini ; Holger Hermanns ORCID

    Probabilistic automata constitute a versatile and elegant model for concurrent probabilistic systems. They are equipped with a compositional theory supporting abstraction, enabled by weak probabilistic bisimulation serving as the reference notion for summarising the effect of abstraction. This paper considers probabilistic automata augmented with costs. It extends the notions of weak transitions in probabilistic automata in such a way that the costs incurred along a weak transition are captured. This gives rise to cost-preserving and cost-bounding variations of weak probabilistic bisimilarity, for which we establish compositionality properties with respect to parallel composition. Furthermore, polynomial-time decision algorithms are proposed, that can be effectively used to compute reward-bounding abstractions of Markov decision processes in a compositional manner.


    Volume: Volume 10, Issue 4
    Published on: December 18, 2014
    Imported on: March 10, 2014
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • Mobility between Europe and Argentina applying Logics to Systems; Funder: European Commission; Code: 295261

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1539 times.
    This article's PDF has been downloaded 444 times.