2026-08-25T22:09:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27367 2026-08-24T14:08:31Z ddc:004 open_access

Active Diagnosis with Costs and Rewards Haddad, Serge Lefaucheux, Engel Schwoon, Stefan Partial observation diagnosis game and automata theory controller synthesis probabilistic discrete event systems Diagnosis is the task of detecting fault occurrences in a partially observed system. Depending on the possible observations, a discrete-event system may be diagnosable or not. Active diagnosis aims at controlling the system to render it diagnosable. In the past, the main analyzed criterion of the quality of an active diagnoser has been the delay between the fault occurrence and its detection. Here we generalize this study by (1) associating costs or rewards with faulty runs, (2) defining three related decision problems, and (3) analyzing their decidability/complexity in the non-deterministic and probabilistic frameworks under several hypotheses. We study non-deterministic and probabilistic semantics and compare their decidability and complexity. In particular, we exhibit one problem decidable for non-deterministic systems but undecidable for probabilistic ones. Furthermore we establish tight lower and upper bounds for the size of the active diagnoser (when it exists). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Serge Haddad and Engel Lefaucheux and Stefan Schwoon 2026 Is Part Of LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2026.37 urn:nbn:de:0030-drops-273674 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.37 eng https://creativecommons.org/licenses/by/4.0/legalcode