Star height problem

The star height problem in

The first question was answered in the negative when in 1963, Eggan gave examples of regular languages of star height n for every n. Here, the star height h(L) of a regular language L is defined as the minimum star height among all regular expressions representing L. The first few languages found by Eggan are described in the following, by means of giving a regular expression for each language:

${\displaystyle {\begin{alignedat}{2}e_{1}&=a_{1}^{*}\\e_{2}&=\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\\e_{3}&=\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\\e_{4}&=\left(\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\left(\left(a_{8}^{*}a_{9}^{*}a_{10}\right)^{*}\left(a_{11}^{*}a_{12}^{*}a_{13}\right)^{*}a_{14}\right)^{*}a_{15}\right)^{*}\end{alignedat}}}$

The construction principle for these expressions is that expression ${\displaystyle e_{n+1}}$ is obtained by concatenating two copies of ${\displaystyle e_{n}}$, appropriately renaming the letters of the second copy using fresh alphabet symbols, concatenating the result with another fresh alphabet symbol, and then by surrounding the resulting expression with a Kleene star. The remaining, more difficult part, is to prove that for ${\displaystyle e_{n}}$ there is no equivalent regular expression of star height less than n; a proof is given in Eggan (1963).

However, Eggan's examples use a large

Their examples can be described by an

inductively defined

family of regular expressions over the binary alphabet ${\displaystyle \{a,b\}}$ as follows–cf.

${\displaystyle {\begin{alignedat}{2}e_{1}&=(ab)^{*}\\e_{2}&=\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\\e_{3}&=\left(aaaa\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}bbbb\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\right)^{*}\\\,&\cdots \\e_{n+1}&=(\,\underbrace {a\cdots a} _{2^{n}}\,\cdot \,e_{n}\,\cdot \,\underbrace {b\cdots b} _{2^{n}}\,\cdot \,e_{n}\,)^{*}\end{alignedat}}}$

Again, a rigorous proof is needed for the fact that ${\displaystyle e_{n}}$ does not admit an equivalent regular expression of lower star height. Proofs are given by Dejean & Schützenberger (1966) and by Salomaa (1981).

Computing the star height of regular languages

In contrast, the second question turned out to be much more difficult, and the question became a famous open problem in formal language theory for over two decades.

A much more efficient algorithm than Hashiguchi's procedure was devised by Kirsten in 2005.[6] This algorithm runs, for a given nondeterministic finite automaton as input, within double-exponential space. Yet the resource requirements of this algorithm still greatly exceed the margins of what is considered practically feasible.

This algorithm has been optimized and generalized to trees by Colcombet and Löding in 2008,^[7] as part of the theory of regular cost functions. It has been implemented in 2017 in the tool suite Stamina.^[8]

See also

• Generalized star height problem
• Kleene's algorithm — computes a regular expression (usually of non-minimal star height) for a language given by a deterministic finite automaton

Notes

References

• ISBN 978-0-12-115350-2. (technical report version)
• Colcombet, Thomas; Löding, Christof (2008). "The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem". Computer Science Logic. Lecture Notes in Computer Science. Vol. 5213. pp. 416–430.
  ISSN 0302-9743
  .
• Dejean, Françoise;
  doi:10.1016/S0019-9958(66)90083-0
  .
• Eggan, Lawrence C. (1963). "Transition graphs and the star-height of regular events".
  Zbl 0173.01504
  .
• McNaughton, Robert (1967). "The Loop Complexity of Pure-Group Events". Information and Control. 11 (1–2): 167–176.
  doi:10.1016/S0019-9958(67)90481-0
  .
• Zbl 0487.68063
  .