In a recent work, we introduced four variants of diagnosability#R##N#(FA, IA, FF, IF) in (finite) probabilistic#R##N#systems (pLTS) depending whether one considers (1) finite or#R##N#infinite runs and (2) faulty or all runs. We studied their#R##N#relationship and established that the corresponding decision#R##N#problems are PSPACE-complete. A key ingredient of the decision#R##N#procedures was a characterisation of diagnosability by the fact that#R##N#a random run almost surely lies in an open set whose specification#R##N#only depends on the qualitative behaviour of the pLTS. Here we#R##N#investigate similar issues for infinite pLTS. We first show that#R##N#this characterisation still holds for FF-diagnosability but#R##N#with a G-delta set instead of an open set and also for IF-#R##N#and IA-diagnosability when pLTS are finitely branching. We also#R##N#prove that surprisingly FA-diagnosability cannot be#R##N#characterised in this way even in the finitely branching case. Then#R##N#we apply our characterisations for a partially observable#R##N#probabilistic extension of visibly pushdown automata (POpVPA),#R##N#yielding EXPSPACE procedures for solving diagnosability problems.#R##N#In addition, we establish some computational lower bounds and show#R##N#that slight extensions of POpVPA lead to undecidability.
['Nathalie Bertrand', 'Serge Haddad', 'Engel Lefaucheux']
Diagnosis in Infinite-State Probabilistic Systems