Adaptive formal approximations of Markov chains

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F21%3APU140793" target="_blank" >RIV/00216305:26230/21:PU140793 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.sciencedirect.com/science/article/pii/S0166531621000249" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0166531621000249</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.peva.2021.102207" target="_blank" >10.1016/j.peva.2021.102207</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Adaptive formal approximations of Markov chains

Popis výsledku v původním jazyce

We explore formal approximation techniques for Markov chains based on state-space reduction that aim at improving the scalability of the analysis, while providing formal bounds on the approximation error. We first present a comprehensive survey of existing state-reduction techniques based on clustering or truncation. Then, we extend existing frameworks for aggregation-based analysis of Markov chains by allowing them to handle chains with an arbitrary structure of the underlying state space - including continuous-time models - and improve upon existing bounds on the approximation error. Finally, we introduce a new hybrid scheme that utilises both aggregation and truncation of the state space and provides the best available approach for approximating continuous-time models. We conclude with a broad and detailed comparative evaluation of existing and new approximation techniques and investigate how different methods handle various Markov models. The results also show that the introduced hybrid scheme significantly outperforms existing approaches and provides a speedup of the analysis up to a factor of 30 with the corresponding approximation error bounded within 0.1%.

Název v anglickém jazyce

Adaptive formal approximations of Markov chains

Popis výsledku anglicky

We explore formal approximation techniques for Markov chains based on state-space reduction that aim at improving the scalability of the analysis, while providing formal bounds on the approximation error. We first present a comprehensive survey of existing state-reduction techniques based on clustering or truncation. Then, we extend existing frameworks for aggregation-based analysis of Markov chains by allowing them to handle chains with an arbitrary structure of the underlying state space - including continuous-time models - and improve upon existing bounds on the approximation error. Finally, we introduce a new hybrid scheme that utilises both aggregation and truncation of the state space and provides the best available approach for approximating continuous-time models. We conclude with a broad and detailed comparative evaluation of existing and new approximation techniques and investigate how different methods handle various Markov models. The results also show that the introduced hybrid scheme significantly outperforms existing approaches and provides a speedup of the analysis up to a factor of 30 with the corresponding approximation error bounded within 0.1%.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GJ20-02328Y" target="_blank" >GJ20-02328Y: CAQtuS: Počítačem podporovaná kvantitativní syntéza</a><br>

Návaznosti

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

Rok uplatnění

2021

Kód důvěrnosti údajů

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

Název periodika

PERFORMANCE EVALUATION

ISSN

0166-5316

e-ISSN

1872-745X

Svazek periodika

148

Číslo periodika v rámci svazku

102207

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

23

Strana od-do

1-23

Kód UT WoS článku

000648542900002

EID výsledku v databázi Scopus

2-s2.0-85105204964