Using Synchronizing Heuristics to Construct Homing Sequences
Autor: | Hüsnü Yenigün, Kamer Kaya, Berk Çirişci, M. Yuşa Emek, Ege Sorguç |
---|---|
Přispěvatelé: | Hammoudi, S., Selic, B., Pires, L. F. |
Rok vydání: | 2019 |
Předmět: |
QA075 Electronic computers. Computer science
Theoretical computer science Computer science Homing (biology) Synchronizing 0102 computer and information sciences 02 engineering and technology 01 natural sciences Automaton 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Heuristics Computer Science::Formal Languages and Automata Theory |
Zdroj: | MODELSWARD |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |