[Back]

A. Pfandler, R. Pichler, S. Woltran:
"Decentralized Diagnosis: Complexity Analysis and Datalog Encodings";
Poster: Junior Scientist Conference 2010, Vienna; 04-07-2010 - 04-09-2010; in: "Proceedings of the Junior Scientist Conference 2010", H. Kaiser, R. Kirner (ed.); (2010), ISBN: 978-3-200-01797-9; 291 - 292.

Diagnosis is an important field of Artificial Intelligence. Recently, Console et al. proposed a framework for decentralized qualitative model-based diagnosis. The basic idea is to decompose a complex system into subsystems, each of which gets a local diagnoser assigned. The global diagnosis is computed by "asking" the local diagnosers, while some information may remain private. A detailed complexity analysis and an implementation are missing. Therefore, we introduce extended definitions, define related problems and analyze their complexity. For each problem an upper bound is determined. If
we allow slight modifications we can prove the completeness in two cases. Using these theoretical results, we propose datalog encodings that match the complexity. Finally, these encodings are evaluated using the datalog system DLV.