Formal languages · automata theory · algebraic language theory · finite monoids

Generalized Star-Height Problem

Collaboration beta

The packet turns one long-standing question about regular expressions into several exact smaller-looking questions about two-state recurrences, return loops, parity, and finite-group accumulation. Those reformulations sharpen the search, but none yet resolves the original problem.

Reg (A) = H_{1} (A) for every finite alphabet A

Known results and sources

A visual identity for the open question of whether every regular language can be described with at most one nested layer of Kleene star.

Research problem

Exact mathematical statement

For a finite alphabet $A$ , let $h(L)$ be the least nesting depth of Kleene stars in a generalized regular expression for $L$ , where complement relative to $A^*$ does not increase the height. Write

\mathsf H_n(A)=\{L\subseteq A^*:h(L)\le n\}.

The source's pursued positive target is

\operatorname{Reg}(A)=\mathsf H_1(A)\qquad\text{for every finite alphabet }A.

A complete negative resolution would instead require a concrete regular language outside $\mathsf H_1$ together with a sound invariant or separation theorem for the full height-one normal form. The source reports neither direction complete.

Problem infographic

Problem at a glance

A four-region scientific illustration connects automata and one-layer expression loops to a two-state recurrence and ordered group-labeled blocks, with unresolved interfaces marked in amber. — Problem explainer: source-reported reformulations focus attention on two-state recurrence and ordered finite-group phases, but none resolves whether every regular language has generalized star-height at most one.

Current mathematical picture

Where work on Generalized Star-Height Problem stands

Open problem

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureDelayed boundary detection and synchronization-by-taking-code-powers

For $K=\{abb,b\}$ , synchronization delay two, and $w=abb$ , the suffix $bb\in K^2$ is misaligned with the canonical factorization, so the proposed count returns zero although the full prefix is counted. The correlated residual rectangle, one-edge even renewal, guarded parity flow, visible group fibers, ordered prefix cocycles, group-primitive screening, and a genuinely closure-stable profinite or topological separation invariant remain live within their stated scopes.

Route status · Narrowed route

Main reductionLocal-divisor narrowing

The source reports that a minimal bad morphism is a group or retains nontrivial group recurrence both off every nonunit delimiter and in an equal-token-length local-divisor layer.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeClose the correlated residual-rectangle form of the two-state matrix-star recurrence for every aperiodic recognizing monoid, including empty-word bookkeeping and both persistent diagonal recurrences.Task status · Ready to work on

Work mapped so far

Generalized Star-Height Problem in numbers

1.1kretained lines of mathematical investigation1,078 in the current working snapshot

Argument development: 874 · 81%
Explored or eliminated routes: 64 · 6%
Computational analysis: 23 · 2%
Open obligations: 44 · 4%
Definitions and setup: 73 · 7%

9selected mapped statements1routes investigated3open questions3contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedAug 30, 2026

Source recordedAug 30, 2026

Recommended next task

Close the correlated residual-rectangle form of the two-state matrix-star recurrence for every aperiodic recognizing monoid, including empty-word bookkeeping and both persistent diagonal recurrences.

Suggested move: Attempt induction on the aperiodic monoid and the two-sided ideal generated by the split-letter product, checking each identity against the exact pair-decoder formula.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

13 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded

Narrowed routeDelayed boundary detection and synchronization-by-taking-code-powers

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Close the correlated residual-rectangle form of the two-state matrix-star recurrence for every aperiodic recognizing monoid, including empty-word bookkeeping and both persistent diagonal recurrences.Suggested move: Attempt induction on the aperiodic monoid and the two-sided ideal generated by the split-letter product, checking each identity against the exact pair-decoder formula.

Ready to work on

Transfer progress between the matrix-star and one-edge renewal formulations without replacing a height-one-transparent deleted automaton by an unjustified star-free base.Suggested move: Construct the exact two-phase automaton of a first-return code and determine which residual-rectangle constraints its even-renewal language satisfies.

Ready to work on

Flatten visible and hidden finite-group accumulation when token or event labels themselves require height-one recognition, preserving order in nonabelian factors.Suggested move: Prove the visible

C_2

body-label parity interface first, then test extension and factorization-forest decompositions before attempting ordered simple-group products.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 30, 2026

Current statusOpen problem

The scoped literature search found no regular language proved to require generalized star height greater than one and no proof that height one suffices universally. The cited ACM survey states the exact question as open, and later work proves additional height-one subclasses while continuing to describe the general problem as long-standing open. This status is a conservative inference and should be refreshed if a resolving claim appears.

[1][3][4]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2018
Peer reviewedDaviaud and Paperman gave effective equational characterizations for classes generated by languages of the form u-star, a special step toward—but not a resolution of—the generalized star-height problem.[4]
2016
PreprintBourne and Ruškuc proved height at most one for several factor-counting families and for languages recognized by Rees zero-matrix semigroups over abelian groups.[3]
1992
Peer reviewedPin, Straubing, and Thérien proved closure and height-one results for group and wreath-product classes, representing every regular language as the inverse image of a restricted-star-height-one language.[2]
1965
Peer reviewedSchützenberger's theorem characterizes generalized star-height zero languages as those recognized by finite aperiodic monoids; this settles level zero, not whether height greater than one is ever required.[1]

Mathematical neighborhood

Related results and reusable starting points

Current focusGeneralized Star-Height Problem

Weaker or relaxed formstar-free regular languages

Generalized star-height zero is the star-free fragment and has a classical algebraic characterization; the open target asks whether one additional star layer covers every regular language.

[1]

Related problemrestricted star-height problem

Ordinary or restricted star height excludes complement from the expression operations; arbitrary restricted heights exist and restricted star height is decidable, so those results do not settle generalized star height.

[1]

Solved special caseRees zero-matrix semigroup languages over abelian groups

Languages recognized by Rees zero-matrix semigroups over abelian groups have generalized star height at most one.

[3]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetNo externally checked invariant was located that separates a concrete regular language from every generalized height-one expression.
Formalization targetNo externally checked universal construction was located that converts every regular language to a generalized expression of height at most one.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

7 standing statements2 proposed statements3 open questions1 narrowed routes

Statements by mathematical role9 selected mapped statements

theorem candidate1 of 91
reduction2 of 92
lemma2 of 92
equivalence3 of 93
special case1 of 91

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.22 displayed rows · 1 route included

retained route statementDoes every regular language have generalized star-height at most one?
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementTwo-state matrix-star interfaceintermediate
retained route statementOne-edge even-renewal interfaceintermediate
retained route statementFinite-group prefix cocyclesintermediate
retained route statementVisible quasi-star-free transferintermediate
retained route statementLocal-divisor narrowingintermediate
retained route statementGroup-primitive solved subclassintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureDelayed boundary detection and synchronization-by-taking-code-powersreported failure
Research targetClose the correlated residual-rectangle form of the two-state matrix-star recurrence for every aperiodic recognizing monoid, including empty-word bookkeeping and both persistent diagonal recurrences.open
Research targetTransfer progress between the matrix-star and one-edge renewal formulations without replacing a height-one-transparent deleted automaton by an unjustified star-free base.open
Research targetFlatten visible and hidden finite-group accumulation when token or event labels themselves require height-one recognition, preserving order in nonabelian factors.open
Narrowed routeDelayed boundary detection and synchronization-by-taking-code-powersFor $K=\{abb,b\}$ , synchronization delay two, and $w=abb$ , the suffix $bb\in K^2$ is misaligned with the canonical factorization, so the proposed count returns zero although the full prefix is counted. The correlated residual rectangle, one-edge even renewal, guarded parity flow, visible group fibers, ordered prefix cocycles, group-primitive screening, and a genuinely closure-stable profinite or topological separation invariant remain live within their stated scopes.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointClose the correlated residual-rectangle form of the two-state matrix-star recurrence for every aperiodic recognizing monoid, including empty-word bookkeeping and both persistent diagonal recurrences.

Generalized Star-Height Problem · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

The current work turns one long-standing question about regular expressions into several exact smaller-looking questions about two-state recurrences, return loops, parity, and finite-group accumulation. Those reformulations sharpen the search, but none yet resolves the original problem.

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references4 cited works · next context review by Nov 30, 2026

The mathematical context was checked on Aug 30, 2026. Status can be refreshed sooner after a material result or claim.

1
Some Open Problems in Automata and Logicsurvey or monograph · Mikołaj Bojańczyk · ACM SIGLOG News · 2014 · accessed Aug 30, 2026
2
Some results on the generalized star-height problempeer reviewed result · Jean-Éric Pin, Howard Straubing, Denis Thérien · Information and Computation · 1992 · DOI 10.1016/0890-5401(92)90063-L · accessed Aug 30, 2026
3
On the star-height of factor counting languages and their relationship to Rees zero-matrix semigroupspreprint · Tom Bourne, Nik Ruškuc · arXiv · 2016 · ARXIV 1603.06236 · accessed Aug 30, 2026
4
Classes of languages generated by the Kleene star of a wordpeer reviewed result · Laure Daviaud, Charles Paperman · Information and Computation · 2018 · DOI 10.1016/j.ic.2018.07.002 · accessed Aug 30, 2026

Important qualifications

The most recent peer-reviewed source located in this scoped search that explicitly frames the problem as long-standing open is from 2018; the 2026 status is a conservative inference from that source, the ACM open-problems survey, and the absence of a resolving source in targeted searches.
The record addresses generalized star height, where complement is allowed without increasing height; it does not conflate this with ordinary or restricted star height, whose hierarchy and decidability have different known results.
No dedicated formalization, decision procedure for generalized height, or independently reproduced separating-language computation was verified; empty readiness lists do not establish nonexistence.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces