Die Sternhohe ist ein Begriff aus der Theoretischen Informatik Sie gibt zu einem regularen Ausdruck das Maximum aller verschachtelten Anwendungen des Kleene Stern Operators an Inhaltsverzeichnis 1 Definition 2 Sternhohenproblem 3 Verallgemeinerte Sternhohe 4 Verallgemeinertes Sternhohenproblem 5 LiteraturDefinition BearbeitenDie Sternhohe sh r displaystyle operatorname sh r nbsp eines regularen Ausdrucks r uber einem endlichen Alphabet A ist rekursiv definiert als sh 0 displaystyle operatorname sh emptyset 0 nbsp sh e 0 displaystyle operatorname sh varepsilon 0 nbsp sh x 0 x A displaystyle operatorname sh x 0 quad forall x in A nbsp sh v w max sh v sh w displaystyle operatorname sh v cdot w max operatorname sh v operatorname sh w nbsp fur alle regularen Ausdrucke v w displaystyle v w nbsp sh v w max sh v sh w displaystyle operatorname sh v w max operatorname sh v operatorname sh w nbsp fur alle regularen Ausdrucke v w displaystyle v w nbsp sh v sh v 1 displaystyle operatorname sh v star operatorname sh v 1 nbsp fur alle regularen Ausdrucke v displaystyle v nbsp Darauf aufbauend ist die Sternhohe sh L displaystyle operatorname sh L nbsp einer regularen Sprache L displaystyle L nbsp definiert als das Minimum aller Sternhohen n displaystyle n nbsp fur das ein regularer Ausdruck r L displaystyle r in L nbsp mit sh r n displaystyle operatorname sh r n nbsp existiert Sternhohenproblem BearbeitenDas Sternhohenproblem behandelt die Frage ob es eine maximale Sternhohe gibt also ob ein n displaystyle n nbsp mit sh L n displaystyle operatorname sh L leq n nbsp fur alle regularen Sprachen L displaystyle L nbsp uber einem festen Alphabet A displaystyle A nbsp existiert Falls ein solches n displaystyle n nbsp nicht existiert lasst sich dann die Sternhohe einer regularen Sprache algorithmisch bestimmen Beide Fragen sind mittlerweile beantwortet Im Jahre 1963 konnte L C Eggan zeigen dass ein solches n displaystyle n nbsp nicht existiert indem er fur jedes n 0 displaystyle n geq 0 nbsp eine Sprache L n displaystyle L n nbsp mit sh L n displaystyle operatorname sh L n nbsp konstruierte Kosaburo Hashiguchi stellte 1988 einen Algorithmus vor mit dem sich zu einer gegebenen regularen Sprache L displaystyle L nbsp die Sternhohe sh L displaystyle operatorname sh L nbsp bestimmen lasst Verallgemeinerte Sternhohe BearbeitenDie verallgemeinerte oder auch generalisierte Sternhohe gsh r displaystyle operatorname gsh r nbsp ist analog zur Sternhohe definiert allerdings nicht uber regularen Ausdrucken sondern uber verallgemeinerten regularen Ausdrucken welche zusatzlich zu den normalen Operatoren direkt die Komplementierung displaystyle neg nbsp erlauben Es gilt also gsh 0 displaystyle operatorname gsh emptyset 0 nbsp gsh e 0 displaystyle operatorname gsh varepsilon 0 nbsp gsh x 0 x A displaystyle operatorname gsh x 0 quad forall x in A nbsp gsh v gsh v displaystyle operatorname gsh lnot v operatorname gsh v nbsp fur alle verallgemeinerten regularen Ausdrucke v displaystyle v nbsp gsh v w max gsh v gsh w displaystyle operatorname gsh v cdot w max operatorname gsh v operatorname gsh w nbsp fur alle verallgemeinerten regularen Ausdrucke v w displaystyle v w nbsp gsh v w max gsh v gsh w displaystyle operatorname gsh v w max operatorname gsh v operatorname gsh w nbsp fur alle verallgemeinerten regularen Ausdrucke v w displaystyle v w nbsp gsh v w max gsh v gsh w displaystyle operatorname gsh v cap w max operatorname gsh v operatorname gsh w nbsp fur alle verallgemeinerten regularen Ausdrucke v w displaystyle v w nbsp gsh v gsh v 1 displaystyle operatorname gsh v star operatorname gsh v 1 nbsp fur alle verallgemeinerten regularen Ausdrucke v displaystyle v nbsp Analog ist die verallgemeinerte Sternhohe gsh L displaystyle operatorname gsh L nbsp einer regularen Sprache L displaystyle L nbsp definiert Beispielsweise hat die Sprache L S displaystyle L Sigma nbsp die Sternhohe 1 wahrend dieselbe Sprache wegen L S L displaystyle L Sigma L neg emptyset nbsp die verallgemeinerte Sternhohe 0 hat Verallgemeinertes Sternhohenproblem BearbeitenDas verallgemeinerte Sternhohenproblem ist analog zum Sternhohenproblem definiert aber im Gegensatz zu diesem noch unbeantwortet Zwar gibt es regulare Sprachen L displaystyle L nbsp mit gsh L 1 displaystyle operatorname gsh L 1 nbsp zum Beispiel die Sprache L a a displaystyle mathcal L aa nbsp Offen ist aber noch die Frage ob auch eine regulare Sprache L displaystyle L nbsp mit gsh L 2 displaystyle operatorname gsh L geq 2 nbsp existiert Literatur BearbeitenLawrence 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 Therien Some results on the generalized star height problem In Information and Computation 101 1992 2 ISSN 0890 5401 S 219 250 liafa jussieu fr Abgerufen von https de wikipedia org w index php title Sternhohe Informatik amp oldid 223287683
