On the starheight of some rational subsets closed under partial commutations

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)].

Recommendations

Cited in

(5)

This page was built for publication: On the starheight of some rational subsets closed under partial commutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1308983)