Generalized star height at most three

Source and verification

This article explains family 134 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Expressions, complement, and iteration depth

A regular language is a set of finite words accepted by a finite deterministic automaton. A generalized regular expression over a fixed finite alphabet $\Sigma$ starts from $0$, $1$, and letters, denoting $\varnothing$, $\{\epsilon \}$, and singleton-letter languages. It permits union, concatenation, complement in ${\Sigma }^{\ast }$, and Kleene star. The language $P^{\ast }$ consists of all finite concatenations of words in $P$, including the empty concatenation.

Star height counts nested stars:

$$\begin{array}{c}h(0)=h(1)=h(a)=0,\\ h(P\cup Q)=h(PQ)\\ =\max (h(P),h(Q)),\\ h(\neg P)=h(P),\\ h(P^{\ast })=h(P)+1.\end{array}$$

The height $h_{\Sigma }(L)$ of a language is the minimum over expressions defining it. This is distinct from the height of a particular expression. For instance, the expression $(a^{\ast }{)}^{\ast }$ has height two, but its language has a simpler expression. More strikingly, ${\Sigma }^{\ast }=\neg 0$ has height zero even though it contains words of every length. Complement preserves the stars already in its operand; it does not simply delete them.

Over $\{a\}$, the even-length language $(aa{)}^{\ast }$ has generalized height exactly one. To see why it is not height zero, identify unary words with their lengths. Finite and cofinite subsets of $\mathbb{N}$ are closed under union and complement, and under the sumset operation corresponding to concatenation. For concatenation, a nonempty finite set plus a cofinite set is cofinite; two cofinite sets also have cofinite sum; empty operands give the empty set. Induction shows that every unary height-zero language is finite or cofinite. Even lengths are neither. (OpenAI, 2026)

🏷️ Three constructions in one family

Uniform height bound, as stated in the strongest manuscript

Every regular language over every finite alphabet $\Sigma$ has a generalized expression over that same alphabet with

$$h_{\Sigma }(L)\le 3.$$

Complements remain relative to ${\Sigma }^{\ast }$. There is no asserted useful bound on expression length or construction time. (OpenAI, 2026)

The three manuscripts prove independent bounds by different constructions:

Bound	Main construction	Iteration accounting
Thirteen	Prediction trials and complete decision histories	Two outer splits and two splits for each of five residual witness types
Four	Affine correction and periodic transport at several scales	Three splits, giving $0\to 2\to 3\to 4$
Three	Arbitrary-function shift tables and a decoder controlling all candidate cuts	Two splits, giving $0\to 2\to 3$

The stronger numerical bound does not serve as a premise in the other proofs. The family establishes an absolute upper bound; it does not prove that some language requires height two or three, determine the minimum height of a given language, or settle whether one always suffices. Ordinary star-height lower bounds concern expressions without complement and cannot simply be imported. (OpenAI, 2026a) (OpenAI, 2026b) (OpenAI, 2026c)

We explain the common splitting mechanism and the main improvement in the height-three paper. Only finite state transformations and elementary finite linear algebra are needed for these interfaces; the broader algebraic classification of regular languages is not developed here.

🏷️ Word values and uniquely parsed episodes

A word acts on the state set of its recognizing automaton. These finitely many transformations form a multiplication table $M$ with identity, with products taken in reading order. Write $T(w)$ for the transformation induced by $w$. Acceptance depends only on $T(w)$, so it suffices to define the fibers $T^{-1}(m)$.

There is no cancellation assumption: two transformations may have the same product after composition without being equal. The elementary periodicity fact used later is that, for any fixed $c\in M$, the sequence $1,c,c^2,\dots$ is eventually periodic. Among its first $|M|+1$ terms two coincide; multiplying further preserves that repetition.

An episode language $E\subseteq {\Sigma }^{+}$ is a prefix code: no episode is a proper prefix of another. This makes factorization into episodes unique. Indeed, the first episodes in two proposed factorizations are prefix-comparable, hence equal; cancel the equal words and continue. Every input will be parsed into complete episodes and a final remainder with no episode prefix.

Each episode $e$ determines a total update $G_e:S\to S$ on a finite state space. The graph language from $x$ to $y$ on a domain $D^{\ast }$ is the set of episode sequences in $D^{\ast }$ whose composite update sends $x$ to $y$. The domain is part of the assertion, and the update is determined by the episode rather than by an expression’s guessed metadata.

🏷️ The split identity

Let $D^{\prime }\subseteq D\subseteq E$. Suppose computations on skipped episodes from $D^{\prime }$ are already expressed by languages $W_{x,y}$. To process the others, seek a prefix test $P_x$ and suffix test $Q_y$ with two properties:

• Whenever an accepted concatenation $uv\in P_x{Q}_y$ starts at a true boundary of a word in $D^{\ast }$, it consumes exactly its first episode and transmits the true update from $x$ to $y$.
• Every episode outside $D^{\prime }$ admits such a cut for every input state $x$.

The first condition is universal over independently chosen prefix and suffix witnesses. Correctness only when their guesses agree would not justify ordinary language concatenation.

Define the finite unions

$$\begin{array}{rl}{A}_x& =\bigcup _i{W}_{x,i}{P}_i,\\ B& =\bigcup _{j,i}{Q}_j{W}_{j,i}{P}_i,\\ C_y& =\bigcup _l{Q}_l{W}_{l,y}.\end{array}$$

The desired graph language is

$$R_{x,y}=D^{\ast }\cap (W_{x,y}\cup A_x{B}^{\ast }{C}_y).$$

For soundness, begin at the input’s actual start. The first $W$ factor consumes whole episodes by the prefix-code property. The following $P,Q$ pair consumes exactly one episode by the first split condition. Repeat to align every subsequent factor and propagate its state. Merely intersecting with $D^{\ast }$ does not align arbitrary interior factors; this induction does.

Conversely, follow the true episode computation, group runs of skipped episodes into $W$ factors, and choose a cut in each remaining episode. If all episodes are skipped, use $W_{x,y}$ directly. The formula also handles the empty sequence.

If $D,P_x,Q_y$ have height at most one and $W_{x,y}$ have height at most $H$, then $D^{\ast }$ has height at most two and the central star has height at most $1+\max (1,H)$. Thus

$$h(R_{x,y})\le \max (2,H+1).$$

This accounts for the progression $0\to 2\to 3$ once two valid splits and their component height bounds have been supplied. (OpenAI, 2026c)

🏷️ Affine corrections without another star

The construction changes updates to affine maps

$$G_e(v)=v{L}_e+b_e$$

on a finite vector space. Their composite along a fixed word is again affine, $v\mapsto vL+b$, with $L$ the product of the linear parts. Its output at zero is $b$. Hence the graph language for the unshifted computation $xL=y$ is

$$\bigcup _b(R_{x,y+b}\cap R_{0,b}).$$

Both conditions must hold on the same word, which explains the intersection. Only finite Boolean operations occur, so this recovery adds no star. Invertibility is unnecessary.

Affine maps can also be represented linearly on one extra coordinate:

$$(v,c)⟼(vL+cb,c).$$

Restricting to $c=1$ recovers the affine action, and composition respects this representation. These identities allow the inner and outer episode computations to use different finite state spaces while retaining compatible update information. (OpenAI, 2026c)

🏷️ A shift table hides one unreadable interval

A cut may cross one interval whose product neither side can read in full. The height-three construction handles arbitrary tables, not only a sequence of actual transformation products.

Fix a finite nonempty entry set $A$ and a finite vector space $S$. The shift-table lemma selects a length $l$, depending only on their sizes, such that for every table

$$f:A^l⟶\mathrm{End}(S)$$

there is one correction table $\beta :A^l\to S$ with the following property. For every tuple $\mathbf{a}$ and input $x$, some coordinate $i$ can vary freely while

$$xf(\mathbf{a}[i\leftarrow b])+\beta (\mathbf{a}[i\leftarrow b])$$

remains constant for $b\in A$. The correction is chosen before $x$; the successful coordinate may depend on both $x$ and the tuple.

Here is the probabilistic mechanism. Let $a=|A|$ and $q=|S|$, and choose the values of $\beta$ independently and uniformly. Given its value at a tuple’s center, constancy on one coordinate line forces the values at its other $a-1$ cells. It succeeds with probability $q^{1-a}$. The $l$ lines share only the center, so the probability that none succeeds is

$$p_l=(1-q^{1-a}{)}^l.$$

A bad event depends only on cells within Hamming distance one of its center. Its dependency neighborhood has size at most

$$D_l=q(1+la+l^2{a}^2).$$

This grows quadratically, while $p_l$ decays exponentially. Choosing $l$ so that $p_l\le 1/[4(D_l+1)]$ allows the finite local-lemma argument to avoid every bad event simultaneously, for all inputs and tuples. If $a=1$ or $q=1$, constancy is immediate. The resulting length is uniform over the table $f$. (OpenAI, 2026c)

This stronger quantifier order is needed because the suffix later tabulates updates at every hypothetical prefix value, including values no actual prefix realizes. A lemma valid only on feasible tuples would not cover that table.

🏷️ Timing, false origins, and the second split

The table handles information at a cut; it does not determine where the episode starts or ends. A finite clock restricts independently successful tags to matching tags or one controlled unequal pair. An affine translation handles the unequal pair. Separate endpoint guards are required before both tests can use the same total time.

When tags match, local markers supply interval boundaries. If a marker is absent, a long periodic region allows cuts to move while the relevant transformation product stays fixed. Eventual periodicity replaces any need to cancel transformation factors.

The first split can fail on an intrinsic exceptional episode class. The second uses earlier cuts chosen from a finite list containing many copies of each required metadata tuple. The decoder must count false origins over all ordered pairs of candidate cuts, including incorrect metadata. Bounding ambiguity only for the true tuple would not leave a usable copy of every required kind.

Two endpoint searches play different roles. A smaller search either finds a bounded end marker or follows a periodic seed to its first mismatch. A larger search supplies a clock anchor. If a nearby origin lacks the larger marker, the smaller searches share a periodic continuation and a common mismatch. If all larger markers are present, their anchors are bounded data. The suffix first identifies the origin and then checks its exact end. The manuscript’s full-candidate ambiguity estimate makes the second split complete on the exceptional class. These timing and decoding estimates are substantive inputs beyond the shift-table lemma. (OpenAI, 2026c)

The thirteen-height proof uses full decision histories to handle five residual witness types, including leaves that no actual prefix can reach. The four-height proof instead uses several scales of periodic boundary movement and two differently ordered residual decoders. Those methods motivate the shared split framework, but their detailed constructions are not interchangeable with the two-split decoder. (OpenAI, 2026a) (OpenAI, 2026b)

🏷️ Compiling tests over the original alphabet

Finite-state decidability alone would establish regularity of a component test, not height at most one. The stronger fact is that each standalone test, even with false guessed data, lies in a finite union of templates

$$a{c}^{i}b,i\ge 0,$$

with fixed words $a,b,c$ and $c\ne \epsilon$. Its own exact-end rule permits only one unbounded periodic middle.

On a template, bounded windows near the ends eventually stabilize. Products crossing the middle have form $uT(c{)}^{i-i_0}v$, hence are eventually periodic in $i$. Fixed-modulus and periodic-agreement checks are also eventually periodic, after finitely many phase cases. Finite universal and uniqueness tests preserve this property.

An ultimately periodic accepted exponent set is a finite set plus finitely many progressions $i_1+p\mathbb{N}$. Each progression gives the height-one expression

$$a{c}^{i_1}(c^p{)}^{\ast }b.$$

The incomplete remainder has the same kind of height-one description. The inner split begins with no skipped episodes and gives height two; affine recovery preserves that bound. These become the outer split’s skipped computations, giving height three. A finite union of concatenations with remainder fibers adds no star.

All tags, states, and residues are finite indices of expressions, not additional input letters. Arbitrary inverse substitutions cannot be used as a shortcut to an original-alphabet height bound. If $\Sigma$ is empty, its only words are the empty word and its only languages are already height zero. (OpenAI, 2026c)

🏷️ Key steps and proof outlines

Counting ambiguity over every possible cut

The height-three paper’s decoder must work with ordinary concatenation of independently accepted prefix and suffix languages. The suffix cannot assume the prefix used the correct metadata. “Recovering the cut on exceptional episodes” therefore counts false origins over all ordered pairs of candidate slots.

Let $\mathcal{P}$ be the finite set of slot offsets, $t$ the true origin, and $p$ the actual prefix slot. If the suffix interprets its beginning as slot $p^{\prime }$, it infers origin $t+p-p^{\prime }$. The schedule makes all nonzero ordered differences $p-p^{\prime }$ distinct as integers and modulo a clock modulus $B$, and widely separated. This turns geometric separation of search windows into a count of bad pairs, including pairs of incorrectly labeled slots.

Two end searches are used at every candidate origin: a smaller one and a larger one. Their search radii are chosen so that any marker eligible for a smaller search at one candidate is eligible for the larger search at every nearby candidate. Consequently, if one larger search is absent, all smaller searches are absent. The long marker-free seed intervals then have overlapping short periodic continuations; the periodic-overlap lemma makes those continuations equal, so they share a first subsequent mismatch $q_0$.

If larger searches are present, their markers lie in a bounded interval and are separated by a fixed marker spacing. There are at most seven such positions; when needed, add the one shared mismatch. The proof uses a convenient upper bound of twenty anchors. Even an arbitrarily remote mismatch contributes only one anchor, so the number of cases stays bounded independently of episode length. (OpenAI, 2026c)

The multiplicity budget leaves a valid copy of each kind

For a fixed actual episode, the proof charges exceptional false origins to three causes. Changes in an end search contribute at most four ordered pairs: two searches and two possible boundary crossings, with at most one pair for each. At a fixed anchor, the clock lemma contributes at most $c_{\mathrm{cl}}\log (2m)$ pairs, where $m$ is the schedule parameter and $c_{\mathrm{cl}}$ is its fixed constant. For each of the $g+1$ inner-marker labels, there are at most three further pairs: one possible crossing of a left endpoint and two possible first markers near a moving right endpoint.

Thus the total is at most

$$4+20(c_{\mathrm{cl}}\log (2m)+3(g+1))<\mu ,$$

where the schedule provides $\mu$ copies of every required metadata kind. The inequality leaves at least one copy of each kind without a false competing origin. Its usefulness depends on counting all pairs before identifying the correct kind; a bound only for the true metadata would not protect a suffix from independently chosen false metadata.

The decoder still must check the end. It first obtains the bounded searches and, in the marker-free case, the shared periodic mismatch information needed for the origin test. It asks for a unique origin only after these data are available, and then verifies that origin’s exact end. If it guessed the end first and discarded the true origin for not matching that guess, uniqueness could certify a false origin. The order of these tests prevents that circularity.

Why this decoder saves an entire nested star

The exceptional class is the part on which the first splitting construction is incomplete. The full-candidate count makes the second split complete on that class. Once both prefix/suffix tests are individually shown to have height at most one, the split identity yields successive bounds $0\to 2\to 3$. The affine correction is recovered by intersections on the same word and therefore adds no iteration.

To see the separate compilation obligation concretely, suppose one standalone test has inputs of form $a{c}^{i}b$, with fixed words $a,b,c$ and $c\ne \epsilon$. Finite-state products along the periodic middle eventually repeat as $i$ increases; bounded endpoint windows and residue tests also eventually repeat. Accepted exponents are therefore a finite set together with finitely many arithmetic progressions. A progression $i=i_0+pj$ becomes $a{c}^{i_0}(c^p{)}^{\ast }b$, of height one. This argument applies even to tests with incorrect guessed metadata; merely proving that successful correctly paired tests are regular would not bound the heights of the operands in the split formula.

The earlier companions close the same kind of independently chosen cut problem with larger collections of residual cases: five witness types and complete decision histories for height thirteen, and a three-split periodic-transport construction for height four. Their greater height counts reflect those additional splits, while the height-three proof uses the stronger arbitrary-table shift lemma and the all-candidate ambiguity bound to finish in two. These are independently attributed source constructions, not deductions that a finite automaton automatically has a low-height expression. (OpenAI, 2026a; OpenAI, 2026b; OpenAI, 2026c)

🏷️ Reading connections

Two-way automata measures finite-state representation cost, whereas this family measures nested iteration with expression length unrestricted. Both use finite word computations, but a small height bound does not imply a small automaton or a short expression.

🏷️ Manuscripts and verification scope

• Finite Monoid Computations and a Uniform Generalized Star-Height Bound — pinned manuscript and companion source.
• Generalized Star Height at Most Four — pinned manuscript and companion source.
• Generalized Star Height at Most Three — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. Its selected statement is the uniform expression bound of three. This implies the weaker numerical bounds without separately formalizing every construction step in the companion methods. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Finite Monoid Computations and a Uniform Generalized Star-Height Bound.

🐻  OpenAI 2026b. Generalized Star Height at Most Four.

🐻  OpenAI 2026c. Generalized Star Height at Most Three.