The relation between preset distinguishing sequences and synchronizing sequences

Abstract

Abstract We study the relation between synchronizing sequences and preset distinguishing sequences which are some special sequences used in finite state machine based testing. We show that the problems related to preset distinguishing sequences can be converted into related problems of synchronizing sequences. Using the results existing in the literature for synchronizing sequences, we offer several reflections of these results for preset distinguishing sequences. Although computing a preset distinguishing sequence is PSPACE-hard , we do identify a class of machines for which computing a preset distinguishing sequence can be performed in polynomial time and argue that this class is practically relevant. We also present an experimental study to compare the performance of exponential brute-force and polynomial heuristic algorithms to compute a preset distinguishing sequence.