Skip to content

Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.

OAI-26 family 134: generalized star height at most three

Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This is a source-pinned account of the publisher's theorem claim, not an independent verification.

The question in plain language

A regular expression describes a language of finite strings. The Kleene star means “repeat a pattern any number of times,” while union and concatenation combine patterns. When expressions can additionally take complements, a longstanding question asks whether arbitrarily many nested stars are truly necessary to describe some regular languages.

Family 134 claims that three nested stars always suffice for every regular language over any finite alphabet.

A small example

For alphabet \(\Sigma=\{a,b\}\), the expression \((ab)^*\) describes zero or more copies of the block \(ab\) and has star nesting depth one. The complement \(\Sigma^*\setminus(ab)^*\) describes all remaining strings; complement is allowed in the generalized regular-expression model.

Star height measures the maximum number of stars nested along a syntax-tree path, not how many stars appear anywhere in the expression. For example, \((a^*b)^*\) has nesting depth two. Equivalent expressions can have different heights, so the generalized star height of a language minimizes this depth across all equivalent generalized expressions.

What is known

The protected Family 134 catalogue lists three manuscripts: Finite Monoid Computations and a Uniform Generalized Star-Height Bound, Generalized Star Height at Most Four, and Generalized Star Height at Most Three. These titles indicate successive proposed bounds, but their proof dependencies and revisions must be verified from the primary texts.

The pinned publisher overview claims that for every regular language \(L\subseteq\Sigma^*\) over a finite alphabet there exists a generalized regular expression \(E\) satisfying

\[ L(E)=L,\qquad \mathrm{sh}(E)\le 3. \]

The permitted operations are union, concatenation and complement over the same alphabet, in addition to Kleene star. This is an absolute bound independent of automaton size, not merely a function of the number of states or alphabet cardinality.

The claimed theorem resolves the uniform-boundedness version of the generalized star-height problem. It does not say that every regular language has generalized star height zero or one, nor does the pinned overview establish that the bound three is optimal.

GCL verification state

Source lock: openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. The protected catalogue identifies three PDFs and the pinned overview attributes the uniform bound of three to the publisher.

This documentary pass has not reconstructed the monoid-based construction, checked the complement convention, verified the inductive reduction from four stars to three, or tested the resulting expression for language equivalence. No Family 134-specific accepted critical proof audit, Comparator receipt, Lean elaboration, or MATHCERT certificate is asserted.

What remains

Read all three pinned manuscripts and identify the exact generalized-expression syntax, including constants, empty word, empty language, Boolean operations and alphabet-relative complement. Reconstruct the algebraic/finite-monoid lemmas and the step providing the absolute three-level bound. Verify that complement does not conceal additional Kleene-star layers or an alphabet extension.

Independently inspect small automata, construct equivalent generalized expressions and calculate syntax-tree star height. Extract any stated effectiveness or size bounds: existence of bounded-depth expressions alone does not guarantee a polynomial-size translation.

Complete mathematical Markdown/MkDocs checks, source-critical review and protected merge/readback. Documentary admission does not certify the generalized star-height theorem.

Sources and claim boundaries

Boundary: NO_CERTIFICATION. The universal star-height bound remains a publisher-reported claim requiring independent mathematical verification.


Indexed primary manuscript paths: