Fortschritte beim verallgemeinerten Sternhöhenproblem?

Die (verallgemeinerte) Sternhöhe einer Sprache ist die minimale Verschachtelung von Kleene-Sternen, die erforderlich ist, um die Sprache durch einen erweiterten regulären Ausdruck darzustellen. Denken Sie daran, dass ein erweiterter regulärer Ausdruck über ein endliches Alphabet die folgenden Bedingungen erfüllt:$A$

(1) und sind erweiterte reguläre Ausdrücke für alle$\emptyset, 1$$a$$a\in A$

(2) Für alle erweiterten regulären Ausdrücke ; , , und$E,F$
$E\cup F$$EF$$E^*$$E^c$ sind erweiterte reguläre Ausdrücke

Eine Formulierung des Problems der verallgemeinerten Sternhöhe ist, ob es einen Algorithmus zur Berechnung der minimalen verallgemeinerten Sternhöhe gibt. In Bezug auf dieses Problem habe ich ein paar Fragen.

1. Gab es in letzter Zeit Fortschritte (oder Forschungsinteressen) in Bezug auf dieses Problem? Ich weiß, dass Pin Straubing und Thérien vor einigen Jahren einige Artikel in diesem Bereich veröffentlicht haben.

2. Das Problem der eingeschränkten Sternhöhe wurde 1988 von Hashiguchi gelöst, aber die verallgemeinerte Version ist (soweit ich weiß) noch offen. Hat jemand eine Ahnung, warum dies der Fall sein könnte?

Ein Link, der hilfreich sein könnte, ist der folgende: starheight

In Bezug auf Ihre zweite Frage lautet eine Erklärung, warum das verallgemeinerte Sternhöhenproblem weniger zugänglich ist als das Sternhöhenproblem, wie folgt: Bereits Eggans wegweisende Arbeit von 1963 enthielt Sprachen mit (gewöhnlicher) Sternhöhe für jedes k ≥ 0 . Nur wenige Jahre später fanden McNaughton und unabhängig voneinander Déjean und Schützenberger Beispiele für binäre Alphabete. Dies machte deutlich, worum es bei dem Problem "geht". In den folgenden Jahren gab es einen mehr oder weniger konstanten Strom veröffentlichter Ergebnisse im Bereich des normalen Sternhöhenproblems. Dies ergab eine ständig wachsende Anzahl veröffentlichter Beispiele, Gegenbeispiele und Phänomene, die dieses Problem umgaben.$k$$k\ge 0$

Im Gegensatz dazu wissen wir nach etwa fünfzig Jahren nicht, ob es eine reguläre Sprache mit mindestens zwei Sternen gibt. Wir wissen also nicht einmal, ob ein Entscheidungsverfahren überhaupt erforderlich ist. Dieses "völlige Fehlen von Beispielen" zeigt, dass es äußerst schwierig ist, dieses Problem in den Griff zu bekommen.

Diese Antwort ist der Erinnerung an Janusz (John) Antoni Brzozowski gewidmet, der am 24. Oktober 2019 verstorben ist.

John ist sicherlich die Person, die die Probleme mit der Sternenhöhe so berühmt gemacht hat. Tatsächlich stellte er auf einer Konferenz in Santa Barbara im Dezember 1979 eine Auswahl von sechs offenen Problemen mit regulären Sprachen vor und erwähnte zwei weitere Themen in der Schlussfolgerung seines Artikels [1]. Diese sechs offenen Probleme waren in der Reihenfolge Sternhöhe, begrenzte Sternhöhe, Gruppenkomplexität, Sternentfernung, Regelmäßigkeit von nicht zählenden Klassen und Optimalität von Präfixcodes. Die beiden anderen Themen waren das Begrenzungsproblem und die Punkttiefenhierarchie.

Im Juni 2015 präsentierte ich anlässlich einer eintägigen Konferenz zu seinem 80. Geburtstag zwei Umfrageartikel, die den Stand der Technik zu diesen Fragen zusammenfassen [2, 3]. Insbesondere finden Sie in [2] detaillierte Informationen zu den Sternhöhenproblemen.

[1] JA Brzozowski, Offene Probleme mit regulären Sprachen in der formalen Sprachtheorie. Perspektiven und offene Probleme, Vorträge eines Symposiums in Santa Barbara, Kalifornien, 10.-14. Dezember 1979 [, RV Book (Hrsg.), S. 23–47, New York Etc .: Academic Press, eine Tochtergesellschaft von Harcourt Brace Jovanovich, Verleger. XIII, 454 S., 1980.

[2] J.-É. Pin, Offene Probleme mit regulären Sprachen, 35 Jahre später Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. Die Rolle der Theorie in der Informatik - Aufsätze zu Janusz Brzozowski, World Scientific, 2017,

[3] J.-É. Pin, Die Punkttiefenhierarchie, 45 Jahre später . Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. Die Rolle der Theorie in der Informatik - Aufsätze zu Janusz Brzozowski, World Scientific, 2017.

Die Lösung des Problems der eingeschränkten Sternhöhe inspirierte die reiche Theorie der regulären Kostenfunktionen (von Colcombet), die wiederum zur Lösung anderer Entscheidbarkeitsprobleme beitrug und neue Tools zum Angriff auf offene Probleme anbot. Diese Theorie befindet sich noch in der Entwicklung und wurde auf unendliche Worte, endliche Bäume, unendliche Bäume mit einer eigenen Reihe tiefer Ergebnisse und offener Probleme ausgedehnt. Hier finden Sie eine wegweisende Abhandlung der Theorie und eine Bibliographie von Colcombets Website.

Während es sich also nicht direkt um eine Anwendung der verallgemeinerten Sternhöhe handelt, zeigt es, dass das Fortschreiten bei scheinbar nutzlosen Problemen wie der Sternhöhe wahrscheinlich ein besseres Verständnis der regulären Sprachen bedeutet und neue Ergebnisse bei verschiedenen Problemen liefert.

Hinweis: Thomas Colcombet. "Die Theorie der Stabilisierungsmonoide und der regulären Kostenfunktionen". In: ICALP 2009