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.2013.527
URN: urn:nbn:de:0030-drops-43981
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4398/
Go to the corresponding LIPIcs Volume Portal

Haar, Stefan ; Haddad, Serge ; Melliti, Tarek ; Schwoon, Stefan

Optimal Constructions for Active Diagnosis

pdf-format:
40.pdf (0.5 MB)

Abstract

The task of diagnosis consists in detecting, without ambiguity, occurrence of faults in a partially observed system. Depending on the degree of observability, a discrete event system may be
diagnosable or not. Active diagnosis aims at controlling the system in order to make it diagnosable. Solutions have already been proposed for the active diagnosis problem, but their complexity remains to be improved. We solve here the active diagnosability decision problem
and the active diagnoser synthesis problem, proving that (1) our
procedures are optimal w.r.t. to computational complexity, and (2) the memory required for the active diagnoser produced by the synthesis is minimal. We then focus on the delay between the occurrence of a fault and its detection by the diagnoser. We construct a memory-optimal diagnoser whose delay is at most twice the minimal delay, whereas the memory required for a diagnoser with optimal delay may be highly greater.

BibTeX - Entry

@InProceedings{haar_et_al:LIPIcs:2013:4398,
  author =	{Stefan Haar and Serge Haddad and Tarek Melliti and Stefan Schwoon},
  title =	{{Optimal Constructions for Active Diagnosis}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{527--539},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4398},
  URN =		{urn:nbn:de:0030-drops-43981},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.527},
  annote =	{Keywords: Diagnosis, Control theory, Automata theory, Games.}
}

Keywords: Diagnosis, Control theory, Automata theory, Games.
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

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