Collapsing words, permutation conditions and coherent colorings of trees

Given a word w over a finite alphabet Σ and a finite deterministic automaton A=〈Q,Σ,δ〉, the inequality |δ(Q,w)|≤|Q|−n means that under the natural action of the word w the image of the state set Q is reduced by at least n states. A word w is n-collapsing if this inequality holds for any deterministic finite automaton that satisfies such an inequality for at least one word. In this paper we prove that the problem of recognizing n-collapsing words is generally co-NP-complete, while restricted to 2-collapsing words over 2-element alphabet it belongs to P. This is connected with introducing a new approach to collapsing words, which is shown to be much more effective in solving various problems in the area. It leads to interesting connections with combinatorial problems concerning solving systems of permutation conditions on one hand, and coloring trees with distinguished nodes on the other hand.