Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1082.20041
Kirsten, Daniel
Distance desert automata and the star height problem. (English)
[J] Theor. Inform. Appl. 39, No. 3, 455-509 (2005). ISSN 0988-3754; ISSN 1290-385X/e

Let $\Sigma$ be a given alphabet. The `star height' of a rational expression over $\Sigma$ is defined inductively as follows: $\bold{sh}(\emptyset):=0$; $\bold{sh}(a):=0$ for all $a\in\Sigma$; and if $r$ and $s$ are regular expressions over $\Sigma$, then $\bold{sh}(rs)=\bold{sh}(r\cup s):=\max\{\bold{sh}(r),\bold{sh}(s)\}$, and $\bold{sh}(r^*):=\bold{sh}(r)+1$. A language $L$ is called `recognizable' over $\Sigma$ if $L=L(r)$ for some regular expression $r$ over $\Sigma$.\par A natural classification of such languages is obtained as follows: for every nonnegative integer $k$, define ${\cal L}_k:=\{L(r)\mid\bold{sh}(r)\leq k\}$.\par The star height of a recognizable language $L$, $\bold{sh}(L)$, is the smallest $k$ such that $L\in{\cal L}_k$. The language classes ${\cal L}_0,{\cal L}_1,\dots$ form a hierarchy that was shown by Eggan to be infinite. In other words, for every $k$, ${\cal L}_k\subset{\cal L}_{k+1}$ but ${\cal L}_k\not={\cal 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.\par An outstanding problem is whether one can decide if a language has star height $k$. This is equivalent to the question ``Is ${\cal L}_k$ decidable?'' or ``Does there exist an algorithm which enables us to test if a language is or is not in ${\cal 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 ${\cal 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.\par 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.\par 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^{{\cal O}(n)}}$ space whether the language accepted by an $n$-state nondeterministic automaton has star height less than $k$. (Also submitted to MR.)
[Francine Blanchet-Sadri (Greensboro)]

MSC 2000:: *20M35 Semigroups in automata theory, linguistics, etc.
68Q17 Computational difficulty of problems
68Q70 Algebraic theory of automata
20M05 Free semigroups

Keywords: recognizable languages; star heights; distance automata; desert automata; hierarchies; decidability; star height problem; free monoids

Cited in: Zbl 1165.68038

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]