Strong inapproximability of the shortest reset word

2014/08/22 by Paweł Gawrychowski, Gawrychowski, Pawel, Damian Straszak +1 · 1 citation
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1408.5248

openalex publication_date 2014/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Černý conjecture states that every n-state synchronizing automaton has a reset word of length at most (n-1)². We study the hardness of finding short reset words. It is known that the exact version of the problem, i.e., finding the shortest reset word, is NP-hard and coNP-hard, and complete for the DP class, and that approximating the length of the shortest reset word within a factor of O(log n) is NP-hard [Gerbush and Heeringa, CIAA'10], even for the binary alphabet [Berlinkov, DLT'13]. We significantly improve on these results by showing that, for every ε>0, it is NP-hard to approximate the length of the shortest reset word within a factor of n^1-ε. This is essentially tight since a simple O(n)-approximation algorithm exists.

Cited by

• Primitive sets of nonnegative matrices and synchronizing automata

Related

• The Černý conjecture for small automata: experimental report
• Generating Synchronizing Automata with Large Reset Lengths
• List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata
• Experimental Study of the Shortest Reset Word of Random Automata
• An improvement to a recent upper bound for synchronizing words of finite automata