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
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.
Repository Staff Only: item control page