Synchronizing billion-scale automata

Official URL: https://dx.doi.org/10.1016/j.ins.2021.05.072

Synchronizing sequences for large-scale automata have gained popularity recently due to their practical use cases especially to have a faster and better testing process. In many applications, shorter sequences imply less overhead and faster processing time but the problem of finding the shortest synchronizing sequence is NP-hard and requires heuristic approaches to be solved. State-of-the-art heuristics manage to obtain desirable, short sequences with relatively small execution times. However, all these heuristics suffer their quadratic memory complexity and fail to scale when the input automaton gets larger. In this paper, we propose an approach exploiting GPUs and hybrid parallelism which can generate synchronizing sequences even for billion-scale automata, in a short amount of time. Overall, the algorithm can generate a synchronizing sequence for a random automaton with n=108 states in 12.1 s, n=5×108 states in 69.1 s, and billion states in 148.2 s.