Endliche Coalgebren in Minimierung und Rekursion

• Antragsteller: Professor Dr. Jiri Adámek
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 251268147

Basierend auf der neuen Charakterisierung der terminalen Koalgebra als Menge aller wohl-punktierten Koalgebren werden verschiedene Konstruktionen von "kleinen"nichtdeterministischen Automaten fuer jede regulaere Sprache praesentiert.Diese Konstruktionen sind abhaengig von der Wahl der Basiskategorie, in der die Automatenals endliche Koalgebren dargestellt werden. Beispielsweisefuehrt die Kategorie der Booleschen Algebren zum "Atomaton" von Brzozowski und Tamm,waehrend die Kategorie der distributiven Verbaende eine neue Konstruktion ergibt. Im Projekt werden die verschiedenen Konstruktionen erforscht und verglichen, und hinreichendeBedingungen dafuer formuliert, dass der Automat zustandsminimal ist.Ein zweiter Bereich, in dem endliche Koalgebren eine wesentliche Rolle spielen, ist Rekursion.In unseren Vorarbeiten haben wir Algebren konstruiert, die iterativ sind in dem Sinne, dassfuer jede Koalgebra, deren unterliegendes Objekt endlich praesentiert ist, genau ein Koalgebra-zu-Algebra Homomorphismus existiert. In einigen Anwendungen erwies sich die endliche Praesentierbarkeit als zu stark und Koalgebren mit endlich erzeugtenunterliegenden Objekten mussten betrachtet werden; in anderen Anwendungen spielten nur dieendlich erzeugten freien Objekte eine Rolle. Wir planen deswegen die Erforschung von Rekursion mit einem allgemeinem Parameter, der die Darstellung von Endlichkeit inAbhaengigkeit von der jeweiligen Anwendung waehlbar macht.

• DFG-Verfahren: Sachbeihilfen