Normal forms under Simon's congruence (Q667852)

A word \(u\) is a subword of a word \(w\) if \(u\) is a sequence of not necessarily consecutive letters from \(w\). Given a natural number \(k\) and words \(u\) and \(v\), write \(u \sim_k v\) if \(u\) and \(v\) share the same subwords of length at most \(k\). The equivalence relation \(\sim_k\) is a congruence with finite index, the so-called Simon's congruence, which defines the \(k\)-piecewise testable languages well-studied in combinatorics on words. A language is \(k\)-piecewise testable if it is a union of classes of \(\sim_k\). Simon found a basis of identities for \(k\)-piecewise testable languages when \(k \in \{1, 2\}\). Moreover, the reviewer gave a basis of identities when \(k = 3\) and proved that there is no finite basis of identities when \(k > 3\). In this very interesting paper, the author presents a normal form for the equivalence classes of \(\sim_k\), whose length is minimal. The author shows how to find a canonical solution of the equation \(pwq \sim_k r\), where the words \(p\), \(q\), \(r\) are parameters and the aim is to solve the equation for the variable \(w\), which is also a word. This can be viewed as a generalization of giving a normal form of the words for \(\sim_k\). Indeed, it has been proved that if a canonical solution of \(pwq \sim_k r\) can be found for some \(k\), then a normal form can be found for \(k + 2\). The author also gives an algorithm to find the canonical solution in \(O((L + n)nk)\) deterministic time, where \(L\) denotes the length of \(pqr\) and \(n\) the size of the alphabet.