An algebraic theory of distance automata

• Applicant: Dr. Daniel Kirsten
• Subject Area: Theoretical Computer Science
• Term: from 2002 to 2004
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Fellowships