License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2018.20
URN: urn:nbn:de:0030-drops-95586
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9558/
Go to the corresponding LIPIcs Volume Portal

Grigore, Radu ; Kiefer, Stefan

Selective Monitoring

pdf-format:
LIPIcs-CONCUR-2018-20.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{grigore_et_al:LIPIcs:2018:9558,
  author =	{Radu Grigore and Stefan Kiefer},
  title =	{{Selective Monitoring}},
  booktitle =	{29th International Conference on Concurrency Theory  (CONCUR 2018)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Sven Schewe and Lijun Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9558},
  URN =		{urn:nbn:de:0030-drops-95586},
  doi =		{10.4230/LIPIcs.CONCUR.2018.20},
  annote =	{Keywords: runtime monitoring, probabilistic systems, Markov chains, automata, language equivalence}
}

Keywords: runtime monitoring, probabilistic systems, Markov chains, automata, language equivalence
Collection: 29th International Conference on Concurrency Theory (CONCUR 2018)
Issue Date: 2018
Date of publication: 31.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI