*(English)*Zbl 1082.20041

Let ${\Sigma}$ be a given alphabet. The ‘star height’ of a rational expression over ${\Sigma}$ is defined inductively as follows: $\mathrm{\mathbf{s}\mathbf{h}}\left(\varnothing \right):=0$; $\mathrm{\mathbf{s}\mathbf{h}}\left(a\right):=0$ for all $a\in {\Sigma}$; and if $r$ and $s$ are regular expressions over ${\Sigma}$, then $\mathrm{\mathbf{s}\mathbf{h}}\left(rs\right)=\mathrm{\mathbf{s}\mathbf{h}}(r\cup s):=max\left\{\mathrm{\mathbf{s}\mathbf{h}}\right(r),\mathrm{\mathbf{s}\mathbf{h}}(s\left)\right\}$, and $\mathrm{\mathbf{s}\mathbf{h}}\left({r}^{*}\right):=\mathrm{\mathbf{s}\mathbf{h}}\left(r\right)+1$. A language $L$ is called ‘recognizable’ over ${\Sigma}$ if $L=L\left(r\right)$ for some regular expression $r$ over ${\Sigma}$.

A natural classification of such languages is obtained as follows: for every nonnegative integer $k$, define ${\mathcal{L}}_{k}:=\{L\left(r\right)\mid \mathrm{\mathbf{s}\mathbf{h}}\left(r\right)\le k\}$.

The star height of a recognizable language $L$, $\mathrm{\mathbf{s}\mathbf{h}}\left(L\right)$, is the smallest $k$ such that $L\in {\mathcal{L}}_{k}$. The language classes ${\mathcal{L}}_{0},{\mathcal{L}}_{1},\cdots $ form a hierarchy that was shown by Eggan to be infinite. In other words, for every $k$, ${\mathcal{L}}_{k}\subset {\mathcal{L}}_{k+1}$ but ${\mathcal{L}}_{k}\ne {\mathcal{L}}_{k+1}$. Eggan’s proof, which uses an alphabet of cardinality ${2}^{k+1}-1$, got improved by Dejean and Schützenberger who used an alphabet of two letters.

An outstanding problem is whether one can decide if a language has star height $k$. This is equivalent to the question “Is ${\mathcal{L}}_{k}$ decidable?” or “Does there exist an algorithm which enables us to test if a language is or is not in ${\mathcal{L}}_{k}$?”. This is referred to as the ‘star height problem’ which was raised by Eggan in 1963 and which has received a lot of attention in the past several years. The class ${\mathcal{L}}_{0}$ consists of the finite languages, and Hashiguchi answered the question positively in 1982 for star height one, and in 1988 for arbitrary star height.

Hashiguchi’s proof of the star height problem is very complicated. In this very interesting paper, the author gives a new proof by reducing the star height problem to the limitedness of his so-called ‘nested distance desert automata’. This notion is introduced as a generalization of both the notion of ‘distance automata’ previously introduced by Hashiguchi and the notion of ‘desert automata’ previously introduced independently by Bala and the author. Such automata compute mappings from the free monoid over ${\Sigma}$ to the set of positive integers. They are called ‘limited’ if the range of the computed mapping is finite.

Limitedness of nested distance desert automata turns out to be PSPACE-complete. The author’s construction gives the first upper complexity bound for the star height problem. More precisely, he shows that given a nonnegative integer $k$, it is decidable in ${2}^{{2}^{\mathcal{O}\left(n\right)}}$ space whether the language accepted by an $n$-state nondeterministic automaton has star height less than $k$. (Also submitted to MR.)

##### MSC:

20M35 | Semigroups in automata theory, linguistics, etc. |

68Q17 | Computational difficulty of problems |

68Q70 | Algebraic theory of languages and automata |

20M05 | Free semigroups, generators and relations, word problems |