Shepherding Hordes of Markov Chains

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F19%3APU132063" target="_blank" >RIV/00216305:26230/19:PU132063 - isvavai.cz</a>

Result on the web

<a href="https://link.springer.com/chapter/10.1007/978-3-030-17465-1_10" target="_blank" >https://link.springer.com/chapter/10.1007/978-3-030-17465-1_10</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-17465-1_10" target="_blank" >10.1007/978-3-030-17465-1_10</a>

Result language

angličtina

Original language name

Shepherding Hordes of Markov Chains

Original language description

This paper considers large families of Markov chains (MCs) that are defined over a set of parameters with finite discrete domains. Such families occur in software product lines, planning under partial observability, and sketching of probabilistic programs. Simple questions, like does at least one family member satisfy a property?, are NP-hard. We tackle two problems: distinguish family members that satisfy a given quantitative property from those that do not, and determine a family member that satisfies the property optimally, i.e., with the highest probability or reward. We show that combining two well-known techniques, MDP model checking and abstraction refinement, mitigates the computational complexity. Experiments on a broad set of benchmarks show that in many situations, our approach is able to handle families of millions of MCs, providing superior scalability compared to existing solutions.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA17-12465S" target="_blank" >GA17-12465S: Verification and Bug Hunting for Advanced Software</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2019

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of 25th International Conference on Tools and Algorithms for the Construction and Analysis of Systems

ISBN

978-3-030-17464-4

ISSN

—

e-ISSN

—

Number of pages

19

Pages from-to

172-190

Publisher name

Springer International Publishing

Place of publication

Praha

Event location

Praha

Event date

Apr 8, 2019

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000681174300010