--- res: bibo_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,\r\nand 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.@eng" bibo_authorlist: - foaf_Person: foaf_givenName: Naci E foaf_name: Sarac, Naci E foaf_surname: Sarac foaf_workInfoHomepage: http://www.librecat.org/personId=8C6B42F8-C8E6-11E9-A03A-F2DCE5697425 - foaf_Person: foaf_givenName: Ömer Faruk foaf_name: Altun, Ömer Faruk foaf_surname: Altun - foaf_Person: foaf_givenName: Kamil Tolga foaf_name: Atam, Kamil Tolga foaf_surname: Atam - foaf_Person: foaf_givenName: Sertac foaf_name: Karahoda, Sertac foaf_surname: Karahoda - foaf_Person: foaf_givenName: Kamer foaf_name: Kaya, Kamer foaf_surname: Kaya - foaf_Person: foaf_givenName: Hüsnü foaf_name: Yenigün, Hüsnü foaf_surname: Yenigün bibo_doi: 10.1016/j.eswa.2020.114203 bibo_issue: '4' bibo_volume: 167 dct_date: 2021^xs_gYear dct_identifier: - UT:000640531100038 dct_isPartOf: - http://id.crossref.org/issn/09574174 dct_language: eng dct_publisher: Elsevier@ dct_title: Boosting expensive synchronizing heuristics@ ...