On the piecewise complexity of words and periodic words

Abstract

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$