In formal language theory, the generalized star-height problem is the open question whether all regular languages can be expressed using generalized regular expressions with a limited nesting depth of Kleene stars. Here, generalized regular expressions are defined like regular expressions, but with a built-in complement operator. For a regular language, its generalized star height is defined as the minimum nesting depth of Kleene stars needed in order to describe the language by means of a generalized regular expression.
More specifically, it is an open question whether a nesting depth of more than 1 is required, and if so, whether there is an algorithm to determine the minimum required star height.
Regular languages of generalized star-height 0 are also known as star-free languages. A theorem of Schützenberger provides an algebraic characterization of star-free languages by means of aperiodic syntactic monoids. In particular, star-free languages are a proper decidable subclass of regular languages.
On October 6, 2026, OpenAI released hundreds of proofs to unsolved math problems generated by an internal research model. Among these were proofs that every regular language over a finite alphabet has a generalized star-height of at most thirteen, at most four, and at most three. If confirmed, these proofs resolve that every regular language has a finite generalized star-height. However, the question if every regular language has a generalized star-height of at most two, or at most one, remains open.