Using structure of automata for faster synchronizing heuristics

Çirişci, Berk and Kahraman, Muhammed Kerem and Yıldırımoğlu, Çağrı Uluç and Kaya, Kamer and Yenigün, Hüsnü (2018) Using structure of automata for faster synchronizing heuristics. In: 6th International Conference on Model-Driven Engineering and Software Development (MODELSWARD 2018), Funchal, Madeira, Portugal

[thumbnail of Paper] PDF (Paper)
Restricted to Repository staff only

Download (911kB) | Request a copy


The problem of finding a synchronizing sequence for an automaton is an interesting problem studied widely in the literature. Finding a shortest synchronizing sequence is an NP-Hard problem. Therefore, there are heuristics to find short synchronizing sequences. Some heuristics work fast but produce long synchronizing sequences, whereas some heuristics work slow but produce relatively shorter synchronizing sequences. In this paper we propose a method for using these heuristics by considering the connectedness of automata. Applying the proposed approach of using these heuristics make the heuristics work faster than their original versions, without sacrificing the quality of the synchronizing sequences.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Finite State Automata, Synchronizing Sequences, Strongly Connected Component
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: 13 Aug 2018 14:35
Last Modified: 31 Jul 2023 15:47

Actions (login required)

View Item
View Item