elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

Computing Quantiles in Markov Reward Models

Ummels, Michael und Baier, Christel (2013) Computing Quantiles in Markov Reward Models. In: Foundations of Software Science and Computation Structures, 7794, Seiten 353-368. Springer. FOSSACS 2013, 18.-20. März 2013, Rom, Italien. doi: 10.1007/978-3-642-37075-5_23. ISBN 978 3 642 37074 8. ISSN 0302-9743.

[img] PDF (Vortragsfolien)
653kB

Offizielle URL: http://dx.doi.org/10.1007/978-3-642-37075-5_23

Kurzfassung

Probabilistic model checking mainly concentrates on techniques for reasoning about the probabilities of certain path properties or expected values of certain random variables. For the quantitative system analysis, however, there is also another type of interesting performance measure, namely quantiles. A typical quantile query takes as input a lower probability bound p and a reachability property. The task is then to compute the minimal reward bound r such that with probability at least p the target set will be reached before the accumulated reward exceeds r. Quantiles are well-known from mathematical statistics, but to the best of our knowledge they have not been addressed by the model checking community so far. In this paper, we study the complexity of quantile queries for until properties in discrete-time finite-state Markov decision processes with non-negative rewards on states. We show that qualitative quantile queries can be evaluated in polynomial time and present an exponential algorithm for the evaluation of quantitative quantile queries. For the special case of Markov chains, we show that quantitative quantile queries can be evaluated in time polynomial in the size of the chain and the maximum reward.

elib-URL des Eintrags:https://elib.dlr.de/82743/
Dokumentart:Konferenzbeitrag (Vortrag)
Titel:Computing Quantiles in Markov Reward Models
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Ummels, Michaelmichael.ummels (at) dlr.deNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Baier, ChristelTU DresdenNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:2013
Erschienen in:Foundations of Software Science and Computation Structures
Referierte Publikation:Ja
Open Access:Ja
Gold Open Access:Nein
In SCOPUS:Nein
In ISI Web of Science:Nein
Band:7794
DOI:10.1007/978-3-642-37075-5_23
Seitenbereich:Seiten 353-368
Herausgeber:
HerausgeberInstitution und/oder E-Mail-Adresse der HerausgeberHerausgeber-ORCID-iDORCID Put Code
Pfennig, FrankCarnegie Mellon UniversityNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Verlag:Springer
Name der Reihe:Lecture Notes in Computer Science
ISSN:0302-9743
ISBN:978 3 642 37074 8
Status:veröffentlicht
Stichwörter:Quantiles, Markov Decision Processes, Probabilistic Model Checking
Veranstaltungstitel:FOSSACS 2013
Veranstaltungsort:Rom, Italien
Veranstaltungsart:internationale Konferenz
Veranstaltungsdatum:18.-20. März 2013
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Verkehr
HGF - Programmthema:Verkehrsmanagement (alt)
DLR - Schwerpunkt:Verkehr
DLR - Forschungsgebiet:V VM - Verkehrsmanagement
DLR - Teilgebiet (Projekt, Vorhaben):V - Projekt Next Generation Railway System II (alt)
Standort: Braunschweig
Institute & Einrichtungen:Institut für Verkehrssystemtechnik > Bahnsysteme
Hinterlegt von: Ummels, Michael
Hinterlegt am:02 Jul 2013 10:39
Letzte Änderung:10 Jul 2023 12:08

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.