Synchronizing billion-scale automata

Taş, Mustafa Kemal and Kaya, Kamer and Yenigün, Hüsnü (2021) Synchronizing billion-scale automata. Information Sciences, 574 . pp. 162-175. ISSN 0020-0255 (Print) 1872-6291 (Online)

Full text not available from this repository. (Request a copy)


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.
Item Type: Article
Uncontrolled Keywords: Finite state automata; GPUs; Multi-core CPUs; Synchronization heuristics; Synchronizing sequences
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 01 Sep 2022 20:44
Last Modified: 01 Sep 2022 20:44

Actions (login required)

View Item
View Item