ECAI-2000 Logo

ECAI-2000 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Differentiating Diagnostic Theories through Constraints over an Eight-valued Logic

Francisco Azevedo, Pedro Barahona

In this paper we address the issue of diagnosing propositional theories where only some components are observable. More specifically, the goal is to find tests that allow the differentiation of two alternative theories. This subject is addressed in the context of differential diagnosis of faulty gates in a VLSI circuit where the only observable findings are its input/output bits, but may be extended to other areas, namely in diagnosing a theory of an agent where knowledge about it is based on its response to external stimuli. To model these problems we developed an eight-valued logic that describes the dependency of the findings on the competing theories. Additionally, we implemented a constraint solver to handle this eight-valued logic domain, and to solve efficiently the problem of obtaining differentiating tests that allow the elimination of one of the alternative theories. We discuss the limitations of the currently more advanced techniques to handle disjunctive constraints, and propose a new method, iterative time-bounded search (ITBS) to overcome them. The method is exemplified and tested in the problem of generating differential test patterns for digital circuits.

Keywords: Constraint-Based Reasoning, Diagnosis, Constraint Satisfaction, Constraint Programming, Search

Citation: Francisco Azevedo, Pedro Barahona: Differentiating Diagnostic Theories through Constraints over an Eight-valued Logic. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.73-77.

[prev] [tofc] [next]

ECAI-2000 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Humboldt University on behalf of Gesellschaft für Informatik.