1 Search Results for "Zyzik, Adam"

Document
DOI: 10.4230/LIPIcs.ESA.2022.85
An Improved Algorithm for Finding the Shortest Synchronizing Words

Authors: Marek Szykuła and Adam Zyzik

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

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.
Cite as

Marek Szykuła and Adam Zyzik. An Improved Algorithm for Finding the Shortest Synchronizing Words. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 85:1-85:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.85},
  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}
}
  • Refine by Author
  • 1 Szykuła, Marek
  • 1 Zyzik, Adam

  • Refine by Classification
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 1 reset threshold
  • 1 reset word
  • 1 subset checking
  • 1 synchronizing automaton
  • 1 synchronizing word
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact