On the starheight of some rational subsets closed under partial commutations (Q1308983)

For a partial commutation relation (a symmetric partial relation) \(\theta\subseteq A\times A\), over an alphabet \(A\), we denote by \(\bar\theta\) its complement: for a string \(w\in A^*\), denote by \([w^*]\) the set of all words in \(A^*\) equivalent to a power \(w^ n\) of \(w\) under the partial commutation \(\theta\). This set is a regular language if and only if \(\bar\theta\) as a graph on the vertices \(A\) is connected [\textit{R. Cori} and \textit{D. Perrin}, RAIRO, Inf. Theor. Appl.19, 21-32 (1985; Zbl 0601.68055)]. The present paper investigates the starheight of languages of the form \([w^*]\) for \(\theta\) as above with \(\bar\theta\) connected. It is proved that (1) when \(\theta\) is not connected, then the starheight is one, but (2) when \(\theta\) is connected, then the starheight can be arbitrarily large: for each \(n>0\) there exists \(w\in A^*\) of length \(O(n)\) such that \([w^*]\) has the starheight equal to \(n\). This second result is a stronger form of a theorem (presented without a complete proof) by \textit{C. Choffrut} and \textit{C. Duboc} [Lect. Notes Comput. Sci. 267, 190-201 (1987; Zbl 0634.20026)].