Binary 3-compressible automata

A finite deterministic automaton A = (Q, Σ, δ) is k-compressible if there is a word w ∈ Σ+ such that the image of the state set Q under the natural action of w is reduced by at least k states. In such case w is called a k-compressing word for A. It is known that, for any alphabet Σ and any k ≥ 2, there exist words that are k-compressing for each k-compressible automaton with the input alphabet Σ. Such words are called k-collapsing. It has been proved that recognizing 2-collapsing words over a 2-element alphabet may be done in polynomial time, while recognizing 2-collapsing words over an alphabet of size ≥ 3 is co-NP-complete. A natural question in this context, whether recognizing 3-collapsing words over a 2-element alphabet is easy or hard, has remained open. In this paper we provide results on 3-compressible binary automata, which allow to prove that that the latter problem is co-NP-complete