License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.417
URN: urn:nbn:de:0030-drops-48605
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4860/
Go to the corresponding LIPIcs Volume Portal

Bertrand, Nathalie ; Haddad, Serge ; Lefaucheux, Engel

Foundation of Diagnosis and Predictability in Probabilistic Systems

pdf-format:
36.pdf (0.5 MB)

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 diagnosis for 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.

BibTeX - Entry

@InProceedings{bertrand_et_al:LIPIcs:2014:4860,
  author =	{Nathalie Bertrand and Serge Haddad and Engel Lefaucheux},
  title =	{{Foundation of Diagnosis and Predictability in Probabilistic Systems}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{417--429},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4860},
  URN =		{urn:nbn:de:0030-drops-48605},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.417},
  annote =	{Keywords: Partially observed systems, Diagnosis, Markov chains}
}

Keywords: Partially observed systems, Diagnosis, Markov chains
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI