I'm interested in the (restricted) star-height of star free-languages.
Recalling the definitions: the star height $h(\mathtt{e})$ of a regular expression $\mathtt{e}$ is
- $0$ if $\mathtt{e}= \varepsilon$ or $a \in \Sigma$
- $\max(h(\mathtt{f}),h(\mathtt{f'}))$ if $\mathtt{e}=\mathtt{f+f'}$ or $\mathtt{f.f'}$
- $1+h(\mathtt{f})$ if $\mathtt{e}=\mathtt{f ^*}$
The star height of a languages is the smallest star height among the regular expressions describing the language.
On the other hand, the star free languages is the smallest set of languages containing the empty set and each individual letter, and closed under concatenation, union and complement (thus also intersection).
I know that the languages of star height $0$ are the finite languages, and that star-free languages can have positive star height. I also know that a family of witnesses for the infinity of the star height hierarchy is the set of languages $L_n= \{\mathbf{w} \in \Sigma^* \quad |\quad |\mathbf{w}|_a= |\mathbf{w}|_b\equiv 0 \mod (2^n) \}$, but these are not star-free
My question is can a star-free language have an arbitrary large star height?
disclaimer: I might be missing some obvious point, but a quick internet check was not productive