Hardness and inapproximability of minimizing adaptive distinguishing sequences

An adaptive distinguishing sequence (ADS) can be used for identifying an unknown initial state of a finite state machine (FSM). It has been long known that checking the existence of an ADS for an FSM, and finding an ADS for an FSM when one exists, can be performed in polynomial time. However, the problem of finding a minimum ADS has not been studied so far. Generating a minimum ADS is especially motivated when such an ADS is used repeatedly, e.g. for the construction of a test sequence. We introduce a number of metrics to define a minimum ADS and show that the problem of generating a minimum ADS with respect to these metrics is NP-complete. In addition, we provide inapproximability results for these hard problems and show that not only deciding but also approximating such a minimum ADS is a hard problem. We modify the only polynomial time ADS generation algorithm existing, and experimentally show that these modifications construct reduced ADSs. We also validate the motivation of ADS minimization by presenting experimental results on the effect of using reduced ADSs to generate test sequences.