Online Monitoring ω-Regular Properties in Unknown Markov Chains

Javier Esparza, Stefan Kiefer, Jan Kretínský, Maximilian Weininger

Abstract

We study runtime monitoring of $\omega$-regular properties. We consider a simple setting in which a run of an unknown finite-state Markov chain $\mathcal M$ is monitored against a fixed but arbitrary $\omega$-regular specification $\varphi$. The purpose of monitoring is to keep aborting runs that are "unlikely" to satisfy the specification until $\mathcal M$ executes a correct run. We design controllers for the reset action that (assuming that $\varphi$ has positive probability) satisfy the following property w.p.1: the number of resets is finite, and the run executed by $\mathcal M$ after the last reset satisfies $\varphi$.
BibTeX
@inproceedings{esparza2021online,
  author = {Javier Esparza and Stefan Kiefer and Jan Kretínský and Maximilian Weininger},
  title = {{Online Monitoring ω-Regular Properties in Unknown Markov Chains}},
  booktitle = {CONCUR},
  year = {2021},
  doi = {10.4230/lipics.concur.2021.5},
}
Figure