Exact and Approximate Diagnosis of
                   Probabilistic Systems


                                                    Serge H ADDAD
                                               LSV, ENS Cachan, France
                                               haddad@lsv.ens-cachan.fr



   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 specifi ed in di fferent ways: (1) exact diagnosability
   (called A-diagnosability) requires that almost surely a fault is detected and that no fault is erroneously
   claimed while (2) approximate diagnosability (called epsilon-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. In this talk, I will cover three aspects of diagnosis. First,
   I solve semantical issues like the (non) equivalence of different notions. Then I study algorithmic issues
   establishing in most of the cases, the decidability status and the complexity class of the diagnosability
   problem. Finally, I explain how to synthetize a diagnoser when the system is diagnosable.




c The Authors. Published by BISL.                          1
Proceedings of VECoS