2025-11-19T16:52:14.243866

Learning Weighted Automata over Number Rings, Concretely and Categorically

Aristote, van Gool, Petrişan et al.
We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted automata over integers to that for weighted automata over rationals (Buna-Marginean et al. 2024). Our procedure improves the efficiency of a category-theoretic automata learning algorithm, and poses new questions about the complexity of its implementation when instantiated to concrete categories. As our second main contribution, we address these complexity aspects in the concrete setting of learning weighted automata over number rings, that is, rings of integers in an algebraic number field. Assuming a full representation of a number ring OK, we obtain an exact learning algorithm of OK-weighted automata that runs in polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of the number field, and the logarithm of its discriminant. Our algorithm produces an automaton that has at most one more state than the minimal one, and we prove that doing better requires solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.
academic

Lernen gewichteter Automaten über Zahlringe, konkret und kategorietheoretisch

Grundinformationen

  • Paper-ID: 2504.16596
  • Titel: Learning Weighted Automata over Number Rings, Concretely and Categorically
  • Autoren: Quentin Aristote, Sam van Gool, Daniela Petrişan, Mahsa Shirmohammadi
  • Klassifikation: cs.FL (Formale Sprachen und Automatentheorie)
  • Veröffentlichungsdatum: 23. April 2025 (arXiv-Preprint)
  • Paper-Link: https://arxiv.org/abs/2504.16596

Zusammenfassung

In diesem Artikel wird ein universelles Reduktionsverfahren für aktive Lernprobleme entwickelt. Die Methode wurde durch die kürzliche Arbeit von Buna-Marginean et al. (2024) inspiriert, die das Problem des exakten Lernens gewichteter Automaten über den ganzen Zahlen polynomiell auf das Lernproblem gewichteter Automaten über den rationalen Zahlen reduziert. Das Verfahren verbessert die Effizienz kategorietheoretischer Automaten-Lernalgorithmen und wirft bei konkreten kategorialen Instanziierungen neue Fragen zur Implementierungskomplexität auf. Als zweiter Hauptbeitrag werden diese Komplexitätsfragen in der konkreten Einstellung des Lernens gewichteter Automaten über Zahlringen (Ganzzahlringe in algebraischen Zahlkörpern) gelöst. Unter der Annahme einer vollständigen Darstellung des Zahlrings OK wird ein exakter Lernalgorithmus für OK-gewichtete Automaten erhalten, der polynomielle Zeitkomplexität in der Größe des Zielautomaten, dem Logarithmus der längsten Gegenbeispielänge, dem Grad des Zahlkörpers und dem Logarithmus der Diskriminante aufweist. Der vom Algorithmus produzierte Automat hat höchstens einen Zustand mehr als der minimale Automat, und es wird bewiesen, dass bessere Ergebnisse die Lösung des Hauptidealproblems erfordern, für das der derzeit beste bekannte Algorithmus quantenpolynomielle Zeit benötigt.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Klassisches Automatenlernen: Angluins L*-Algorithmus lernt effizient deterministische endliche Automaten im Rahmen des minimalen ausreichenden Lehrers (MAT), ein klassisches Ergebnis der Computational Learning Theory.
  2. Herausforderungen beim Lernen gewichteter Automaten: Die Erweiterung von Lernalgorithmen auf ausdrucksstärkere Modelle (wie gewichtete Automaten) ist herausfordernd, besonders wenn die Gewichte nicht in einem Körper sondern in einem Ring liegen.
  3. Einschränkungen bestehender Methoden:
    • Für gewichtete Automaten über Körpern existieren polynomielle Lernalgorithmen
    • Für gewichtete Automaten über allgemeinen Ringen haben bestehende Methoden entweder zu hohe Komplexität oder begrenzte Anwendbarkeit
    • Kategorietheoretische Methoden sind zwar universell, können aber bei konkreter Implementierung zu exponentieller Komplexität führen

Forschungsmotivation

  1. Theoretischer Bedarf: Ein Rahmen ist erforderlich, der sowohl die Allgemeinheit der kategorietheoretischen Methode bewahrt als auch in konkreten Fällen polynomielle Komplexität aufweist
  2. Praktische Anwendungen: Zahlringe haben wichtige Anwendungen in der Kryptographie; effizientes Lernen gewichteter Automaten über ihnen hat praktischen Wert
  3. Theoretische Grenzen: Erforschung der theoretischen Grenzen der Minimierung gewichteter Automaten, insbesondere Verallgemeinerungen der Fatou-Eigenschaft

Kernbeiträge

  1. Universelles Reduktionsverfahren: Präsentation von Algorithmus 3, einem universellen Reduktionsverfahren im kategorietheoretischen Rahmen, das eine Klasse von Lernproblemen auf eine leichter handhabbare Klasse reduziert
  2. Konkreter Algorithmus für Zahlringe: Entwicklung von Algorithmus 4, ein spezialisierter polynomieller Zeitalgorithmus zum Lernen gewichteter Automaten über Zahlringen OK
  3. Quasi-Optimalitätsergebnisse: Beweis, dass der vom Algorithmus produzierte Automat höchstens einen Zustand mehr als der minimale Automat hat (quasi-Minimalität)
  4. Theoretische Komplexitätsgrenzen: Beweis, dass das Erreichen eines vollständig minimalen Automaten äquivalent zur Lösung des Hauptidealproblems (PIP-hart) ist, wodurch eine theoretische Untergrenze etabliert wird
  5. Verallgemeinerung der Fatou-Eigenschaft: Beweis, dass Dedekind-Bereiche "quasi-stark Fatou-Ringe" sind, was die klassische Fatou-Eigenschaft verallgemeinert

Methodische Details

Aufgabendefinition

Eingabe: Eine unbekannte OK-gewichtete Sprache L: Σ* → OK (über ein Orakel zugänglich) Ausgabe: Ein OK-gewichteter Automat, der L berechnet Einschränkung: Algorithmuskomplexität ist polynomiell in der Größe des Zielautomaten, dem Logarithmus der längsten Gegenbeispielänge, dem Grad des Zahlkörpers und dem Logarithmus der Diskriminante

Kernmethodischer Rahmen

1. Kategorietheoretische Grundlagen

Der Artikel verwendet eine Funktorsicht, wobei Automaten als Funktoren A: I → C betrachtet werden, wobei:

  • I die von dem Alphabet Σ erzeugte freie Kategorie ist
  • C die Ausgabekategorie ist (z.B. Modulkategorie ModR)

2. Universelles Reduktionsverfahren (Algorithmus 3)

Algorithmische Idee:
1. Lernen eines Automaten in der "leicht handhabbaren" Kategorie D
2. Etablierung einer Verbindung durch einen Funktor F: C → D
3. Verwendung des rechtsadjungierten Funktors G: D → C 
   zum Zurückziehen des Ergebnisses in die Zielkategorie C

Schlüsselannahme (Annahme 12):

  • F bewahrt bestimmte Morphismusklassen
  • F hat einen Rechtsadjungierten G
  • Unit- und Counit-Morphismen haben spezifische Eigenschaften

3. Konkrete Implementierung über Zahlringen (Algorithmus 4)

Schritt 1: Rückwärtige Konjugation

Berechnung einer Basis B des rückwärtigen Raums des Automaten A
Konjugation von A durch Matrix B zur Erzeugung von A'

Schritt 2: Vordere Modulgenerierung

Aufruf von Algorithmus 5 zur Berechnung einer Generatorenmenge 
des vorderen OK-Moduls von A'
Verwendung einer zweistufigen Strategie:
- Erste Stufe: Finden von Wörtern, die den Rang in K erhöhen
- Zweite Stufe: Vervollständigung der Modulgenerierung in OK

Schritt 3: Pseudobasis-Berechnung

Verwendung der Pseudo-Hermite-Normalform (pseudo-HNF) 
zur Berechnung einer Pseudobasis aus der Generatorenmenge
Pseudobasis-Form: {(ai, vi) | 1 ≤ i ≤ ℓ}, wobei ai Bruchideale sind

Schritt 4: Quasi-minimale Generatorenmenge

Umwandlung der Pseudobasis durch Algorithmus 6 
in eine Generatorenmenge der Größe höchstens ℓ+1
Verwendung von Idealfaktor-Verfeinerung und Chinesischem Restsatz

Technische Innovationen

  1. Zweistufige Generierungsstrategie: Zuerst wird der Rang in dem Körper K bestimmt, dann wird die Modulstruktur in OK vervollständigt, wodurch exponentielle Komplexität vermieden wird
  2. Pseudobasis-Technik: Nutzung der Strukturtheorie von Dedekind-Bereichen zur Behandlung von Fällen mit nicht-Hauptidealdomänen durch Pseudobasen
  3. Kombination von Kategorientheorie und konkretem Algorithmus: Konkretisierung des abstrakten kategorietheoretischen Rahmens zu einem implementierbaren polynomiellen Algorithmus

Experimentelle Einrichtung

Theoretische Verifikation

Der Artikel ist hauptsächlich eine theoretische Arbeit, verifiziert durch:

  1. Komplexitätsanalyse: Detaillierte Analyse der Zeitkomplexität von Algorithmus 4 und Algorithmus 5
  2. Korrektheitsbeweise: Beweis der Korrektheit des universellen Algorithmus durch Theorem 18
  3. Konkrete Beispiele: Bereitstellung von Beispielen (z.B. Beispiel 1) zur Illustration der Situation über Zi√5

Komplexitätsgrenzen

Theorem 2: Gegeben eine vollständige Darstellung von OK ist das exakte Lernen OK-gewichteter Automaten in polynomieller Zeit in den folgenden Parametern lösbar:

  • Größe des Zielautomaten
  • Logarithmus der längsten Gegenbeispielänge
  • Grad d des Zahlkörpers
  • Logarithmus der Diskriminante ΔK

Experimentelle Ergebnisse

Haupttheoretische Ergebnisse

  1. Quasi-Optimalität (Proposition 10): Für einen Dedekind-Bereich R existiert für jede R-gewichtete Sprache L vom Rang n ein R-gewichteter Automat mit höchstens n+1 Zuständen, der L berechnet
  2. Komplexitätsuntergrenze (Proposition 26): Die Bestimmung, ob ein OK-gewichteter Automat zustandsminimal ist, ist PIP-hart
  3. Verallgemeinerung der Fatou-Eigenschaft (Korollar 16): Dedekind-Bereiche sind quasi-stark Fatou-Ringe

Analyse konkreter Beispiele

Beispiel 1: Im Zahlring R = Zi√5:

  • Konstruktion eines 3-Zustands-R-gewichteten Automaten
  • Existenz eines äquivalenten 2-Zustands-K-gewichteten Automaten (K = Q(i√5))
  • Illustration, dass die starke Fatou-Eigenschaft nicht immer gilt, aber die quasi-starke Fatou-Eigenschaft erfüllt ist

Verwandte Arbeiten

Klassisches Automatenlernen

  • Angluins L*-Algorithmus: Polynomiales Lernen deterministischer endlicher Automaten
  • Beimel et al.: Lernalgorithmen für gewichtete Automaten über Körpern

Gewichtete Automaten über Ringen

  • van Heerdt et al.: Lernen über Hauptidealdomänen, aber ohne Komplexitätsgrenzen
  • Buna-Marginean et al.: Reduktion von Z zu Q, direkte Inspiration für diesen Artikel

Kategorietheoretische Methoden

  • Colcombet-Petrişan: Funktormethoden zur Automatenminiminierung
  • Urbat-Schröder et al.: Algebraische Ansätze zum Lernen

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Entwicklung des ersten polynomiellen Zeitalgorithmus zum Lernen gewichteter Automaten über Zahlringen
  2. Beweis der Schwierigkeit, vollständig minimale Automaten zu erhalten (PIP-hart)
  3. Etablierung einer Brücke zwischen Kategorientheorie und konkreten Algorithmen

Einschränkungen

  1. Darstellungsanforderungen: Erfordert eine "vollständige Darstellung" des Zahlrings OK, was in der Praxis schwierig sein kann
  2. Quasi-Optimalität: Der vom Algorithmus produzierte Automat kann einen Zustand mehr als der minimale haben
  3. Spezifische Struktur: Die Methode ist spezialisiert auf Dedekind-Bereiche; Verallgemeinerungen auf allgemeine Ringe sind unklar

Zukünftige Richtungen

  1. Andere Ringklassen: Untersuchung von Verallgemeinerungen auf nicht-Dedekind-Bereiche
  2. Praktische Implementierung: Entwicklung konkreter Softwareimplementierungen und experimentelle Verifikation
  3. Anwendungsforschung: Konkrete Anwendungen in der Kryptographie und anderen Bereichen

Tiefgreifende Bewertung

Stärken

  1. Theoretische Tiefe: Geschickte Kombination von Kategorientheorie, algebraischer Zahlentheorie und Rechenkomplexitätstheorie
  2. Technische Innovation: Kreative Verwendung der zweistufigen Lernstrategie und Pseudobasis-Technik
  3. Vollständigkeit: Bereitstellung sowohl von Algorithmen als auch von Untergrenzen bietet ein vollständiges Bild des Problems
  4. Strenge: Mathematische Beweise sind rigoros, Komplexitätsanalyse ist detailliert

Schwächen

  1. Praktische Anwendbarkeit: Mangel an praktischer Implementierung und experimenteller Verifikation
  2. Lesbarkeit: Der kategorietheoretische Teil kann für Nicht-Experten schwierig zu verstehen sein
  3. Anwendungsbereich: Die Anwendbarkeit der Methode ist auf spezifische algebraische Strukturen beschränkt

Auswirkungen

  1. Theoretischer Beitrag: Wichtiger Beitrag zur Theorie des Lernens gewichteter Automaten
  2. Methodologie: Demonstration, wie abstrakte kategorietheoretische Methoden konkretisiert werden können
  3. Interdisziplinarität: Verbindung von Automatentheorie, algebraischer Zahlentheorie und Rechenkomplexität

Anwendungsszenarien

  1. Kryptographie: Anwendungen von Zahlringen in der Gitterkryptographie
  2. Symbolische Berechnung: Rechenproblemen über algebraischen Zahlkörpern
  3. Theoretische Forschung: Grundlagen für weitere Forschung zum Lernen von Automaten

Ergänzende technische Details

Darstellung von Zahlringen

Der Artikel erfordert eine "vollständige Darstellung" von OK, einschließlich:

  • Integrale Basis Ω = {ω1,...,ωd}
  • Primitives Element θ und sein Minimalpolynom
  • Komplexitätsmaß CK = d⁴(log d + log ΔK)

Algorithmuskomplexität

Wichtige Komplexitätsgrenzen stammen aus:

  • Pseudo-HNF-Berechnung: Polynomielle Zeit (Biasse-Fieker-Hofmann)
  • Länge streng aufsteigender Ketten: Durch Lemma 24 begrenzt durch log(N(d))
  • Idealoperationen: Polynomielle Zeit in CK

Dieser Artikel leistet einen wichtigen Beitrag zur theoretischen Informatik, besonders im Schnittbereich von Automatenlernen und algebraischer Berechnung. Obwohl die praktische Anwendbarkeit noch zu überprüfen ist, sind sein theoretischer Wert und seine methodologische Bedeutung erheblich.