Diagnosis in Infinite-State Probabilistic Systems (long version) - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2016

Diagnosis in Infinite-State Probabilistic Systems (long version)

Résumé

In a recent work, we introduced four variants of diagnosability (FA, IA, FF, IF) in (finite) probabil-istic systems (pLTS) depending whether one considers (1) finite or infinite runs and (2) faulty or all runs. We studied their relationship and established that the corresponding decision problems are PSPACE-complete. A key ingredient of the decision procedures was a characterisation of diagnosability by the fact that a random run almost surely lies in an open set whose specification only depends on the qualitative behaviour of the pLTS. Here we investigate similar issues for infinite pLTS. We first show that this characterisation still holds for FF-diagnosability but with a G δ set instead of an open set and also for IF-and IA-diagnosability when pLTS are finitely branching. We also prove that surprisingly FA-diagnosability cannot be characterised in this way even in the finitely branching case. Then we apply our characterisations for a partially observable probabilistic extension of visibly pushdown automata (POpVPA), yielding EXPSPACE procedures for solving diagnosability problems. In addition, we establish some computational lower bounds and show that slight extensions of POpVPA lead to undecidability.
Fichier principal
Vignette du fichier
main.pdf (725.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01334218 , version 1 (20-06-2016)

Identifiants

  • HAL Id : hal-01334218 , version 1

Citer

Nathalie Bertrand, Serge Haddad, Engel Lefaucheux. Diagnosis in Infinite-State Probabilistic Systems (long version). [Research Report] Inria Rennes; LSV, ENS Cachan. 2016. ⟨hal-01334218⟩
295 Consultations
92 Téléchargements

Partager

Gmail Facebook X LinkedIn More