Eindeutige endliche Automaten auf unendlichen Wörtern

Eindeutige Maschinen- und Automatenmodelle sind in der (theoretischen) Informatik ein wichtiger Forschungsgegenstand. Ergebnisse des Antragstellers mit einem Doktoranden zeigen, dass strikt eindeutige omega-Automaten -- auch prophetische Automaten genannt -- gewinnbringend bei der Klassifizierung von temporalen Eigenschaften eingesetzt werden können. Ziel des Vorhabens ist es, aus den bisherigen Ergebnissen zu eindeutigen omega-Automaten eine umfassende Theorie der eindeutigen und strikt eindeutigen omega-Automaten zu entwickeln, um unter anderem beurteilen zu können, in welchen Situationen der Einsatz dieser Automaten zu besseren Ergebnissen als der Einsatz von deterministischen oder nichtdeterministischen Automaten führt. Insbesondere soll untersucht werden, ob und gegebenenfalls wie durch strikt eindeutige Automaten auch komplexere Klassifizierungsprobleme für omega-Sprachen und Logiken auf unendlichen Wörtern gelöst werden können.

DFG-Verfahren Sachbeihilfen