1 Search Results for "Melliti, Tarek"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.527
Optimal Constructions for Active Diagnosis

Authors: Stefan Haar, Serge Haddad, Tarek Melliti, and Stefan Schwoon

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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.
Cite as

Stefan Haar, Serge Haddad, Tarek Melliti, and Stefan Schwoon. Optimal Constructions for Active Diagnosis. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 527-539, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{haar_et_al:LIPIcs.FSTTCS.2013.527,
  author =	{Haar, Stefan and Haddad, Serge and Melliti, Tarek and Schwoon, Stefan},
  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 =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.527},
  URN =		{urn:nbn:de:0030-drops-43981},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.527},
  annote =	{Keywords: Diagnosis, Control theory, Automata theory, Games.}
}
  • Refine by Author
  • 1 Haar, Stefan
  • 1 Haddad, Serge
  • 1 Melliti, Tarek
  • 1 Schwoon, Stefan

  • Refine by Classification

  • Refine by Keyword
  • 1 Automata theory
  • 1 Control theory
  • 1 Diagnosis
  • 1 Games.

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2013

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact