COLLAPSING WORDS: A PROGRESS REPORT
Dmitry S. Ananichev, I. V. Petrov, Mikhail Vladimirovich Volkov · International Journal of Foundations of Computer Science · 2006
A word w over a finite alphabet Σ is n-collapsing if for an arbitrary DFA [Formula: see text], the inequality |δ(Q, w)| ≤ |Q| - n holds provided that |δ(Q, u)| ≤ |Q| - n for some word u ∈ Σ+(depending on [Formula: see text]). 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.