Skip to main content
Kent Academic Repository

Selective Monitoring

Grigore, Radu, Kiefer, Stefan (2018) Selective Monitoring. In: Leibniz International Proceedings in Informatics. 20. LIPICS, Germany (doi:10.4230/LIPIcs.CONCUR.2018.20) (KAR id:67553)


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)
DOI/Identification number: 10.4230/LIPIcs.CONCUR.2018.20
Uncontrolled keywords: runtime monitoring, probabilistic systems, Markov chains, automata, language equivalence
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Radu Grigore
Date Deposited: 02 Jul 2018 13:50 UTC
Last Modified: 16 Feb 2021 13:55 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.