Reduktions- und Lerntechniken für omega-Automaten

• Antragsteller: Privatdozent Dr. Christof Löding
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 442233282

In diesem Projekt sollen Reduktions- und Lerntechniken für Automaten auf unendlichen Wörtern (omega-Automaten) untersucht werden. Ein zentraler Aspekt ist die Entwicklung von Algorithmen zur Konstruktion von omega-Automaten aus endlichen Mengen von Beispielwörtern. Im Fall der endlichen Wörter gibt es bereits viele Arbeiten zu diesem Problem, für unendliche Wörter hingegen gibt es kaum Ergebnisse dazu. Als weiteres Ziel soll die Theorie aktiver Lernalgorithmen (basierend auf Anfragen) für omega-Automaten weiterentwickelt werden. Im Bereich der Reduktion von omega-Automaten geht es einerseits um effiziente Heuristiken zur Rekuktion der Zustandszahl von deterministischen omega-Automaten (bereits während der Determinisierung und auch für bereits gegebene deterministische Automaten). Andererseits sollen auch Aspekte der exakten Minimierung studiert werden, welche deutlichkomplexer ist als für klassische deterministische Automaten auf endlichen Wörtern.

• DFG-Verfahren: Sachbeihilfen