Journal article
Selective monitoring
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 579.4KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jcss.2020.09.003
Authors
- Publisher:
- Elsevier
- Journal:
- Journal of Computer and System Sciences More from this journal
- Volume:
- 117
- Pages:
- 99-129
- Publication date:
- 2020-11-18
- Acceptance date:
- 2020-09-17
- DOI:
- ISSN:
-
0022-0000
- Language:
-
English
- Keywords:
- Pubs id:
-
1137604
- Local pid:
-
pubs:1137604
- Deposit date:
-
2020-10-14
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier Inc.
- Copyright date:
- 2020
- Rights statement:
- © 2020 Elsevier Inc. All rights reserved.
- Notes:
-
This is the accepted manuscript version of the article. The final version is available from Elsevier at https://doi.org/10.1016/j.jcss.2020.09.003
If you are the owner of this record, you can report an update to it here: Report update to this record