Evaluating the length of distinguishing sequences for nondeterministic Input/Output automata
Igor Borisovich Burdonov, Alexandr Kossachev, Nina Vladimirovna Yevtushenko, Alexey Demakov · 2019
Distinguishing sequences are used in model based mutation testing in order to distinguish the specification from its mutants that usually represent critical implementation faults. In this paper, we consider distinguishing sequences for Input/Output automata when a sequence of inputs can be applied before getting any response or a sequence of output responses from an implementation under test. We propose a technique for deriving an r- distinguishing trace, i.e. a distinguishing trace with respect to the trace inclusion (quasi-reduction) relation, and obtain the least and upper bounds on the length of a shortest r- distinguishing trace showing that the exponential upper bound with respect to the number of states of the specification automaton is reachable; the results are then adapted for a proper case of Input/Output automata when each input is followed by an output, i.e., for Finite State Machines.