Synchronizing heuristics for weakly connected automata with various topologies

Çirişci, Berk and Sevilmiş, Barış and Sivri, Emre Yasin and Karaçam, Poyraz Kıvanç and Kaya, Kamer and Yenigün, Hüsnü (2019) Synchronizing heuristics for weakly connected automata with various topologies. In: 6th International Conference on Model-Driven Engineering and Software Development (MODELSWARD 2018), Funchal, Madeira, Portugal

[thumbnail of MODELSWARD.pdf] PDF

Download (1MB)


Since the problem of finding a shortest synchronizing sequence for an automaton is known to be NP-hard, heuristics algorithms are used to find synchronizing sequences. There are several heuristic algorithms in the literature for this purpose. However, even the most efficient heuristic algorithm in the literature has a quadratic complexity in terms of the number of states of the automaton, and therefore can only scale up to a couple of thousands of states. It was also shown before that if an automaton is not strongly connected, then these heuristic algorithms can be used on each strongly connected component separately. This approach speeds up these heuristic algorithms and allows them to scale to much larger number of states easily. In this paper, we investigate the effect of the topology of the automaton on the performance increase obtained by these heuristic algorithms. To this end, we consider various topologies and provide an extensive experimental study on the performance increase obtained on the existing heuristic algorithms. Depending on the size and the number of components, we obtain speed-up values as high as 10000x and more.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Finite state automata; Strongly connected component; Synchronizing sequences
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: Kamer Kaya
Date Deposited: 28 Aug 2019 09:49
Last Modified: 10 Jun 2023 15:49

Actions (login required)

View Item
View Item