-
Selection by year
-
Selection by authors
-
Complete lists
FSTTCS14
N. Bertrand, S. Haddad, E. Lefaucheux. Foundation of Diagnosis and Predictability in Probabilistic Systems. In FSTTCS'14, New Delhi, India, December 2014.
Download [help]
Download paper:
Adobe portable document (pdf) 
Copyright notice:
This material is presented to ensure timely dissemination of scholarly and
technical work. Copyright and all rights therein are retained by authors or
by other copyright holders. All persons copying this information are expected
to adhere to the terms and constraints invoked by each author's
copyright. These works may not be reposted without the explicit permission of
the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic
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 diagnosisfor probabilistic systems modelled by partially observed Markov chains also called probabilistic labeled transition systems (pLTS). First we study different specifications 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
Contact
Nathalie Bertrand http://www.irisa.fr/prive/nbertran/
BibTex Reference
@InProceedings{FSTTCS14,
Author = {Bertrand, N. and Haddad, S. and Lefaucheux, E.},
Title = {Foundation of Diagnosis and Predictability in Probabilistic Systems},
BookTitle = {FSTTCS'14},
Address = {New Delhi, India},
Month = {December},
Year = {2014}
}
EndNote Reference [help]
Get EndNote Reference (.ref)