The relation between preset distinguishing sequences and synchronizing sequences
Güniçen, Canan and İnan, Kemal and Türker, Uraz Cengiz and Yenigün, Hüsnü (2014) The relation between preset distinguishing sequences and synchronizing sequences. Formal Aspects of Computing, 26 (6). pp. 1153-1167. ISSN 0934-5043 (Print) 1433-299X (Online)
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s00165-014-0297-8
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.
Repository Staff Only: item control page