Generalized star-height problem

Unsolved problem in computer science:
Can all <a href="/facts/Regular_language/ahxw67T1">regular languages</a> be expressed using generalized regular expressions with a limited nesting depth of <a href="/facts/Kleene_star/I6SX0f2Y">Kleene stars</a>?
<a href="/facts/List_of_unsolved_problems_in_computer_science/QySnBJ5E">(more unsolved problems in computer science)</a>

The generalized star-height problem in <a href="/facts/Formal_language_theory/crDTyP8q">formal language theory</a> is the open question whether all <a href="/facts/Regular_language/ahxw67T1">regular languages</a> can be expressed using generalized regular expressions with a limited nesting depth of <a href="/facts/Kleene_star/I6SX0f2Y">Kleene stars</a>. Here, generalized regular expressions are defined like <a href="/facts/Regular_expression/KFL3veHX">regular expressions</a>, but they have a built-in complement operator. For a regular language, its <a href="/facts/Star_height/advq3Hzx">generalized star height</a> is defined as the minimum nesting depth of Kleene stars needed in order to describe the language by means of a generalized regular expression, hence the name of the problem. 
More specifically, it is an open question whether a nesting depth of more than 1 is required, and if so, whether there is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> to determine the minimum required star height.
<a href="/facts/Regular_language/ahxw67T1">Regular languages</a> of star-height 0 are also known as <a href="/facts/Star-free_language/GJyaevnF">star-free languages</a>. The theorem of <a href="/facts/Marcel-Paul_Sch%C3%BCtzenberger/aF62Lo9H">Schützenberger</a> provides an algebraic characterization of star-free languages by means of aperiodic <a href="/facts/Syntactic_monoid/7khpKalF">syntactic monoids</a>. In particular star-free languages are a proper decidable subclass of regular languages.

Generalized star-height problem open-in-new

Generalized star-height problem