Recognizing 3-collapsing words over a binary alphabet ?
A finite deterministic automaton A=(Q,?,?) A = ( Q , ? , ? ) is k -compressible if there is a word w??+ 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 A . It is known that, for any alphabet ? and any k?2 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 n?3 n ? 3 is co-NP-complete. The computational complexity of recognizing k -collapsing words with k?3 k ? 3 over an n -element alphabet has remained open. In this paper we prove that this remaining problem is co-NP-complete in the simplest case with k=3 k = 3 and n=2 n = 2 .
k-collapsing words k-compressible automata permutation conditions