Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Tight Game Abstractions of Probabilistic Automata
verfasst von : Falak Sher Vira, Joost-Pieter Katoen
Erschienen in: CONCUR 2014 – Concurrency Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a new game-based abstraction technique for probabilistic automata (PA). The key idea is to use
distribution
-based abstraction – preserving novel distribution-based (alternating) simulation relations – rather than classical
state
-based abstraction. These abstractions yield (simple) probabilistic game automata (PGA), turn-based 2 player stochastic games in which moves of both players – as opposed to classical stochastic games – yield distributions over states. As distribution-based (alternating) simulation relations are pre-congruences for composite PGA, abstraction can be done compositionally. Our abstraction yields tighter upper and lower bounds on (extremal) reachability probabilities than state-based abstraction. This shows the potential superiority over state-based abstraction of PA and Markov decision processes.