Sternhöhe (computer science)

from Wikipedia, the free encyclopedia

The star height is a term from theoretical computer science . It specifies the maximum of all nested applications of the Kleene star operator for a regular expression .

definition

The star height sh (r) of a regular expression  r over a finite alphabet  A is recursively defined as

for all regular expressions
for all regular expressions
for all regular expressions

Building on the astrolabe is a regular language defined as the minimum of all star levels , for a regular expression to exist.

Star altitude problem

The star height problem deals with the question of whether there is a maximum star height, i.e. whether there is one with for all regular languages over a fixed alphabet . If one does not exist, can the star height of a regular language be determined algorithmically ?

Both questions have now been answered. In 1963 was LC Eggan show that such does not exist, by asking for each language with constructed. In 1988 Kosaburo Hashiguchi presented an algorithm with which the star height can be determined for a given regular language .

Generalized star height

The generalized (or generalized) star height is defined in the same way as the star height, but not via regular expressions, but via generalized regular expressions which, in addition to the normal operators, directly allow complementation ( ). The following applies:

for all generalized regular expressions
for all generalized regular expressions
for all generalized regular expressions
for all generalized regular expressions
for all generalized regular expressions

The generalized star height of a regular language is defined analogously . For example, the language has a star height of 1 while the same language has a generalized star height of 0 because of this.

Generalized star height problem

The generalized star height problem is defined analogously to the star height problem, but in contrast to it, it is still unanswered. While there are regular languages with - for example, the language - open but is still the question of whether a regular language with existed.

literature

  • Lawrence C. Eggan: Transition graphs and the star-height of regular events . In: Michigan Mathematical Journal 10, 1963, 4, ISSN  0026-2285 , pp. 385-397, online (PDF; 1.2 MB), acc. August 8, 2010 .
  • Kosaburo Hashiguchi: Algorithms for Determining Relative Star Height and Star Height . In: Information and computation 78, 1988, 2, ISSN  0890-5401 , pp. 124-169.
  • Jean-Eric Pin, Howard Straubing, Denis Thérien: Some results on the generalized star-height problem . In: Information and Computation 101, 1992, 2, ISSN  0890-5401 , pp. 219-250, liafa.jussieu.fr