Boosting expensive synchronizing heuristics

N.E. Sarac, Ö.F. Altun, K.T. Atam, S. Karahoda, K. Kaya, H. Yenigün, Expert Systems with Applications (n.d.).

Download
OA synchroPaperRevised.pdf 634.97 KB

Journal Article | In Press | English

Scopus indexed
Author
Saraç, N. EgeIST Austria; Altun, Ömer Faruk; Atam, Kamil Tolga; Karahoda, Sertac; Kaya, Kamer; Yenigün, Hüsnü
Department
Abstract
For automata, synchronization, the problem of bringing an automaton to a particular state regardless of its initial state, is important. It has several applications in practice and is related to a fifty-year-old conjecture on the length of the shortest synchronizing word. Although using shorter words increases the effectiveness in practice, finding a shortest one (which is not necessarily unique) is NP-hard. For this reason, there exist various heuristics in the literature. However, high-quality heuristics such as SynchroP producing relatively shorter sequences are very expensive and can take hours when the automaton has tens of thousands of states. The SynchroP heuristic has been frequently used as a benchmark to evaluate the performance of the new heuristics. In this work, we first improve the runtime of SynchroP and its variants by using algorithmic techniques. We then focus on adapting SynchroP for many-core architectures, and overall, we obtain more than 1000× speedup on GPUs compared to naive sequential implementation that has been frequently used as a benchmark to evaluate new heuristics in the literature. We also propose two SynchroP variants and evaluate their performance.
Publishing Year
Date Published
2020-11-17
Journal Title
Expert Systems with Applications
Acknowledgement
This work was supported by The Scientific and Technological Research Council of Turkey (TUBITAK) [grant number 114E569]. This research was supported in part by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award). We would like to thank the authors of (Roman & Szykula, 2015) for providing their heuristics implementations, which we used to compare our SynchroP implementation as given in Table 11.
Article Number
114203
ISSN
IST-REx-ID

Cite this

Sarac NE, Altun ÖF, Atam KT, Karahoda S, Kaya K, Yenigün H. Boosting expensive synchronizing heuristics. Expert Systems with Applications. doi:10.1016/j.eswa.2020.114203
Sarac, N. E., Altun, Ö. F., Atam, K. T., Karahoda, S., Kaya, K., & Yenigün, H. (n.d.). Boosting expensive synchronizing heuristics. Expert Systems with Applications. Elsevier. https://doi.org/10.1016/j.eswa.2020.114203
Sarac, Naci E, Ömer Faruk Altun, Kamil Tolga Atam, Sertac Karahoda, Kamer Kaya, and Hüsnü Yenigün. “Boosting Expensive Synchronizing Heuristics.” Expert Systems with Applications. Elsevier, n.d. https://doi.org/10.1016/j.eswa.2020.114203.
N. E. Sarac, Ö. F. Altun, K. T. Atam, S. Karahoda, K. Kaya, and H. Yenigün, “Boosting expensive synchronizing heuristics,” Expert Systems with Applications. Elsevier.
Sarac NE, Altun ÖF, Atam KT, Karahoda S, Kaya K, Yenigün H. Boosting expensive synchronizing heuristics. Expert Systems with Applications., 114203.
Sarac, Naci E., et al. “Boosting Expensive Synchronizing Heuristics.” Expert Systems with Applications, 114203, Elsevier, doi:10.1016/j.eswa.2020.114203.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2020-12-02
MD5 Checksum
600c2f81bc898a725bcfa7cf26ff4fed


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar