Deciding whether a finite set of words has rank at most two (Q1210296)

Let \(X\subseteq A^*\) be a finite set of words over the alphabet \(A\). The rank \(r(X)\) of \(X\) is the smallest size of a set \(Y\subseteq A^*\) of words such that \(X\subseteq Y^*\). The author presents an algorithm to check the condition \(r(X)\leq 2\). This algorithm works in \(O(n\log^ 2 m)\) time, where \(n\) is the sum of the lengths of words in \(X\) and \(m\) is the length of the longest word in \(X\).