Using synchronizing heuristics to construct homing sequences

Çirişci, Berk and Emek, M. Yuşa and Sorguç, Ege and Kaya, Kamer and Yenigün, Hüsnü (2019) Using synchronizing heuristics to construct homing sequences. In: 7th International Conference on Model-Driven Engineering and Software Development (MODELSWARD 2019), Prague, Czech Republic

[thumbnail of 64-MODELSWARD_2019_44.pdf] PDF
64-MODELSWARD_2019_44.pdf

Download (327kB)

Abstract

Computing a shortest synchronizing sequence of an automaton is an NP-Hard problem. There are well-known heuristics to find short synchronizing sequences. Finding a shortest homing sequence is also an NP-Hard problem. Unlike existing heuristics to find synchronizing sequences, homing heuristics are not widely studied. In this paper, we discover a relation between synchronizing and homing sequences by creating an automaton called homing automaton. By applying synchronizing heuristics on this automaton we get short homing sequences. Furthermore, we adapt some of the synchronizing heuristics to construct homing sequences.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Finite State Machines; Homing Sequences; Synchronizing Sequences
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
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 Aug 2019 10:12
Last Modified: 07 Feb 2024 14:34
URI: https://research.sabanciuniv.edu/id/eprint/37817

Actions (login required)

View Item
View Item