Synchronizing heuristics for weakly connected automata with various topologies

Official URL: http://dx.doi.org/10.1007/978-3-030-11030-7_21

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.