2026-07-23T16:35:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4398 2024-03-06T10:35:01Z ddc:004 open_access

Optimal Constructions for Active Diagnosis Haar, Stefan Haddad, Serge Melliti, Tarek Schwoon, Stefan Diagnosis Control theory Automata theory Games. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Haar and Serge Haddad and Tarek Melliti and Stefan Schwoon 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.527 urn:nbn:de:0030-drops-43981 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.527 eng https://creativecommons.org/licenses/by/3.0/legalcode