On the Piecewise Complexity of Words and Periodic Words

The piecewise complexity h(u) of a word is the minimal length of subwords needed to exactly characterise u. Its piecewise minimality index \(\rho (u)\) is the smallest length k such that u is minimal among its order-k class \([u]_k\) in Simon’s congruence. We study these two measures and provide efficient algorithms for computing h(u) and \(\rho (u)\) . We also provide efficient algorithms for the case where u is a periodic word, of the form \(u=v^n\) .