Approximating the minimum length of synchronizing words is hard

Abstract

We prove that, unless $\mathrm{P}=\mathrm{NP}$, no polynomial algorithm can approximate the minimum length of \sws for a given \san within a constant factor.

arXiv comment12 pages, 1 figure

Cited by in corpus (3)

• Primitive digraphs with large exponents and slowly synchronizing automata
• The Complexity of Finding Reset Words in Finite Automata
• Checking Whether an Automaton Is Monotonic Is NP-complete