Diagnosing Circuits With State: An Inherently Underconstrained Problem

Walter Hamscher, Randall Davis

"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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.