Star height

In mathematics, the star height "h"("E") of a regular expression "E" over a finite alphabet "A" is defined as follows [ The definition given here is that of "generalized star height" since regular expressions are allowed to use the "complement" operator.] :

* "h"(∅) = 0, "h"(ε) = 0, "h"("a") = 0 for all "a" ∈ "A".
* "h"("E" ∪ "F") = "h"("EF") = max("h"("E"), "h"("F"))
* "h"("E^c") = "h"("E")
* "h"("E"^*) = "h"("E") + 1

The star height "h"("L") of a regular language "L" is defined as the minimum of the star heights of all regular expressions representing "L".

It can be shown that a language "L" has star height 0 iff its syntactic monoid is aperiodic (Schützenberger 1965).

See also star height problem and generalized star height problem.

Notes