Counterexample Explanation by Learning Small Strategies in Markov Decision Processes
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00080918" target="_blank" >RIV/00216224:14330/15:00080918 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-21690-4_10" target="_blank" >http://dx.doi.org/10.1007/978-3-319-21690-4_10</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-21690-4_10" target="_blank" >10.1007/978-3-319-21690-4_10</a>
Alternative languages
Result language
angličtina
Original language name
Counterexample Explanation by Learning Small Strategies in Markov Decision Processes
Original language description
For deterministic systems, a counterexample to a property can simply be an error trace, whereas counterexamples in probabilistic systems are necessarily more complex. For instance, a set of erroneous traces with a sufficient cumulative probability mass can be used. Since these are too large objects to understand and manipulate, compact representations such as subchains have been considered. In the case of probabilistic systems with non-determinism, the situation is even more complex. While a subchain for a given strategy (or scheduler, resolving non-determinism) is a straightforward choice, we take a different approach. Instead, we focus on the strategy itself, and extract the most important decisions it makes, and present its succinct representation.The key tools we employ to achieve this are (1) introducing a concept of importance of a state w.r.t. the strategy, and (2) learning using decision trees. There are three main consequent advantages of our approach.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Computer Aided Verification: 27th International Conference, CAV 2015
ISBN
9783319216898
ISSN
0302-9743
e-ISSN
—
Number of pages
20
Pages from-to
158-177
Publisher name
Springer
Place of publication
Cham
Event location
Cham
Event date
Jan 1, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—