Sternhöhe (Informatik)

Die Sternhöhe ist ein Begriff aus der Theoretischen Informatik. Sie gibt zu einem regulären Ausdruck das Maximum aller verschachtelten Anwendungen des Kleene-Stern-Operators an.

Definition

Die Sternhöhe ${\displaystyle \operatorname {sh} (r)}$ eines regulären Ausdrucks r über einem endlichen Alphabet A ist rekursiv definiert als

${\displaystyle \operatorname {sh} (\emptyset )=0}$

${\displaystyle \operatorname {sh} (\varepsilon )=0}$

${\displaystyle \operatorname {sh} (x)=0\quad \forall x\in A}$

${\displaystyle \operatorname {sh} (v\cdot w)=\max(\operatorname {sh} (v),\operatorname {sh} (w))}$ für alle regulären Ausdrücke ${\displaystyle v,w}$

${\displaystyle \operatorname {sh} (v|w)=\max(\operatorname {sh} (v),\operatorname {sh} (w))}$ für alle regulären Ausdrücke ${\displaystyle v,w}$

${\displaystyle \operatorname {sh} (v^{\star })=\operatorname {sh} (v) 1}$ für alle regulären Ausdrücke ${\displaystyle v}$

Darauf aufbauend ist die Sternhöhe ${\displaystyle \operatorname {sh} (L)}$ einer regulären Sprache ${\displaystyle L}$ definiert als das Minimum aller Sternhöhen ${\displaystyle n}$, für das ein regulärer Ausdruck ${\displaystyle r\in L}$ mit ${\displaystyle \operatorname {sh} (r)=n}$ existiert.

Sternhöhenproblem

Das Sternhöhenproblem behandelt die Frage, ob es eine maximale Sternhöhe gibt, also ob ein ${\displaystyle n}$ mit ${\displaystyle \operatorname {sh} (L)\leq n}$ für alle regulären Sprachen ${\displaystyle L}$ über einem festen Alphabet ${\displaystyle A}$ existiert. Falls ein solches ${\displaystyle n}$ nicht existiert, lässt sich dann die Sternhöhe einer regulären Sprache algorithmisch bestimmen?

Beide Fragen sind mittlerweile beantwortet. Im Jahre 1963 konnte L. C. Eggan zeigen, dass ein solches ${\displaystyle n}$ nicht existiert, indem er für jedes ${\displaystyle n\geq 0}$ eine Sprache ${\displaystyle L_{n}}$ mit ${\displaystyle \operatorname {sh} (L)=n}$ konstruierte. Kosaburo Hashiguchi stellte 1988 einen Algorithmus vor, mit dem sich zu einer gegebenen regulären Sprache ${\displaystyle L}$ die Sternhöhe ${\displaystyle \operatorname {sh} (L)}$ bestimmen lässt.

Verallgemeinerte Sternhöhe

Die verallgemeinerte (oder auch generalisierte) Sternhöhe ${\displaystyle \operatorname {gsh} (r)}$ ist analog zur Sternhöhe definiert, allerdings nicht über regulären Ausdrücken, sondern über verallgemeinerten regulären Ausdrücken, welche zusätzlich zu den normalen Operatoren direkt die Komplementierung (${\displaystyle \neg }$) erlauben. Es gilt also:

${\displaystyle \operatorname {gsh} (\emptyset )=0}$

${\displaystyle \operatorname {gsh} (\varepsilon )=0}$

${\displaystyle \operatorname {gsh} (x)=0\quad \forall x\in A}$

${\displaystyle \operatorname {gsh} (\lnot v)=\operatorname {gsh} (v)}$ für alle verallgemeinerten regulären Ausdrücke ${\displaystyle v}$

${\displaystyle \operatorname {gsh} (v\cdot w)=\max(\operatorname {gsh} (v),\operatorname {gsh} (w))}$ für alle verallgemeinerten regulären Ausdrücke ${\displaystyle v,w}$

${\displaystyle \operatorname {gsh} (v|w)=\max(\operatorname {gsh} (v),\operatorname {gsh} (w))}$ für alle verallgemeinerten regulären Ausdrücke ${\displaystyle v,w}$

${\displaystyle \operatorname {gsh} (v\cap w)=\max(\operatorname {gsh} (v),\operatorname {gsh} (w))}$ für alle verallgemeinerten regulären Ausdrücke ${\displaystyle v,w}$

${\displaystyle \operatorname {gsh} (v^{\star })=\operatorname {gsh} (v) 1}$ für alle verallgemeinerten regulären Ausdrücke ${\displaystyle v}$

Analog ist die verallgemeinerte Sternhöhe ${\displaystyle \operatorname {gsh} (L)}$ einer regulären Sprache ${\displaystyle L}$ definiert. Beispielsweise hat die Sprache ${\displaystyle L(\Sigma ^{*})}$ die Sternhöhe 1, während dieselbe Sprache wegen ${\displaystyle L(\Sigma ^{*})=L(\neg \emptyset )}$ die verallgemeinerte Sternhöhe 0 hat.

Verallgemeinertes Sternhöhenproblem

Das verallgemeinerte Sternhöhenproblem ist analog zum Sternhöhenproblem definiert, aber im Gegensatz zu diesem noch unbeantwortet. Zwar gibt es reguläre Sprachen ${\displaystyle L}$ mit ${\displaystyle \operatorname {gsh} (L)=1}$, zum Beispiel die Sprache ${\displaystyle {\mathcal {L}}((aa)^{*})}$. Offen ist aber noch die Frage, ob auch eine reguläre Sprache ${\displaystyle L}$ mit ${\displaystyle \operatorname {gsh} (L)\geq 2}$ existiert.

Literatur

• Lawrence C. Eggan: Transition graphs and the star-height of regular events. In: Michigan Mathematical Journal 10, 1963, 4, ISSN 0026-2285, S. 385–397, online (PDF; 1,2 MB), acc. 8. August 2010.
• Kosaburo Hashiguchi: Algorithms for Determining Relative Star Height and Star Height. In: Information and computation 78, 1988, 2, ISSN 0890-5401, S. 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, S. 219–250, liafa.jussieu.fr