Kategorielle Theorie der Automaten

• Antragsteller: Professor Dr. Stefan Milius; Dr. Henning Urbat
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 470467389

Endliche zustandsbasierte Strukturen sind grundlegende Beschreibungsmittel in der Informatik, den Ingenieur- und Naturwissenschaften. Es gibt dutzende Maschinentypen, z.B. für reguläre Sprachen endlicher und unendlicher Wörter oder Bäume, gewichtete oder stochastische Sprachen oder Datensprachen. Ihre Theorien zeigen viele Gemeinsamkeiten, z.B. maschinenunabhängige Beschreibungen durch endliche algebraische Erkenner oder eine Form von monadischer Logik zweiter Stufe sowie ähnliche Algorithmik. Trotzdem wurden verschiedene Systemtypen bisher meist separat erforscht. In CATHY entwickeln wir eine einheitliche Theorie, die das gesamte Spektrum von endlichen Zustandsmaschinen abdeckt. Dies basiert auf Konzepten der Kategorientheorie, einer mächtigen mathematischen Theorie, die sich sehr gut eignet, um Ähnlichkeiten formal zu erfassen und verschiedene Strukturen systematisch in Beziehung zu setzen. Das Ziel ist eine Theorie der Regularität von Maschinenverhalten, die unabhängig vom Systemtyp ist. Insbesondere geht es dabei um Dualitäten, die einen tiefen Zusammenhang zwischen Maschinen und endlichen algebraischen Strukturen für reguläres Verhalten herstellen. Dualität ist bspw. die Basis für Eilenberg/Reiterman-artige Korrespondenzen, die Eigenschaften regulären Verhaltens mit Eigenschaften ihrer algebraischen Erkenner in Beziehung setzen und deren Spezifikation mittels proendlicher Gleichungen erlauben. Hinzu kommen topologische Methoden, die zu einem besseren Verständnis von Phänomenen in der Theorie der regulären Sprache geführt haben. Sie fußen auf der Beobachtung, dass Erkennbarkeit von Sprachen durch die Stetigkeit entsprechender Prädikate beschreibbar ist. Anfänge einer generischen Theorie existieren, inkl. einer allgemeinen Eilenberg/Reiterman-Korrespondenz. Topologische Methoden und sogar ein generisches Maschinenmodell fehlen hingegen bisher.In CATHY werden wir den Stand der Technik der generischen, dualitätsbasierten Theorie der algebraischen Sprachtheorie durch die Entwicklung topologischer Methoden erweitern. Ferner wird ein generisches Maschinenmodell für reguläres Verhalten eingeführt und dessen Algorithmik erforscht. Hierbei liegt ein besonderer Fokus auf algorithmischem Lernen dieser Maschinen, das auf neuen koalgebraischen Verfahren des Automatenlernens beruht. Die Robustheit des generischen Ansatzes wird demonstriert, indem wir neuen, nicht trivialen Anwendungen erhöhte Aufmerksamkeit widmen. Dies betrifft sowohl naheliegende Anwendungen wie Textsprachen als auch herausfordernde wie Datensprachen, stochastische Sprachen und von endlichen Quantenautomaten akzeptierte reguläre Sprachen. Zusammenfassend entsteht so eine vereinheitlichte generische Theorie des Verhaltens endlicher Zustandsmaschinen mit umfassenden mathematischen Grundlagen, Konstruktionen und Algorithmen mit breiter Anwendbarkeit.

• DFG-Verfahren: Sachbeihilfen