Enforcing ω-Regular Properties in Markov Chains by Restarting

ESPARZA, Javier; Stefan KIEFER; Jan KŘETÍNSKÝ a Maximilian WEININGER. Enforcing ω-Regular Properties in Markov Chains by Restarting. In 32nd International Conference on Concurrency Theory, CONCUR 2021, August 24-27, 2021, Virtual Conference. Dagstuhl, 2021, s. 1-22. ISBN 9783959772037. Dostupné z: https://doi.org/10.4230/LIPICS.CONCUR.2021.5.

Základní údaje

Originální název

Enforcing ω-Regular Properties in Markov Chains by Restarting

Autoři

ESPARZA, Javier; Stefan KIEFER; Jan KŘETÍNSKÝ a Maximilian WEININGER

Vydání

32nd International Conference on Concurrency Theory, CONCUR 2021, August 24-27, 2021, Virtual Conference. od s. 1-22, 22 s. 2021

Nakladatel

Dagstuhl

---

Další údaje

Typ výsledku

Stať ve sborníku

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

ISBN

9783959772037

ISSN

DOI

https://doi.org/10.4230/LIPICS.CONCUR.2021.5

---

Anotace

V originále

Restarts are used in many computer systems to improve performance. Examples include reloading a webpage, reissuing a request, or restarting a randomized search. The design of restart strategies has been extensively studied by the performance evaluation community. In this paper, we address the problem of designing universal restart strategies, valid for arbitrary finite-state Markov chains, that enforce a given ω-regular property while not knowing the chain. A strategy enforces a property φ if, with probability 1, the number of restarts is finite, and the run of the Markov chain after the last restart satisfies φ. We design a simple "cautious" strategy that solves the problem, and a more sophisticated "bold"strategy with an almost optimal number of restarts.