Eine algebraische Theorie von Distanzautomaten

• Antragsteller: Dr. Daniel Kirsten
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2002 bis 2004
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5389415

Distanzautomaten, auch bekannt als Automaten mit einer Bewertung im tropischen Semiring oder min-plus bewertete Automaten, sind in der Informatik von praktischen und theoretischen Interesse. In der Industrie werden Distanzautomaten zur Entwicklung von Spracherkennungssystemen und zur Kompression von Bild- und Videodaten in Internet eingesetzt. In der Theoretischen Informatik wurden Distanzautomaten u.a. von Hashiguchi, Leung und Simon benutzt, um das Sternhöhenproblem und andere Probleme in der Strukturtheorie der erkennbaren Sprachen zu lösen. Die teilweise beeindruckenden Forschungsergebnisse in diesem Bereich sind jedoch in zahlreichen, mitunter kaum verstandenen Arbeiten verstreut, so dass man nicht von einer einheitlichen Theorie von Distanzautomaten sprechen kann. Ausgehend von meinem neuen Beweis für die Entscheidbarkeit der Finite Power Property will ich in dem Forschungsvorhaben die bisherigen Ideen zu Distanzautomaten zusammenführen, weiterentwickeln und vereinfachen, um zu einer einheitlichen, algebraischen Theorie von Distanzautomaten zu gelangen. In dieser Theorie will ich Komplexitätsergebnisse erzielen und Zusammenhänge zwischen der Sternhöhenhierarchie und anderen Hierarchien erkennbarer Sprachen herausarbeiten. Weiterhin möchte ich Verallgemeinerungen dieser Theorie auf Spurmonoide untersuchen.

• DFG-Verfahren: Forschungsstipendien