On the piecewise complexity of 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 $\ddot{I}(u)$ is the smallest length $k$ such that $u$ is minimal among its order-$k$ class $[u{]}_k$ in Simon's congruence. We initiate a study of these two descriptive complexity measures. Among other results we provide efficient algorithms for computing $h(u)$ and $\ddot{I}(u)$ for a given word $u$.