Foundation of Diagnosis and Predictability in Probabilistic Systems

Nathalie Bertrand 1 Serge Haddad 2, 3 Engel Lefaucheux 1, 3, 2
1 SUMO - SUpervision of large MOdular and distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
2 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
3 LSV - Laboratoire Spécification et Vérification [Cachan]
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.
Type de document :
Communication dans un congrès
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'14), Dec 2014, New Delhi, India. 29, pp.417-429, LIPIcs
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01088117
Contributeur : Nathalie Bertrand <>
Soumis le : jeudi 27 novembre 2014 - 14:19:07
Dernière modification le : jeudi 7 février 2019 - 16:53:16
Document(s) archivé(s) le : lundi 2 mars 2015 - 09:24:10

Fichier

paper-90.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01088117, version 1

Collections

INRIA | IRISA | UNIV-RENNES1 | IRISA-D4 | ENS-CACHAN | INSTITUT-TELECOM | UR1-UFR-ISTIC | UNIV-RENNES

Citation

Nathalie Bertrand, Serge Haddad, Engel Lefaucheux. Foundation of Diagnosis and Predictability in Probabilistic Systems. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'14), Dec 2014, New Delhi, India. 29, pp.417-429, LIPIcs. 〈hal-01088117〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

339

Téléchargements de fichiers

163

Contact


archive-ouverte@inria.fr