Lokale Divisoren in Halbgruppen und Formalen Sprachen

• Antragsteller: Professor Dr. Volker Diekert; Dr. Manfred Kufleitner
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 233994807

Das Projekt zielt auf eine Reihe von aktiven Forschungsthemen im Zusammenspiel zwischen den Gebieten der formalen Sprachen, endlichen Halbgruppen, Automatentheorie und Logik ab. Wir konzentrieren uns auf sechs Ziele, bei denen neu entwickelte Techniken benutzt werden, um den derzeitigen Forschungsstand voranzubringen. Die Motivation für dieses Projekt hat sich durch Vorarbeiten während der vergangenen zwei Jahre entwickelt. Als der erste Antragsteller 2004 die mathematische Technik der lokalen Divisoren von endlichen Monoiden entwickelte (und dabei eine Konstruktion von Meyberg aus dem Jahr 1972 verfeinerte), wurde dies gemacht, um die volle Ausdrucksstärke von lokalem LTL über Mazurkiewicz Spuren zu beweisen. In den letzten Jahren haben wir bemerkt, dass lokale Divisoren ein sehr allgemeines und mächtiges Induktionsschema ermöglichen, welches sich für zahlreiche Situationen eignet -- wie z.B. die Krohn-Rhodes Zerlegung. Dieses neue Beweisschema teilt einen "großen" Induktionsschritt in mehrere "winzige" Schritte auf. Im letzten Jahr waren wir in der Lage unsere Technik der lokalen Divisoren weiter zu verbessern und diese Methode auf offene Probleme der klassischen Theorie der formalen Sprachen anzuwenden; und wir waren sofort erfolgreich! Dies wird z.B. durch Publikationen bei den Konferenzen CSR 2012 und ICALP 2012 belegt. Natürlich kann ein Beweisschema für sich noch keine Lösung für offene Probleme liefern. Ebenso eignet sich auch nicht jedes Problem dazu, mit lokalen Divisoren gelöst zu werden. Wir haben sechs Ziele identifiziert, bei denen ein Lösungsansatz mit lokalen Divisoren sehr vielversprechend ist. Zusätzlich wird das Projekt von der international anerkannten Fachkompetenz der Antragsteller sowie von bereits existierenden erfolgreichen Kooperationen mit weiteren führenden Experten auf diesem Forschungsgebiet profitieren.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Frankreich, Kanada
• Beteiligte Personen: Professor Dr. Markus Lohrey; Dr. Klaus Reinhardt; Professor Dr. Benjamin Steinberg; Professor Dr. Pascal Weil