<p>This answer is dedicated to the memory of Janusz (John) Antoni Brzozowski, who passed away on October 24, 2019.</p>

<p>John is certainly the person who made the star-height problems so famous. Indeed, at a conference in Santa Barbara in December 1979, he presented a selection of six open problems about regular languages and mentioned two other topics in the conclusion of his article [1]. These six open problems were, in order, star height, restricted star height, group complexity, star removal, regularity of non-counting classes and optimality of prefix codes. The two other topics were the limitedness problem and the dot-depth hierarchy.</p>

<p>In June 2015, during a <a href="https://cs.uwaterloo.ca/events/brzozowski-80-role-theory-computer-science" rel="noreferrer">one-day conference in honour of his 80th birthday</a>,
I presented two survey articles summarising the state of the art on these questions [2, 3]. In particular, you will find in [2] detailed information on the star-height problems.</p>

<p>[1] J. A. Brzozowski, <a href="https://books.google.fr/books?id=kT60BQAAQBAJ&amp;pg=PR4&amp;lpg=PR4&amp;dq=Formal+language+theory.+Perspectives+and+open+problems,+Proceedings+of+a+symposium+held+in+Santa+Barbara&amp;source=bl&amp;ots=zRyvthkh7q&amp;sig=ACfU3U3B27aW4E1xRmWZjVylFIf1HOqoyA&amp;hl=fr&amp;sa=X&amp;ved=2ahUKEwjDu-S4-dLlAhVy8eAKHa9sAZgQ6AEwBnoECAoQBA#v=onepage&amp;q=Formal%20language%20theory.%20Perspectives%20and%20open%20problems%2C%20Proceedings%20of%20a%20symposium%20held%20in%20Santa%20Barbara&amp;f=false" rel="noreferrer">Open problems about regular languages</a>, in Formal language theory. Perspectives and open problems, Proceedings of a symposium held in Santa Barbara, California, December 10-14, 1979[, R. V. Book (ed.), pp. 23–47, New York Etc.: Academic Press, a Subsidiary of Harcourt Brace Jovanovich, Publishers. XIII, 454 p., 1980.</p>

<p>[2] J.-É. Pin, <a href="https://hal.archives-ouvertes.fr/hal-01614375v2/document" rel="noreferrer">Open problems about regular languages, 35 years later</a>, Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski, World Scientific, 2017,</p>

<p>[3] J.-É. Pin, <a href="https://hal.archives-ouvertes.fr/hal-01614357/document" rel="noreferrer">The dot-depth hierarchy, 45 years later</a>. Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski, World Scientific, 2017.</p>

CC BY-SA 4.0
2019-11-05T22:02:54.677Z
Thanks for sharing this - I just learned from your answer that he passed away.
Hermann Gruber
CC BY-SA 4.0
2019-11-05T11:26:24.447Z
2019-11-05T11:26:24.447Z
J.-E. Pin
<p>Regarding your second question, an explanation why the generalized star height problem is less accessible than the star height problem is the following: Already Eggan's seminal paper in 1963 contained languages of (ordinary) star height $k$, for each $k\ge 0$. Only a few years later, McNaughton, and, independently, Déjean and Schützenberger, found examples over binary alphabets. This made clear what the problem "is about". During the years that followed, there was a more or less steady flow of published results in the area of the ordinary star height problem. This gave an ever increasing body of published examples, counterexamples and phenomena surrounding this problem.</p>

<p>In contrast, after some fifty years now, we don't know whether there is any regular language of star height at least two. So we do not even know whether there is a need for a decision procedure after all. This "complete lack of examples" indicates that it is extremely difficult to get a grip on this problem. </p>

CC BY-SA 3.0
2011-04-18T01:21:57.083Z
Do you know of any applications/areas that would be directly affected by the discovery of an actual algorithm? (other than from a purely intellectual standpoint)
Patrick Papadopulos
CC BY-SA 3.0
2011-04-23T13:50:13.750Z
The classification of the languages of star height $0$ turned out to have an extremely rich theory, see for example: Robert McNaughton & Seymour Papert. Counter-free Automata. MIT Press, 1971. The classification of languages of star height $1$ might have just as many consequences. Yet, I do not know of any direct consequences à la "Assuming the generalized star height hierarchy is infinite, we can prove...". But I am probably not the best person to ask either.
Hermann Gruber
CC BY-SA 3.0
2015-01-13T15:35:51.710Z
Restricted star-height is likely to be applied soon in a work about approximating costs of components in communicating systems. (no reference yet sorry)
Denis
CC BY-SA 3.0
2011-04-17T22:17:20.167Z
2011-04-17T22:17:20.167Z
Hermann Gruber
<p>The solution of the restricted star-height problem inspired the rich theory of regular cost functions (by Colcombet), which in turn helped to solve other decidability problems and offers new tools to attack open problems. This theory is still developing and was extended to infinite words, finite trees, infinite trees, with its own set of deep results and open problems.
Here is a  <a href="http://www.liafa.univ-paris-diderot.fr/~colcombe/Publications/ICALP09-colcombet.pdf" rel="nofollow">seminal paper</a> of the  theory, and a <a href="http://www.liafa.univ-paris-diderot.fr/~colcombe/bibliography_en.html" rel="nofollow">bibliography</a>, from Colcombet's website.</p>

<p>So while it is not directly an application of generalized star-height, it shows that progressing on seemingly useless problems such as star-height is likely to mean better understanding of regular languages, and yield new results on different problems.</p>

<p>Reference : Thomas Colcombet. “The theory of stabilisation monoids and regular cost functions”. In: ICALP 2009</p>

CC BY-SA 3.0
2015-01-12T14:45:31.927Z
2015-01-12T15:05:12.323Z
2015-01-12T15:05:12.323Z
Denis
<p>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:</p>

<p>(1) $\emptyset, 1$ and $a$ are extended regular expressions for all $a\in A$</p>

<p>(2) For all extended regular expressions $E,F$; <br/>
 $E\cup F$, $EF$, $E^*$ and $E^c$ are extended regular expressions</p>

<p>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.</p>

<ol>
<li><p>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. </p></li>
<li><p>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?</p></li>
</ol>

<p>A link that might be helpful is the following: <a href="http://www.liafa.univ-paris-diderot.fr/~jep/PDF/StarHeight.pdf" rel="noreferrer"> starheight  </a></p>

CC BY-SA 3.0
2011-04-17T19:41:42.627Z
A clear definition of 'extended regular expression" or a link would be helpful. Also links to the papers cited would help flesh out the question
Suresh Venkat
CC BY-SA 3.0
2011-04-17T19:48:27.887Z
@Suresh Given a finite alphabet A, then the extended regular expression are defined by: $\emptyset, 1, a$ for every $a\in A$ are extended regular expressions.  Also, union, concatenation, complement and star are extended regular expressions.  Basically just adding complement.  A link that might be helpful is the following: http://www.liafa.jussieu.fr/~jep/PDF/StarHeight.pdf
Patrick Papadopulos
CC BY-SA 3.0
2011-04-17T20:46:32.413Z
AFAIK, Pin keeps his webpage updated ( http://liafa.jussieu.fr/~jep/Problemes/starheight.html ), which would mean no progress.
Michaël Cadilhac
CC BY-SA 3.0
2011-04-17T21:31:13.513Z
thanks: even better would be to incorporate it in the question.
Suresh Venkat
CC BY-SA 3.0
2015-01-13T14:12:46.290Z
In the previous comments, "liafa.jussieu.fr" should be replaced "www.liafa.univ-paris-diderot.fr". I edited the link in the question, but could not edit the links in the comments.
J.-E. Pin
<fl.formal-languages><lower-bounds><regular-expressions>
Progress on generalized star-height problem?
Patrick Papadopulos
# Progress on generalized star-height problem?

(Asked by: username_0 on 2011-04-17)

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.

1. 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.
2. 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](http://www.liafa.univ-paris-diderot.fr/~jep/PDF/StarHeight.pdf)

**Tags:** fl.formal-languages, lower-bounds, regular-expressions
> **Comments:**
> **username_1**: A clear definition of 'extended regular expression" or a link would be helpful. Also links to the papers cited would help flesh out the question  
> **username_0**: @Suresh Given a finite alphabet A, then the extended regular expression are defined by: $\emptyset, 1, a$ for every $a\in A$ are extended regular expressions.  Also, union, concatenation, complement and star are extended regular expressions.  Basically just adding complement.  A link that might be helpful is the following: http://www.liafa.jussieu.fr/~jep/PDF/StarHeight.pdf  
> **username_2**: AFAIK, Pin keeps his webpage updated ( http://liafa.jussieu.fr/~jep/Problemes/starheight.html ), which would mean no progress.  
> **username_1**: thanks: even better would be to incorporate it in the question.  
> **username_3**: In the previous comments, "liafa.jussieu.fr" should be replaced "www.liafa.univ-paris-diderot.fr". I edited the link in the question, but could not edit the links in the comments.  

---

## 3 answers

### Answer by username_3 on 2019-11-05. Score: 10

This answer is dedicated to the memory of Janusz (John) Antoni Brzozowski, who passed away on October 24, 2019.

John is certainly the person who made the star-height problems so famous. Indeed, at a conference in Santa Barbara in December 1979, he presented a selection of six open problems about regular languages and mentioned two other topics in the conclusion of his article [1]. These six open problems were, in order, star height, restricted star height, group complexity, star removal, regularity of non-counting classes and optimality of prefix codes. The two other topics were the limitedness problem and the dot-depth hierarchy.

In June 2015, during a [one-day conference in honour of his 80th birthday](https://cs.uwaterloo.ca/events/brzozowski-80-role-theory-computer-science),
I presented two survey articles summarising the state of the art on these questions [2, 3]. In particular, you will find in [2] detailed information on the star-height problems.

[1] J. A. Brzozowski, [Open problems about regular languages](https://books.google.fr/books?id=kT60BQAAQBAJ&pg=PR4&lpg=PR4&dq=Formal+language+theory.+Perspectives+and+open+problems,+Proceedings+of+a+symposium+held+in+Santa+Barbara&source=bl&ots=zRyvthkh7q&sig=ACfU3U3B27aW4E1xRmWZjVylFIf1HOqoyA&hl=fr&sa=X&ved=2ahUKEwjDu-S4-dLlAhVy8eAKHa9sAZgQ6AEwBnoECAoQBA#v=onepage&q=Formal%20language%20theory.%20Perspectives%20and%20open%20problems%2C%20Proceedings%20of%20a%20symposium%20held%20in%20Santa%20Barbara&f=false), in Formal language theory. Perspectives and open problems, Proceedings of a symposium held in Santa Barbara, California, December 10-14, 1979[, R. V. Book (ed.), pp. 23–47, New York Etc.: Academic Press, a Subsidiary of Harcourt Brace Jovanovich, Publishers. XIII, 454 p., 1980.

[2] J.-É. Pin, [Open problems about regular languages, 35 years later](https://hal.archives-ouvertes.fr/hal-01614375v2/document), Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski, World Scientific, 2017,

[3] J.-É. Pin, [The dot-depth hierarchy, 45 years later](https://hal.archives-ouvertes.fr/hal-01614357/document). Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski, World Scientific, 2017.

> **Comments:**
> **username_4**: Thanks for sharing this - I just learned from your answer that he passed away.  

---

### Answer by username_4 on 2011-04-17. Score: 9

Regarding your second question, an explanation why the generalized star height problem is less accessible than the star height problem is the following: Already Eggan's seminal paper in 1963 contained languages of (ordinary) star height $k$, for each $k\ge 0$. Only a few years later, McNaughton, and, independently, Déjean and Schützenberger, found examples over binary alphabets. This made clear what the problem "is about". During the years that followed, there was a more or less steady flow of published results in the area of the ordinary star height problem. This gave an ever increasing body of published examples, counterexamples and phenomena surrounding this problem.

In contrast, after some fifty years now, we don't know whether there is any regular language of star height at least two. So we do not even know whether there is a need for a decision procedure after all. This "complete lack of examples" indicates that it is extremely difficult to get a grip on this problem.

> **Comments:**
> **username_0**: Do you know of any applications/areas that would be directly affected by the discovery of an actual algorithm? (other than from a purely intellectual standpoint)  
> **username_4**: The classification of the languages of star height $0$ turned out to have an extremely rich theory, see for example: Robert McNaughton & Seymour Papert. Counter-free Automata. MIT Press, 1971. The classification of languages of star height $1$ might have just as many consequences. Yet, I do not know of any direct consequences à la "Assuming the generalized star height hierarchy is infinite, we can prove...". But I am probably not the best person to ask either.  
> **username_5**: Restricted star-height is likely to be applied soon in a work about approximating costs of components in communicating systems. (no reference yet sorry)  

---

### Answer by username_5 on 2015-01-12. Score: 3

The solution of the restricted star-height problem inspired the rich theory of regular cost functions (by Colcombet), which in turn helped to solve other decidability problems and offers new tools to attack open problems. This theory is still developing and was extended to infinite words, finite trees, infinite trees, with its own set of deep results and open problems.
Here is a [seminal paper](http://www.liafa.univ-paris-diderot.fr/~colcombe/Publications/ICALP09-colcombet.pdf) of the theory, and a [bibliography](http://www.liafa.univ-paris-diderot.fr/~colcombe/bibliography_en.html), from Colcombet's website.

So while it is not directly an application of generalized star-height, it shows that progressing on seemingly useless problems such as star-height is likely to mean better understanding of regular languages, and yield new results on different problems.

Reference : Thomas Colcombet. “The theory of stabilisation monoids and regular cost functions”. In: ICALP 2009


---

