The (generalized) star height of a language is the minimum nesting of Kleene stars required to represent the language by an extended regular expression. Recall that an extended regular expression over a finite alphabet $A$ satisfies the following:
(1) $\emptyset, 1$ and $a$ are extended regular expressions for all $a\in A$
(2) For all extended regular expressions $E,F$;
$E\cup F$, $EF$, $E^*$ and $E^c$ are extended regular expressions
One phrasing of the generalized star height problem is whether there is an algorithm to compute the minimum generalized star height. With regards to this problem I have a few questions.
Has there been any recent progress (or research interest) concerning this problem? I know a number of years ago that Pin Straubing and Thérien published some papers in this area.
The restricted star height problem was resolved in 1988 by Hashiguchi but the generalized version (as far as I know) is still open. Does anyone have any intuition as to why this might be the case?
A link that might be helpful is the following: starheight