Skip to Main content Skip to Navigation
Conference papers

Accurate approximate diagnosability of stochastic systems

Nathalie Bertrand 1 Serge Haddad 2, 3 Engel Lefaucheux 2, 3, 1 
1 SUMO - SUpervision of large MOdular and distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
3 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], Inria Saclay - Ile de France
Abstract : Diagnosis of partially observable stochastic systems prone to faults was introduced in the late nineties. Diagnosability, i.e. the existence of a diagnoser, may be specified in different ways: (1) exact diag-nosability (called A-diagnosability) requires that almost surely a fault is detected and that no fault is erroneously claimed while (2) approximate diagnosability (called ε-diagnosability) allows a small probability of error when claiming a fault and (3) accurate approximate diagnosability (called AA-diagnosability) requires that this error threshold may be chosen arbitrarily small. Here we mainly focus on approximate diagnoses. We first refine the almost sure requirement about finite delay introducing a uniform version and showing that while it does not discriminate between the two versions of exact diagnosability this is no more the case in approximate diagnosis. Then we establish a complete picture for the decid-ability status of the diagnosability problems: (uniform) ε-diagnosability and uniform AA-diagnosability are undecidable while AA-diagnosability is decidable in PTIME, answering a longstanding open question.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Nathalie Bertrand Connect in order to contact the contributor
Submitted on : Monday, December 7, 2015 - 4:04:48 PM
Last modification on : Thursday, January 20, 2022 - 4:16:17 PM
Long-term archiving on: : Saturday, April 29, 2017 - 9:17:53 AM


Files produced by the author(s)




  • HAL Id : hal-01220954, version 2


Nathalie Bertrand, Serge Haddad, Engel Lefaucheux. Accurate approximate diagnosability of stochastic systems. 10th International Conference on Language and Automata Theory and Applications, Mar 2016, Prague, Czech Republic. ⟨hal-01220954v2⟩



Record views


Files downloads