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 <math>\operatorname{sh}(r)</math> eines regulären Ausdrucks r über einem endlichen Alphabet A ist rekursiv definiert als

<math>\operatorname{sh}(\emptyset) = 0</math>

<math>\operatorname{sh}(\varepsilon) = 0</math>

<math>\operatorname{sh}(x) = 0 \quad \forall x \in A</math>

<math>\operatorname{sh}(v\cdot w) = \max(\operatorname{sh}(v),\operatorname{sh}(w))</math> für alle regulären Ausdrücke <math>v, w</math>

<math>\operatorname{sh}(v | w) = \max(\operatorname{sh}(v),\operatorname{sh}(w))</math> für alle regulären Ausdrücke <math>v, w</math>

<math>\operatorname{sh}(v^\star) = \operatorname{sh}(v) + 1</math> für alle regulären Ausdrücke <math>v</math>

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

Sternhöhenproblem

Das Sternhöhenproblem behandelt die Frage, ob es eine maximale Sternhöhe gibt, also ob ein <math>n</math> mit <math>\operatorname{sh}(L)\leq n</math> für alle regulären Sprachen <math>L</math> über einem festen Alphabet <math>A</math> existiert. Falls ein solches <math>n</math> 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 <math>n</math> nicht existiert, indem er für jedes <math>n \geq 0</math> eine Sprache <math>L_n</math> mit <math>\operatorname{sh}(L)=n</math> konstruierte. Kosaburo Hashiguchi stellte 1988 einen Algorithmus vor, mit dem sich zu einer gegebenen regulären Sprache <math>L</math> die Sternhöhe <math>\operatorname{sh}(L)</math> bestimmen lässt.

Verallgemeinerte Sternhöhe

Die verallgemeinerte (oder auch generalisierte) Sternhöhe <math>\operatorname{gsh}(r)</math> 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 (<math>\neg</math>) erlauben. Es gilt also:

<math>\operatorname{gsh}(\emptyset) = 0</math>

<math>\operatorname{gsh}(\varepsilon) = 0</math>

<math>\operatorname{gsh}(x) = 0 \quad \forall x \in A</math>

<math>\operatorname{gsh}(\lnot v) = \operatorname{gsh}(v) </math> für alle verallgemeinerten regulären Ausdrücke <math>v</math>

<math>\operatorname{gsh}(v\cdot w) = \max(\operatorname{gsh}(v),\operatorname{gsh}(w))</math> für alle verallgemeinerten regulären Ausdrücke <math>v, w</math>

<math>\operatorname{gsh}(v | w) = \max(\operatorname{gsh}(v),\operatorname{gsh}(w))</math> für alle verallgemeinerten regulären Ausdrücke <math>v, w</math>

<math>\operatorname{gsh}(v\cap w) = \max(\operatorname{gsh}(v),\operatorname{gsh}(w))</math> für alle verallgemeinerten regulären Ausdrücke <math>v, w</math>

<math>\operatorname{gsh}(v^\star) = \operatorname{gsh}(v) + 1</math> für alle verallgemeinerten regulären Ausdrücke <math>v</math>

Analog ist die verallgemeinerte Sternhöhe <math>\operatorname{gsh}(L)</math> einer regulären Sprache <math>L</math> definiert. Beispielsweise hat die Sprache <math>L(\Sigma^*)</math> die Sternhöhe 1, während dieselbe Sprache wegen <math>L(\Sigma^*) = L(\neg \emptyset)</math> 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 <math>L</math> mit <math>\operatorname{gsh}(L)=1</math>, zum Beispiel die Sprache <math>\mathcal{L}((aa)^*)</math>. Offen ist aber noch die Frage, ob auch eine reguläre Sprache <math>L</math> mit <math>\operatorname{gsh}(L)\geq 2</math> existiert.

Literatur

Lawrence C. Eggan: Transition graphs and the star-height of regular events. In: Michigan Mathematical Journal 10, 1963, 4, {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|0026-2285|0}}{{#ifeq:1|0|[!]

}}{{#ifeq:0|1

        |{{#switch:00
                  |11= (print/online)
                  |10= (print)
                  |01= (online)
          }}

}}{{#ifeq:0|0

        |{{#ifeq:0|0
              |{{#if:{{#invoke:URIutil|isISSNvalid|1=0026-2285}}
                    |
                    |{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}

}}, 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, {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|0890-5401|0}}{{#ifeq:1|0|[!]

}}{{#ifeq:0|1

        |{{#switch:00
                  |11= (print/online)
                  |10= (print)
                  |01= (online)
          }}

}}{{#ifeq:0|0

        |{{#ifeq:0|0
              |{{#if:{{#invoke:URIutil|isISSNvalid|1=0890-5401}}
                    |
                    |{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}

}}, 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, {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|0890-5401|0}}{{#ifeq:1|0|[!]

}}{{#ifeq:0|1

        |{{#switch:00
                  |11= (print/online)
                  |10= (print)
                  |01= (online)
          }}

}}{{#ifeq:0|0

        |{{#ifeq:0|0
              |{{#if:{{#invoke:URIutil|isISSNvalid|1=0890-5401}}
                    |
                    |{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}

}}, S. 219–250, liafa.jussieu.fr