The relation between preset distinguishing sequences and synchronizing sequences

Warning The system is temporarily closed to updates for reporting purpose.

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. (Request a copy)

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.
Item Type: Article
Uncontrolled Keywords: Finite state machines; Preset distinguishing sequence; Synchronizing sequences
Subjects: Q Science > QA Mathematics > QA076 Computer software
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Hüsnü Yenigün
Date Deposited: 28 Nov 2014 22:16
Last Modified: 02 Aug 2019 10:32
URI: https://research.sabanciuniv.edu/id/eprint/24482

Actions (login required)

View Item
View Item