Generalised star-height problem

Summary

AI-assisted claims

Claims as their sources state them. Papex has not checked them; the status stays the source’s.

All AI-assisted claims

Why it is open

Regular expressions describe sets of words, called languages, from single letters with union, concatenation and the Kleene star, which describes an arbitrarily long repetition [7, 9]. Extended, or generalised, expressions also allow complement, the set of all words not in a language [7]. The star height of an extended expression is its maximum depth of nested stars, with complement adding nothing; the generalised star height of a regular language is the least star height of an extended expression that defines it [7].

The problem has several layers. Janusz Brzozowski included star height among six open problems about regular languages that he presented in 1979, and Jean-Éric Pin's 2017 survey states it as the question whether an algorithm computes the star height of a given regular language [7]. Wikipedia's list asks whether all regular languages can be expressed with a limited nesting depth of stars [10]. The sharpest question is whether any language needs height 2: Pin wrote that "we still have no example of a language of star height 2" [7], and the abstract of Thomas Bourne's thesis of the same year says: "Rather surprisingly, it is not yet known whether there exists a regular language of generalised star-height greater than one" [8]. Howard Straubing distinguished a universal finite bound from a universal bound of one, a 2026 manuscript notes [9].

The version without complement, the restricted star-height problem, is solved: Kosaburo Hashiguchi proved in 1988 that restricted star height is decidable [2, 7]. No prize or committee sets terms for a resolution; the status here follows Wikipedia's list of unsolved problems in computer science [10].

What is known

Restricted star height (1963–2015). Lawrence C. Eggan raised the star-height problem for ordinary regular expressions in 1963, and in 1966 Françoise Dejean and Marcel-Paul Schützenberger showed that for each n some language has restricted star height n [7]. Hashiguchi proved in 1982 that restricted star height one is decidable, and in 1988 the general case [2, 7]. Pin calls the proof hard to read, with an algorithm of non-elementary complexity [7]. Daniel Kirsten's simpler proof of 2005 decides in doubly exponential space whether the language of an n-state nondeterministic automaton has star height less than a given integer, "the first ever complexity bound for the star height problem" [4, 7]. Bojańczyk gave a further proof through games in 2015 [7].

Height 0: star-free languages (1965). Languages of generalised star height 0 are called star-free [7]. A language's syntactic monoid identifies two words when exchanging them inside any word never changes membership in the language [7]. Schützenberger proved in 1965 that a language is star-free if and only if its syntactic monoid is aperiodic, that is, group-free, so height 0 is decidable [1, 3, 7]. For example, (ab)* over the letters a and b is star-free, while (aa)* is not and has star height 1 [7]. Avraham Trahtman proved in 2007 that synchronising automata accepting only star-free languages satisfy the Černý conjecture [5]; see the Papex page Černý conjecture.

Height at most 1 (1971–2017). Henneman showed in 1971 that languages recognised by commutative groups have star height at most 1 [3, 7]. In 1992 Pin, Straubing and Denis Thérien extended this to nilpotent groups of class 2 and to every group of order less than 12 [3]. Writing L(u, k, n) for the words in which u occurs as a subsequence a number of times congruent to k modulo n, they proved height at most 1 when u has length at most 2, and when u has length 3 and n is square-free [3]. This covers L(abc, 0, 2), which Brzozowski had proposed as a candidate for height 2 [3]. For contiguous occurrences, Bourne and Nik Ruškuc proved height at most 1 in three special cases in 2016, and for languages recognised by Rees zero-matrix semigroups over abelian groups [6]. Bourne's thesis showed that the languages in which a fixed word occurs as a contiguous factor exactly a given number of times are all star-free, and that counting such occurrences modulo a fixed number gives height at most 1 [8].

Structure (1978–2017). For each n, the languages of height at most n are closed under Boolean operations, quotients and inverses of length-decreasing morphisms, as Pin, Straubing and Thérien proved [3, 7]. By a 1978 result of Pin's, if the languages of height at most 1 were also closed under all inverse morphisms, every regular language would have height at most 1 [7]. Every regular language is the inverse image, under some morphism between free monoids, of a language of restricted star height 1 [3]. Several past candidates for height 2 have been turned down [7].

Recent claims. On 6 October 2026 OpenAI released a repository of mathematical manuscripts "produced by an internal OpenAI model", which it says are "at different stages of verification" [9]. Three manuscripts dated 25 September 2026 claim that every regular language over a finite alphabet has generalised star height at most 13, at most 4 and at most 3, each with its own proof; a Lean formalisation of the bound of three is linked to them [9]. The repository describes this as "resolving the uniform-boundedness version of the generalized star-height problem" [9]. The manuscript for three says that it "does not exhibit a language of generalized height greater than one, and does not decide whether one always suffices", and that its construction bounds nesting "without a bound on expression size or running time" [9]. Wikipedia's list of unsolved problems, last revised on 15 September 2026, includes the problem [10].

Main approaches

An algebraic invariant. Characterise the languages of height at most 1 by a property of their syntactic monoids, as Schützenberger did for height 0 [3, 7]. Strongest evidence: Schützenberger's theorem, and the closure of each level under Boolean operations, quotients and inverse length-decreasing morphisms [7]. Main difficulty: Pin's 1978 result "appears to kill the algebraic approach, unless every language has star height 0 or 1"; a single nontrivial identity of the weaker kind satisfied by all languages of height at most 1 would give a language of height 2, but none is known [7].

Group languages as candidates. Since group-free is equivalent to star-free, look for height 2 among languages whose syntactic monoid is a group [3]. Strongest evidence: Pin, Straubing and Thérien could not complete the case of subsequences of length 3 [3], and Pin names languages defined through a morphism onto a group such as the symmetric group S5 as reasonable candidates [7]. Main difficulty: commutative groups, nilpotent groups of class 2 and all groups of order below 12 give only height at most 1 [3].

Counting languages. Prove height at most 1 for families of languages that count subsequences or contiguous factors [3, 6, 8]. Strongest evidence: the results for nilpotent groups of class 2 and for Rees zero-matrix semigroups over abelian groups [3, 6]. Main difficulty: these families are restricted [9], and the subsequence case of length 3 is incomplete [3].

Inverse morphisms. To show that every language has height at most 1, prove that the languages of height at most 1 are closed under inverse morphisms [3, 7]. Strongest evidence: the reduction through restricted star height 1 [3]. Main difficulty: even inverse images of F*, with F a finite language, "can be extremely complicated" [7].

Direct constructions. Express the computation of a finite monoid on a word with expressions of bounded height [9]. Strongest evidence: the claimed bounds of 13, 4 and 3, with a formalisation listed for 3 [9]. Main difficulty: these are preprints released by OpenAI, and the bound of three does not decide whether height 1 suffices [9].

Open sub-questions

1. Symmetric-group languages. For a morphism π from the words over an alphabet onto the symmetric group S5, does π⁻¹(1) have generalised star height 1, or is it a language of height 2, as Pin suggests it might be [7]?
2. Length-three subsequences. Does L(u, k, n) have height at most 1 for every word u of length 3 when n is not square-free, the case Pin, Straubing and Thérien left open in 1992 [3]?
3. An identity. Is there a nontrivial profinite identity, of the kind preserved by inverse length-decreasing morphisms, that all languages of height at most 1 satisfy [7]?
4. Stars of finite languages. Do the languages F*, with F finite, generate all regular languages under Boolean operations, quotients and inverse length-decreasing morphisms, which Pin records as unknown [7]?
5. Two nested stars. Can the construction in the 2026 manuscript, which gives height at most 3, be shortened to height 2 [9]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

1. Schützenberger, M. P. (1965). On finite monoids having only trivial subgroups. Information and Control 8(2), 190–194. 10.1016/S0019-9958(65)90108-7 · Checked 16 Oct 2026
2. Hashiguchi, K. (1988). Algorithms for determining relative star height and star height. Information and Computation 78(2), 124–169. 10.1016/0890-5401(88)90033-8 · Checked 16 Oct 2026
3. Pin, J.-É., Straubing, H. & Thérien, D. (1992). Some results on the generalized star-height problem. Information and Computation 101(2), 219–250. 10.1016/0890-5401(92)90063-L · Checked 16 Oct 2026
4. Kirsten, D. (2005). Distance desert automata and the star height problem. RAIRO – Theoretical Informatics and Applications 39(3), 455–509. 10.1051/ita:2005027 · Checked 16 Oct 2026
5. Trahtman, A. N. (2007). The Černý conjecture for aperiodic automata. Discrete Mathematics and Theoretical Computer Science 9(2), 3–10. 10.46298/dmtcs.395 · Checked 16 Oct 2026
6. Bourne, T. & Ruškuc, N. (2016). On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups. Theoretical Computer Science 653, 87–96. 10.1016/j.tcs.2016.09.024 · Checked 16 Oct 2026
7. Pin, J.-É. (2017). Open problems about regular languages, 35 years later. In The Role of Theory in Computer Science, World Scientific, 153–175. 10.1142/9789813148208_0007 · Checked 16 Oct 2026
8. Bourne, T. (2017). Counting subwords and other results related to the generalised star-height problem for regular languages. PhD thesis, University of St Andrews. Source · Checked 16 Oct 2026
9. OpenAI (2026). Generalized star height at most three. OpenAI Math Release preprint, manuscript dated 25 September 2026, released 6 October 2026, with the companion manuscripts "Generalized Star Height at Most Four" and "Finite Monoid Computations and a Uniform Generalized Star-Height Bound" (both dated 25 September 2026). Source · Checked 16 Oct 2026
10. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.