%0 Conference Proceedings
%F bertrand:hal-01220954
%A Bertrand, N.
%A Haddad, S.
%A Lefaucheux, E.
%T Accurate approximate diagnosability of stochastic systems
%B 10th International Conference on Language and Automata Theory and Applications
%I Springer
%C Prague, Czech Republic
%X 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 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. 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 decidability status of the diagnosability problems: (uniform) epsilon-diagnosability and uniform AA-diagnosability are undecidable while AA-diagnosability is decidable in PTIME, answering a longstanding open question
%U http://www.irisa.fr/sumo/Publis/PDF/AA-main.pdf
%8 March
%D 2016