Synchronizing billion-scale automata
| Autor: | Hüsnü Yenigün, Mustafa Kemal Taş, Kamer Kaya |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Sequence
Information Systems and Management Computer science Heuristic 05 social sciences Process (computing) 050301 education Synchronizing Scale (descriptive set theory) 02 engineering and technology Parallel computing Computer Science Applications Theoretical Computer Science Automaton Artificial Intelligence Control and Systems Engineering 0202 electrical engineering electronic engineering information engineering Overhead (computing) 020201 artificial intelligence & image processing Heuristics 0503 education Software |
| Zdroj: | Information Sciences. 574:162-175 |
| ISSN: | 0020-0255 |
| Popis: | 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 = 10 8 states in 12.1 s, n = 5 × 10 8 states in 69.1 s, and billion states in 148.2 s. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect