💻 computer science

The complexity of downward closures of indexed languages

Dieser Beitrag löst die offene Frage bezüglich der Komplexität der Berechnung von Abwärtsabschlüssen für indizierte Sprachen, indem er für nichtdeterministische und deterministische Automaten jeweils dreifach und vierfach exponentielle obere Schranken sowie dazu passende untere Schranken etabliert, was durch eine neuartige Methode erreicht wird, die indizierte Grammatiken unter Verwendung semigruppenbasierter Wortzusammenfassungen in kontextfreie Grammatiken transformiert.

Ursprüngliche Autoren: Richard Mandel, Corto Mascle, Georg Zetzsche

Veröffentlicht 2026-05-28

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Richard Mandel, Corto Mascle, Georg Zetzsche

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine massive, unendlich komplexe Bibliothek von Geschichten vor. Manche Geschichten sind kurz, manche Millionen Seiten lang, und manche folgen Regeln, die so kompliziert sind, dass ein normaler Computer sie nicht einmal lesen kann. In der Welt der Informatik heißen diese Geschichten indizierte Sprachen. Sie sind wie eine überladene Version der standardmäßigen „kontextfreien" Sprachen (die Dinge wie die Syntax von Programmcode antreiben), besitzen aber eine zusätzliche Komplexitätsebene: einen „Stapel von Stapeln".

Stellen Sie sich einen normalen Stapel wie einen Stapel Teller vor. Sie können einen Teller hinzufügen oder einen wegnehmen. Eine indizierte Sprache ist wie ein Stapel ganzer Teller-Türme. Sie können einen ganzen Turm hinzufügen oder einen ganzen Turm wegnehmen. Dies macht das System unglaublich leistungsfähig, aber auch unglaublich schwer zu analysieren.

Das Problem: Der „absteigende Abschluss"

Die Autoren dieses Papiers interessieren sich für eine bestimmte Art, diese riesigen Bibliotheken zu vereinfachen. Sie nennen es den absteigenden Abschluss.

Stellen Sie sich einen sehr langen Satz vor: „Der schnelle braune Fuchs springt über den faulen Hund."
Der „absteigende Abschluss" dieses Satzes ist die Sammlung aller möglichen kürzeren Sätze, die Sie bilden können, indem Sie Buchstaben löschen, aber die Reihenfolge beibehalten.

„Der Fuchs springt" ist im Abschluss enthalten.
„Schneller Hund" ist im Abschluss enthalten.
„Hund schneller" ist nicht enthalten (weil sich die Reihenfolge geändert hat).

Warum ist das wichtig? Weil die ursprüngliche Bibliothek unendlich und unmöglich zu verarbeiten sein könnte. Aber der „absteigende Abschluss" (die Menge aller möglichen Unter-Geschichten) ist immer regulär. In der Computersprache bedeutet dies, dass er durch eine einfache, endliche Maschine beschrieben werden kann (wie ein grundlegender Flussdiagramm). Es ist eine Möglichkeit, ein chaotisches, unendliches Durcheinander in eine ordentliche, handhabbare Liste von Mustern zu verwandeln.

Die große Frage: Wir wussten, dass wir diese komplexen indizierten Sprachen in einfache Listen (absteigende Abschlüsse) verwandeln konnten. Aber wir wussten nicht, wie groß diese Liste sein würde. Wäre es eine Liste in der Größe eines Telefonbuchs? Eine Liste in der Größe des gesamten Internets? Oder eine Liste, die so groß ist, dass es länger dauern würde, sie zu schreiben, als das Alter des Universums?

Die Entdeckung: Eine dreifach exponentielle Explosion

Die Autoren, Mandel, Mascle und Zetzsche, haben dieses Rätsel endlich gelöst. Sie bewiesen, dass die Maschine, die entsteht, wenn man eine indizierte Sprache in ihren einfachen absteigenden Abschluss verwandelt, dreifach exponentiell groß sein kann.

Lassen Sie uns aufschlüsseln, was „dreifach exponentiell" bedeutet, anhand einer Metapher:

Linear: Wenn Sie 10 Gegenstände haben, benötigen Sie 10 Boxen.
Exponentiell: Wenn Sie 10 Gegenstände haben, benötigen Sie $2^{10}$ (1.024) Boxen.
Doppelt exponentiell: Wenn Sie 10 Gegenstände haben, benötigen Sie $2^{2^{10}}$ (über eine Million Milliarden) Boxen.
Dreifach exponentiell: Wenn Sie 10 Gegenstände haben, benötigen Sie $2^{2^{2^{10}}}$ Boxen. Diese Zahl ist so gewaltig, dass sie fast unmöglich zu begreifen ist. Es ist wie der Versuch, jedes Sandkorn an jedem Strand der Erde zu zählen, und das dann für jedes Sandkorn an jedem Strand auf jedem Strand zu wiederholen...

Die Autoren zeigten, dass für indizierte Sprachen der „absteigende Abschluss"-Maschine ungefähr so riesig ist. Sie bewiesen auch, dass man nicht besser damit umgehen kann; die Maschine muss für bestimmte Sprachen so groß sein.

Wie sie es taten: Der „Zusammenfassungs"-Trick

Wie komprimiert man einen Stapel von Türmen in eine einfache Liste, ohne die Fähigkeit zu verlieren, Muster zu erkennen?

Die Autoren verwendeten einen cleveren Trick aus einem Bereich der Mathematik namens Semigruppentheorie. Stellen Sie sich vor, Sie lesen eine sehr lange Geschichte, aber es interessiert Sie nur die „Stimmung" der Geschichte, nicht jedes einzelne Wort.

Wenn sich eine Geschichte ein bestimmtes Muster immer wiederholt (wie ein Refrain in einem Lied), müssen Sie nicht den ganzen Refrain jedes Mal aufschreiben. Sie können einfach „Refrain" schreiben und weitermachen.
Die Autoren erstellten eine mathematische „Zusammenfassung" für die Stapel. Anstatt jeden einzelnen „Teller" oder „Turm" im Stapel zu verfolgen, ersetzten sie lange Sequenzen identischer Muster durch ein einziges Zusammenfassungssymbol.

Sie zeigten, dass man, obwohl die Stapel unendlich sind, sie durch diese Zusammenfassungen ersetzen kann. Sobald Sie das getan haben, wird die komplexe „indizierte Grammatik" zu einer einfacheren „kontextfreien Grammatik" (ein Standardtyp einer Computer-Grammatik). Dann verwendeten sie bestehende Methoden, um diese einfachere Grammatik in die endgültige Maschine für den absteigenden Abschluss zu verwandeln.

Das Ergebnis: Ein neuer Rekord

Vor diesem Papier wussten die Leute, dass das Problem lösbar war, aber sie kannten die Kosten nicht.

Die obere Schranke: Sie bauten eine Methode, um die Maschine zu erstellen, und sie benötigt dreifach exponentielle Zeit und Speicherplatz.
Die untere Schranke: Sie bauten auch eine spezifische, knifflige Sprache, die jede Maschine zwingt, mindestens dreifach exponentiell groß zu sein.

Das bedeutet, sie haben den genauen „Preis" für dieses Problem gefunden. Es ist nicht nur „schwierig"; es ist „dreifach exponentiell schwierig".

Sie wandten dies auch auf zwei weitere Fragen an:

Vergleich: Wenn Sie zwei komplexe Sprachen haben, können Sie feststellen, ob ihre „absteigenden Abschlüsse" gleich sind? Die Antwort ist ja, aber es ist ein co-3-NEXP-vollständiges Problem. Auf Deutsch gesagt: Es ist ein Rätsel, das unglaublich schwer zu lösen ist, genau am Rand dessen, was Computer theoretisch in einem angemessenen Zeitrahmen bewältigen können.
Pump-Schwelle: Sie bewiesen, dass das längste Wort, das Sie in einer endlichen indizierten Sprache generieren können, bevor es beginnt, Muster zu wiederholen, ebenfalls dreifach exponentiell ist.

Zusammenfassung

Stellen Sie sich indizierte Sprachen als ein riesiges, unendliches Labyrinth vor. Der „absteigende Abschluss" ist eine Karte aller möglichen Abkürzungen durch dieses Labyrinth.

Altes Wissen: Wir wussten, dass eine Karte existiert.
Neues Wissen: Wir wissen jetzt, dass für die komplexesten Labyrinthe die Karte so riesig ist, dass es einem Computer länger dauern würde, sie zu zeichnen, als das Universum existiert hat.
Die Methode: Die Autoren fanden einen Weg, das Labyrinth durch Zusammenfassen der sich wiederholenden Teile auf eine handhabbare Größe zu schrumpfen, was es ihnen ermöglichte, die Karte zu zeichnen und genau zu beweisen, wie groß sie sein muss.

Sie haben nicht nur geraten; sie haben die Karte gebaut und bewiesen, dass keine kleinere Karte funktionieren könnte.

Technische Zusammenfassung: Die Komplexität der Abwärtsabschlüsse indizierter Sprachen

Problemstellung

Der Artikel behandelt die rechnerische Komplexität der Konstruktion von Abwärtsabschlüssen für indizierte Sprachen. Der Abwärtsabschluss einer Sprache $L$ , bezeichnet als $L^\downarrow$ , ist die Menge aller gestreuten Teilwörter der Wörter in $L$ . Nach Higman's Lemma ist $L^\downarrow$ stets eine reguläre Sprache, was sie zu einer entscheidenden regulären Überapproximation für die Verifikation von Systemen mit unendlichem Zustandsraum macht (z. B. Modellprüfung höherer Ordnung, asynchrone Programme und verlustbehaftete Kanalsysteme).

Während die Berechenbarkeit von Abwärtsabschlüssen für indizierte Sprachen (äquivalent zu Pushdown-Automaten der Ordnung 2 oder 2-PDAs) im Jahr 2015 über einen allgemeinen Algorithmus auf Basis von wohlquasi-geordneten Mengen etabliert wurde, blieben die Komplexitätsschranken für diese Konstruktion ein offenes Problem. Insbesondere war unklar, ob eine primitiv-rekursive Konstruktion existiert, und es waren keine oberen oder unteren Schranken für die Größe der resultierenden Automaten bekannt. Vor dieser Arbeit betrug die beste bekannte untere Schranke für die Größe eines nichtdeterministischen endlichen Automaten (NFA) für den Abwärtsabschluss einer indizierten Sprache doppelt exponentiell, und die Komplexität von Entscheidungsproblemen wie der Inklusion und Äquivalenz von Abwärtsabschlüssen war als mindestens co-2-NEXP-hart bekannt.

Methodik

Die Autoren lösen dieses offene Problem durch die Bereitstellung enger (asymptotisch übereinstimmender) oberer und unterer Schranken. Ihr Ansatz basiert auf einer neuartigen algebraischen Abstraktion von Stapelinhalten, um indizierte Grammatiken in kontextfreie Grammatiken (CFGs) zu transformieren, wobei der Abwärtsabschluss erhalten bleibt.

1. Produktivität und Annotation

Die Konstruktion beginnt damit, sicherzustellen, dass die Eingabe-indizierte Grammatik produktiv ist (jeder Satzform kann ein terminales Wort abgeleitet werden). Die Autoren führen eine annotierte Version der Grammatik ein, bei der Stapelsymbole mit Mengen von Nichtterminalen gepaart werden, die von dieser Stapelkonfiguration aus terminale Wörter ableiten können. Dies verhindert die Generierung „toter" Terme, die nicht zum Beitrag zur Sprache beitragen können, eine Eigenschaft, die für die Erhaltung des Abwärtsabschlusses während nachfolgender Transformationen wesentlich ist.

2. Der Stapel-Monoide und Zusammenfassungen

Die zentrale technische Innovation umfasst die endliche Halbgruppentheorie. Die Autoren definieren ein Stapel-Monoid $M$ (ein endliches Monoid aus Booleschen Matrizen), das das Verhalten von Stapeloperationen (Pushen und Poppen) in Bezug auf die Nichtterminale der Grammatik kodiert.

Zusammenfassungen: Sie nutzen jüngste Fortschritte in der Halbgruppentheorie (insbesondere Ergebnisse von Jecker und Gimbert et al.), um Zusammenfassungen (summaries) von beliebig langen Stapelwörtern zu berechnen. Eine Zusammenfassung ist eine komprimierte Darstellung eines Stapelworts, die genügend Informationen bewahrt, um das Ergebnis von Push-/Pop-Operationen bezüglich des Monoids $M$ zu bestimmen.
Pumpen und Überspringen: Die Autoren führen zwei neue Ableitungsregeln ein, pump (pumpen) und skip (überspringen), die die Erweiterung und Reduktion von Stapel-Infixen ermöglichen, die auf dasselbe idempotente Element im Monoid abbilden. Sie beweisen, dass diese Regeln den Abwärtsabschluss der Sprache nicht verändern.
Komprimierung: Durch Anwendung dieser Regeln zeigen sie, dass jeder Stapelinhalt in eine Zusammenfassung mit begrenzter Größe (exponentiell in der Größe der Grammatik) komprimiert werden kann. Diese Komprimierung verliert effektiv Informationen über den genauen Stapelinhalt, bewahrt jedoch den Abwärtsabschluss.

3. Reduktion auf kontextfreie Grammatiken

Mittels dieser Zusammenfassungen konstruieren die Autoren eine kontextfreie Grammatik (CFG) $G_{CFG}$ , die die ursprüngliche indizierte Grammatik $G$ simuliert. In $G_{CFG}$ werden die Stapelinhalte der indizierten Grammatik durch ihre Zusammenfassungen ersetzt.

Die Nichtterminale von $G_{CFG}$ sind Tripel $(A, X, \sigma)$ , wobei $A$ ein Nichtterminal, $X$ eine Menge von Nichtterminalen und $\sigma$ eine zulässige Zusammenfassung ist.
Push- und Pop-Operationen in der ursprünglichen Grammatik werden durch Operationen auf Zusammenfassungen simuliert (unter Verwendung der auf dem Monoid definierten push- und pop-Relationen).
Die Autoren beweisen, dass $L(G_{CFG})^\downarrow = L(G)^\downarrow$ gilt.

4. Komplexitätsanalyse

Da die Größe einer Zusammenfassung exponentiell in der Größe der Grammatik beschränkt ist, hat die resultierende CFG $G_{CFG}$ eine doppelt exponentielle Größe. Bestehende Algorithmen zur Berechnung von Abwärtsabschlüssen von CFGs liefern einen NFA mit exponentieller Größe relativ zur CFG. Folglich ergibt die Komposition einen NFA für $L(G)^\downarrow$ mit dreifach exponentieller Größe.

Für deterministische endliche Automaten (DFA) führt die Standard-Teilmenge-Konstruktion, angewendet auf den dreifach exponentiellen NFA, zu einer vierfach exponentiellen oberen Schranke.

Hauptbeiträge und Ergebnisse

Obere Schranken

NFA-Größe: Gegeben eine indizierte Grammatik der Größe $n$ , kann ein NFA für ihren Abwärtsabschluss in dreifach exponentieller Zeit berechnet werden und hat eine Größe von höchstens dreifach exponentiell ( $O(\exp_3(n))$ ).
DFA-Größe: Ein DFA für den Abwärtsabschluss kann mit einer Größe von höchstens vierfach exponentiell ( $O(\exp_4(n))$ ) konstruiert werden.
Entscheidungsprobleme: Die Probleme der Inklusion von Abwärtsabschlüssen ( $L_1^\downarrow \subseteq L_2^\downarrow$ ) und der Äquivalenz ( $L_1^\downarrow = L_2^\downarrow$ ) für indizierte Sprachen sind co-3-NEXP-vollständig.

Untere Schranken

Die Autoren liefern übereinstimmende untere Schranken und beweisen damit die Schärfe ihrer oberen Schranken:

Untere NFA-Schranke: Es existiert eine Familie indizierter Grammatiken polynomieller Größe, sodass jeder NFA für deren Abwärtsabschluss mindestens dreifach exponentielle Zustände erfordert. Dies wird durch die Konstruktion einer Grammatik erreicht, die die Sprache $\{a^{\exp_3(n)}\}$ erzeugt.
Untere DFA-Schranke: Es existiert eine Familie indizierter Grammatiken, sodass jeder DFA für deren Abwärtsabschluss mindestens vierfach exponentielle Zustände erfordert.
Pump-Schwelle: Die Ergebnisse implizieren, dass die Pump-Schwelle für indizierte Grammatiken (die maximale Länge eines Wortes in einer endlichen indizierten Sprache der Größe $n$ ) mindestens dreifach exponentiell wächst, was eine frühere Behauptung einer doppelt exponentiellen Schranke in der Literatur korrigiert.

Bedeutung

Der Artikel klärt ein langjähriges offenes Problem bezüglich der Komplexität von Abwärtsabschlüssen für indizierte Sprachen.

Enge Schranken: Er stellt fest, dass die Komplexität strikt höher ist als für kontextfreie Sprachen (die für NFAs doppelt exponentiell sind), aber niedriger als der allgemeine Exponentialturm, der oft mit Systemen höherer Ordnung der Ordnung $k > 2$ assoziiert wird. Der Sprung von doppelt zu dreifach exponentiell für indizierte Sprachen (Ordnung 2) ist unerwartet angesichts des linearen Wachstums der Komplexität für andere Probleme (wie Leerheit) in Bezug auf die Ordnung des Pushdown-Automaten.
Algorithmische Machbarkeit: Er bestätigt, dass eine primitiv-rekursive Konstruktion existiert und löst die Frage, ob das Problem lediglich berechenbar oder innerhalb einer bestimmten Komplexitätsklasse effektiv konstruierbar ist.
Methodischer Fortschritt: Die Technik, halbgruppenbasierte Zusammenfassungen zur Komprimierung von Stapelinhalten unter Beibehaltung von Abwärtsabschlüssen zu verwenden, bietet ein neues Werkzeug zur Analyse von Systemen höherer Ordnung, das potenziell auf breitere Klassen von Systemen mit unendlichem Zustandsraum anwendbar ist.

Die Autoren betonen, dass ihre Ergebnisse aus einer konstruktiven Transformation indizierter Grammatiken in CFGs abgeleitet sind, wobei die algebraischen Eigenschaften des Stapel-Monoids genutzt werden, um die unbeschränkte Natur der Stapel so zu handhaben, dass die für Abwärtsabschlüsse wesentliche Teilwortstruktur erhalten bleibt.