| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Foundation of Diagnosis and Predictability in Probabilistic Systems
Abstract : In discrete event systems prone to unobservable faults, a diagnoser must eventually detect fault occurrences. The diagnosability problem consists in deciding whether such a diagnoser exists. Here we investigate diagnosis for probabilistic systems modelled by partially observed Markov chains also called probabilistic labeled transition systems (pLTS). First we study different spe-cifications of diagnosability and establish their relations both in finite and infinite pLTS. Then we analyze the complexity of the diagnosability problem for finite pLTS: we show that the polynomial time procedure earlier proposed is erroneous and that in fact for all considered specifications, the problem is PSPACE-complete. We also establish tight bounds for the size of diagnosers. Afterwards we consider the dual notion of predictability which consists in predicting that in a safe run, a fault will eventually occur. Predictability is an easier problem than diagnosability: it is NLOGSPACE-complete. Yet the predictor synthesis is as hard as the diagnoser synthesis. Finally we introduce and study the more flexible notion of prediagnosability that generalizes predictability and diagnosability.
Cited literature [13 references]
https://hal.inria.fr/hal-01088117
Contributor : Nathalie Bertrand <>
Submitted on : Thursday, November 27, 2014 - 2:19:07 PM
Last modification on : Tuesday, June 15, 2021 - 4:28:22 PM
Long-term archiving on: : Monday, March 2, 2015 - 9:24:10 AM
Contributor : Nathalie Bertrand <>
Submitted on : Thursday, November 27, 2014 - 2:19:07 PM
Last modification on : Tuesday, June 15, 2021 - 4:28:22 PM
Long-term archiving on: : Monday, March 2, 2015 - 9:24:10 AM
File
paper-90.pdf
Files produced by the author(s)