Using Synchronizing Heuristics to Construct Homing Sequences
Berk Çirişci, M. Emek, Ege Sorguç, Kamer Kaya, Hüsnü Yenigün · 2019
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.