Effective algorithms for constructing minimum cost adaptive distinguishing sequences

Context: Given a Finite State Machine (FSM), a checking sequence is a test sequence that determines whether the system under test is correct as long as certain standard assumptions hold. Many checking sequence generation methods use an adaptive distinguishing sequence (ADS), which is an experiment that distinguishes the states of the specification machine. Furthermore, it has been shown that the use of shorter ADSs yields shorter checking sequences. It is also known, on the other hand, that constructing a minimum cost ADS is an NP-hard problem and it is NP-hard to approximate. This motivates studying and investigating effective ADS construction methods.