Language Recognition by Algebra and Topology

• Applicant: Privatdozent Dr. Andreas Krebs
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 219077758

Sprachklassen unterhalb der regulären Sprachen lassen sich durch Klassen von endlichen Monoiden beschreiben. Diese strukturelle Gleichheit wurde detailliert für Unterklassen der regulären Sprachen analysiert und zum Teil verwendet um Komplexitätsklassen zu trennen. Wenn man über reguläre Sprachen hinausgeht, reichen endliche Monoide nicht mehr aus. Bei unendlichen Monoiden ist aber eine zusätzlich Struktur nötig, damit diese nicht zu „mächtig“ werden. Wir haben in diesem Bereich einen Ansatz geschaffen, Monoide mit weiteren endlichen Strukturen zu versehen. Unser Ansatz ermöglicht es, beliebige Sprachklassen konkret zu charakterisieren und hat es auch erlaubt, Trennungsergebnisse zu erreichen. Ein anderer Ansatz besteht darin, die Monoide mit einer Topologie oder genauer einer Uniformität zu erweitern und dann den topologischen Abschluss zu betrachten. Dieser Ansatz scheint ein größeres Potential zu haben, bisher sind aber kaum konkrete Beispiele bekannt. In diesem Projekt sollen die Gemeinsamkeiten der beiden Ansätze untersucht werden. Ein Schwerpunkt soll dabei sein, dem topologischen Ansatz eine konstruktive Komponente zu geben.

• DFG Programme: Research Grants