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
IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL, Inria Rennes – Bretagne Atlantique
3 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
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.
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01220954
Contributor : Nathalie Bertrand <>
Submitted on : Monday, December 7, 2015 - 4:04:48 PM
Last modification on : Thursday, February 7, 2019 - 2:59:52 PM
Document(s) archivé(s) le : Saturday, April 29, 2017 - 9:17:53 AM

File

AA-main.pdf
Files produced by the author(s)

Licence


Copyright

Identifiers

  • HAL Id : hal-01220954, version 2

Citation

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⟩

Share

Metrics

Record views

959

Files downloads

227