Minimizing the cost of fault location when testing from a finite state machine

Abstract

If a test does not produce the expected output, the incorrect output may have been caused by an earlier state transfer failure. Ghedamsi and coworkers generate a set of candidates and then produce further tests to locate the failures within this set. We consider a special case where there is a state identification process that is known to be correct. A number of preset and adaptive approaches to fault location are described and the problem of minimizing the cost is explored. Some of the approaches lead to NP-hard optimization problems for which possible heuristics are suggested.