Diagnosing Circuits With State: An Inherently Underconstrained Problem

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 4

Automated Reasoning

Hard problems can be hard because they are computationally intractable, or because they are underconstrained. Here we describe candidate generation for digital devices with state, a fault localization problem that is intractable when the devices are described at low levels of abstraction, and is underconstrained when described at higher levels of abstraction. Previous work [l] has shown that a fault in a combinatorial digital circuit can be localized using a constraint-based representation of structure and behavior. ln this paper we (1) extend this representation to model a circuit with state by choosing a time granularity and vocabulary of signals appropriate to that circuit; (2) demonstrate that the same candidate generation procedure that works for combinatorial circuits becomes indiscriminate when applied to a state circuit modeled in that extended representation;(3) show how the common technique of single-stepping can be viewed as a divide-and-conquer approach to overcoming that lack of constraint; and (4) illustrate how using structural detail can help to make the candidate generator discriminating once again, but only at great cost.