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.

Item Type:Article
Uncontrolled Keywords:Finite state machines; Preset distinguishing sequence; Synchronizing sequences
Subjects:Q Science > QA Mathematics > QA076 Computer software
ID Code:24482
Deposited By:Hüsnü Yenigün
Deposited On:28 Nov 2014 22:16
Last Modified:02 Aug 2019 10:32

Repository Staff Only: item control page