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], 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.
Type de document :
Communication dans un congrès
10th International Conference on Language and Automata Theory and Applications, Mar 2016, Prague, Czech Republic. Springer, 〈http://grammars.grlmc.com/lata2016/index.php〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01220954
Contributeur : Nathalie Bertrand <>
Soumis le : lundi 7 décembre 2015 - 16:04:48
Dernière modification le : mercredi 11 avril 2018 - 01:50:59
Document(s) archivé(s) le : samedi 29 avril 2017 - 09:17:53

Fichier

AA-main.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

  • 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. Springer, 〈http://grammars.grlmc.com/lata2016/index.php〉. 〈hal-01220954v2〉

Partager

Métriques

Consultations de la notice

689

Téléchargements de fichiers

100