Selective Monitoring

Grigore, Radu and Kiefer, Stefan (2018) Selective Monitoring. In: 29th International Conference on Concurrency Theory (CONCUR 2018), 4--7 September 2018, Beijing, China, 4--7 September 2018, Beijing, China. (In press) (doi: (Access to this publication is currently restricted. You may be able to access a copy if URLs are provided)

PDF - Publisher pdf
Restricted to Repository staff only

Creative Commons Licence
This work is licensed under a Creative Commons Attribution 4.0 International License.
Contact us about this Publication Download (385kB)
Official URL


We study selective monitors for labelled Markov chains. Monitors observe the outputs that are generated by a Markov chain during its run, with the goal of identifying runs as correct or faulty. A monitor is selective if it skips observations in order to reduce monitoring overhead. We are interested in monitors that minimize the expected number of observations. We establish an undecidability result for selectively monitoring general Markov chains. On the other hand, we show for non-hidden Markov chains (where any output identifies the state the Markov chain is in) that simple optimal monitors exist and can be computed efficiently, based on DFA language equivalence. These monitors do not depend on the precise transition probabilities in the Markov chain. We report on experiments where we compute these monitors for several open-source Java projects.

Item Type: Conference or workshop item (Paper)
Uncontrolled keywords: runtime monitoring, probabilistic systems, Markov chains, automata, language equivalence
Divisions: Faculties > Sciences > School of Computing
Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Radu Grigore
Date Deposited: 02 Jul 2018 13:50 UTC
Last Modified: 02 Jul 2018 13:51 UTC
Resource URI: (The current URI for this page, for reference purposes)
Grigore, Radu:
  • Depositors only (login required):


Downloads per month over past year