License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.85
URN: urn:nbn:de:0030-drops-170237
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17023/
Szykuła, Marek ;
Zyzik, Adam
An Improved Algorithm for Finding the Shortest Synchronizing Words
Abstract
A synchronizing word of a deterministic finite complete automaton is a word whose action maps every state to a single one. Finding a shortest or a short synchronizing word is a central computational problem in the theory of synchronizing automata and is applied in other areas such as model-based testing and the theory of codes. Because the problem of finding a shortest synchronizing word is computationally hard, among exact algorithms only exponential ones are known. We redesign the previously fastest known exact algorithm based on the bidirectional breadth-first search and improve it with respect to time and space in a practical sense. We develop new algorithmic enhancements and adapt the algorithm to multithreaded and GPU computing. Our experiments show that the new algorithm is multiple times faster than the previously fastest one and its advantage quickly grows with the hardness of the problem instance. Given a modest time limit, we compute the lengths of the shortest synchronizing words for random binary automata up to 570 states, significantly beating the previous record. We refine the experimental estimation of the average reset threshold of these automata. Finally, we develop a general computational package devoted to the problem, where an efficient and practical implementation of our algorithm is included, together with several well-known heuristics.
BibTeX - Entry
@InProceedings{szykula_et_al:LIPIcs.ESA.2022.85,
author = {Szyku{\l}a, Marek and Zyzik, Adam},
title = {{An Improved Algorithm for Finding the Shortest Synchronizing Words}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {85:1--85:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17023},
URN = {urn:nbn:de:0030-drops-170237},
doi = {10.4230/LIPIcs.ESA.2022.85},
annote = {Keywords: \v{C}ern\{\'{y}\} conjecture, reset threshold, reset word, subset checking, synchronizing automaton, synchronizing word}
}
