Collapsing Words: A Progress Report.

A word w over a finite alphabet Σ is n-collapsing if for an arbitrary DFA ${\mathcal A}=\langle Q,\Sigma,\delta\rangle$, the inequality $<INNOPIPE>\delta(Q,w)<INNOPIPE>\le<INNOPIPE>Q<INNOPIPE>-n$ holds provided that $<INNOPIPE>\delta(Q,u)<INNOPIPE>\le<INNOPIPE>Q<INNOPIPE>-n$ for some word u∈Σ+ (depending on ${\mathcal A}$). We overview some recent results related to this notion. One of these results implies that the property of being n-collapsing is algorithmically recognizable for any given positive integer n. [ABSTRACT FROM AUTHOR]