Selected publications at LSV

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. Furthermore, focusing on the minimal delay before detection, we establish that the memory required for any active diagnoser achieving this delay may be highly greater than the previous one. So we refine our construction to build with the same complexity and memory requirement an active diagnoser that realizes a delay bounded by twice the minimal delay.

@inproceedings{HHMS-fsttcs13,
   address = {Guwahati, India},
   author = {Haar, Stefan and Haddad, Serge and Melliti, Tarek and Schwoon, Stefan},
   booktitle = {{P}roceedings of the 33rd {C}onference on {F}oundations of {S}oftware {T}echnology and {T}heoretical {C}omputer {S}cience ({FSTTCS}'13)},
   DOI = {10.4230/LIPIcs.FSTTCS.2013.527},
   editor = {Seth, Anil and Vishnoi, Nisheeth},
   month = dec,
   pages = {527-539},
   publisher = {Leibniz-Zentrum f{\"u}r Informatik},
   series = {Leibniz International Proceedings in Informatics},
   title = {Optimal Constructions for Active Diagnosis},
   url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/HHMS13-fsttcs.pdf},
   volume = {24},
   year = {2013},
}

About LSV