Approximation of Reset Thresholds with Greedy Algorithms

• Autorzy: Ananichev D. S. , Gusev V. V.

Identyfikatory

DOI

10.3233/FI-2016-1357

• Języki publikacji: EN

Abstrakty

EN

The problem of approximate computation of reset thresholds of synchronizing automata has gained a lot of attention recently. We introduce a broad class of algorithms that compute reset words and analyze their approximation ratios. We present three series of automata that reveal inherent limitations of greedy strategies for approximation of reset thresholds.

Słowa kluczowe

EN

approximation algorithm; greedy algorithm; inapproximability; reset threshold; synchronizing automata; synchronizing word

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 3
• Strony: 221--227
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Ananichev D. S.

• Institute of Mathematics and Computer Science, Ural Federal University, Lenina 51, Ekaterinburg, Russia

autor

Gusev V. V.

• Institute of Mathematics and Computer Science, Ural Federal University Ekaterinburg, Russia

Bibliografia

• [1] Volkov MV. Synchronizing Automata and the Černý Conjecture. In: Martín-Vide C, Otto F, Fernau H, editors. Language and Automata Theory and Applications. vol. 5196 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2008. p. 11–27. doi:10.1007/978-3-540-88282-4 4.
• [2] Eppstein D. Reset sequences for monotonic automata. SIAM J Computing. 1990 June;19(3):500–510. doi:10.1137/0219033.
• [3] Olschewski J, Ummels M. The Complexity of Finding Reset Words in Finite Automata. In: Hlinĕný P, Kučera A, editors. Mathematical Foundations of Computer Science 2010. vol. 6281 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2010. p. 568–579. doi:10.1007/978-3-642-15155-2 50.
• [4] Berlinkov MV. Approximating the Minimum Length of Synchronizing Words Is Hard. Theory of Computing Systems. 2014;54(2):211–223. doi:10.1007/s00224-013-9511-y.
• [5] Gerbush M, Heeringa B. Approximating Minimum Reset Sequences. In: Domaratzki M, Salomaa K, editors. Implementation and Application of Automata. vol. 6482 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2011. p. 154–162. doi:10.1007/978-3-642-18098-9 17.
• [6] Berlinkov MV. On Two Algorithmic Problems about Synchronizing Automata. In: Shur AM, Volkov MV, editors. Developments in Language Theory. vol. 8633 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2014. p. 68–75. doi:10.1007/978-3-319-09698-8 6.
• [7] Gawrychowski P, Straszak D. Strong Inapproximability of the Shortest Reset Word. In: Italiano FG, Pighizzini G, Sannella TD, editors. Mathematical Foundations of Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg; 2015. p. 243–255. doi:10.1007/978-3-662-48057-1 19.
• [8] Trahtman A. An efficient algorithm finds noticeable trends and examples concerning the Černý conjecture. In: Královič P R ; Urzyczyn, editor. Mathematical Foundations of Computer Science. vol. 4162 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2006. p. 789–800. doi:10.1007/978-3-642-13182-0 4.
• [9] Roman A. Synchronizing finite automata with short reset words. Applied Mathematics and Computation. 2009;209(1):125 – 136. Special Issue International Conference on Computational Methods in Sciences and Engineering 2005 (ICCMSE-2005). doi:http://dx.doi.org/10.1016/j.amc.2008.06.019.
• [10] Ananichev DS, Gusev VV, Volkov MV. Primitive digraphs with large exponents and slowly synchronizing automata. Journal of Mathematical Sciences. 2013;192(3):263–278. doi:10.1007/s10958-013-1392-8.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).