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

[img]PDF (Paper ) - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.5220/0006660805440551


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
ID Code:34938
Deposited By:Hüsnü Yenigün
Deposited On:13 Aug 2018 14:35
Last Modified:13 Aug 2018 14:35

Repository Staff Only: item control page