---
_id: '8912'
abstract:
- lang: eng
  text: "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."
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'
article_processing_charge: No
article_type: original
author:
- first_name: Naci E
  full_name: Sarac, Naci E
  id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
  last_name: Sarac
- first_name: Ömer Faruk
  full_name: Altun, Ömer Faruk
  last_name: Altun
- first_name: Kamil Tolga
  full_name: Atam, Kamil Tolga
  last_name: Atam
- first_name: Sertac
  full_name: Karahoda, Sertac
  last_name: Karahoda
- first_name: Kamer
  full_name: Kaya, Kamer
  last_name: Kaya
- first_name: Hüsnü
  full_name: Yenigün, Hüsnü
  last_name: Yenigün
citation:
  ama: Sarac NE, Altun ÖF, Atam KT, Karahoda S, Kaya K, Yenigün H. Boosting expensive
    synchronizing heuristics. <i>Expert Systems with Applications</i>. 2021;167(4).
    doi:<a href="https://doi.org/10.1016/j.eswa.2020.114203">10.1016/j.eswa.2020.114203</a>
  apa: Sarac, N. E., Altun, Ö. F., Atam, K. T., Karahoda, S., Kaya, K., &#38; Yenigün,
    H. (2021). Boosting expensive synchronizing heuristics. <i>Expert Systems with
    Applications</i>. Elsevier. <a href="https://doi.org/10.1016/j.eswa.2020.114203">https://doi.org/10.1016/j.eswa.2020.114203</a>
  chicago: Sarac, Naci E, Ömer Faruk Altun, Kamil Tolga Atam, Sertac Karahoda, Kamer
    Kaya, and Hüsnü Yenigün. “Boosting Expensive Synchronizing Heuristics.” <i>Expert
    Systems with Applications</i>. Elsevier, 2021. <a href="https://doi.org/10.1016/j.eswa.2020.114203">https://doi.org/10.1016/j.eswa.2020.114203</a>.
  ieee: N. E. Sarac, Ö. F. Altun, K. T. Atam, S. Karahoda, K. Kaya, and H. Yenigün,
    “Boosting expensive synchronizing heuristics,” <i>Expert Systems with Applications</i>,
    vol. 167, no. 4. Elsevier, 2021.
  ista: Sarac NE, Altun ÖF, Atam KT, Karahoda S, Kaya K, Yenigün H. 2021. Boosting
    expensive synchronizing heuristics. Expert Systems with Applications. 167(4),
    114203.
  mla: Sarac, Naci E., et al. “Boosting Expensive Synchronizing Heuristics.” <i>Expert
    Systems with Applications</i>, vol. 167, no. 4, 114203, Elsevier, 2021, doi:<a
    href="https://doi.org/10.1016/j.eswa.2020.114203">10.1016/j.eswa.2020.114203</a>.
  short: N.E. Sarac, Ö.F. Altun, K.T. Atam, S. Karahoda, K. Kaya, H. Yenigün, Expert
    Systems with Applications 167 (2021).
corr_author: '1'
date_created: 2020-12-02T13:34:25Z
date_published: 2021-04-01T00:00:00Z
date_updated: 2025-04-15T06:25:57Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1016/j.eswa.2020.114203
external_id:
  isi:
  - '000640531100038'
file:
- access_level: open_access
  checksum: 600c2f81bc898a725bcfa7cf26ff4fed
  content_type: application/pdf
  creator: esarac
  date_created: 2020-12-02T13:33:51Z
  date_updated: 2020-12-02T13:33:51Z
  file_id: '8913'
  file_name: synchroPaperRevised.pdf
  file_size: 634967
  relation: main_file
file_date_updated: 2020-12-02T13:33:51Z
has_accepted_license: '1'
intvolume: '       167'
isi: 1
issue: '4'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Submitted Version
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: Formal methods for the design and analysis of complex systems
publication: Expert Systems with Applications
publication_identifier:
  issn:
  - '09574174'
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Boosting expensive synchronizing heuristics
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 167
year: '2021'
...