← All problems

Generalized star height problem

62 years old · documented by

Let AA be a finite alphabet. The set of generalized regular expressions over AA is defined inductively: ∅\emptyset and aa for each a∈Aa \in A are generalized regular expressions, and if EE and FF are generalized regular expressions, then so are (E∪F)(E \cup F), (E⋅F)(E \cdot F), (E∗)(E^{*}) and (Ec)(E^{c}). The language L(E)⊆A∗L(E) \subseteq A^{*} denoted by such an expression is given by L(∅)=∅L(\emptyset) = \emptyset, L(a)={a}L(a) = \{a\}, L(E∪F)=L(E)∪L(F)L(E \cup F) = L(E) \cup L(F), L(E⋅F)=L(E)L(F)={uv:u∈L(E), v∈L(F)}L(E \cdot F) = L(E)L(F) = \{uv : u \in L(E),\, v \in L(F)\}, L(E∗)=⋃n≥0L(E)nL(E^{*}) = \bigcup_{n \ge 0} L(E)^{n}, and L(Ec)=A∗∖L(E)L(E^{c}) = A^{*} \setminus L(E).

The star height h(E)h(E) of a generalized regular expression is defined by

h(∅)=h(a)=0,h(E∪F)=h(E⋅F)=max⁡{h(E),h(F)},h(Ec)=h(E),h(E∗)=h(E)+1.h(\emptyset) = h(a) = 0, \qquad h(E \cup F) = h(E \cdot F) = \max\{h(E), h(F)\}, \qquad h(E^{c}) = h(E), \qquad h(E^{*}) = h(E) + 1 .

For a regular language L⊆A∗L \subseteq A^{*}, its generalized star height is

gh(L)=min⁡{h(E):E a generalized regular expression over A with L(E)=L}.\mathrm{gh}(L) = \min \{ h(E) : E \text{ a generalized regular expression over } A \text{ with } L(E) = L \} .

Then: for every finite alphabet AA and every regular language L⊆A∗L \subseteq A^{*},

gh(L)≤1,\mathrm{gh}(L) \le 1 ,

that is, LL can be denoted by a generalized regular expression in which no Kleene star occurs inside the scope of another Kleene star.

References
  1. Wikipedia, Generalized star-height problem, the article this problem comes from.

Source: Wikipedia

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 3

Claimed by OpenAI. For every regular language over every finite alphabet, the manuscript claims a generalized regular expression over the same alphabet with star height at most thirteen, allowing union, concatenation and complement in that alphabet’s free monoid. This is related progress toward the page’s generalized star-height-one assertion; a bound of thirteen does not establish the requested bound of one.See full solutionHide full solution
Claimed by OpenAI. For every regular language over every finite alphabet, the manuscript claims generalized star height at most four over that same alphabet, with complements taken in its free monoid. This is related progress toward the page’s universal bound of one. The finite bound of four does not establish star height one.See full solutionHide full solution
Claimed by OpenAI. For every regular language over every finite alphabet, the manuscript claims generalized star height at most three, using expressions over the same alphabet and complement within its free monoid. This is related progress toward the page’s universal star-height-one assertion; the bound of three does not establish the requested bound of one.See full solutionHide full solution