Generalized star height problem
Let be a finite alphabet. The set of generalized regular expressions over is defined inductively: and for each are generalized regular expressions, and if and are generalized regular expressions, then so are , , and . The language denoted by such an expression is given by , , , , , and .
The star height of a generalized regular expression is defined by
For a regular language , its generalized star height is
Then: for every finite alphabet and every regular language ,
that is, can be denoted by a generalized regular expression in which no Kleene star occurs inside the scope of another Kleene star.
References
- Wikipedia, Generalized star-height problem, the article this problem comes from.
Source: Wikipedia
Progress summary
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 solution
GitHub repository: https://github.com/openai/math
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 solution
GitHub repository: https://github.com/openai/math
- OpenAI-134-02-Generalized-Star-Height-at-Most-Four.pdfOpen
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 solution
GitHub repository: https://github.com/openai/math
- OpenAI-134-03-Generalized-Star-Height-at-Most-Three.pdfOpen