Definierbarkeit von Baumtransformationen

• Antragsteller: Professor Dr. Sebastian Maneth
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 441896869

In diesem Projekt soll der Wissensstand über Baum Transduktoren (tree transducer, oder auch"Baumübersetzer") erheblich erweitert werden, indem mehrere offene und schwierige Fragestellungen gelöst werden. Diese Fragestellungen beziehen sich auf sogenannte "Definierbarkeitsprobleme". In einem Definierbarkeitsproblem möchte man entscheiden, ob eine Transformation einer gegebenen größeren Klasse von transducers auch realisiert werden kann von einem transducer eine gegebenen kleineren Klasse. Oft entsteht die kleinere Klasse durch eine Ressourcenbeschränkung der größeren Klasse. Beispielsweise möchten man entscheiden, ob eine gegebene Übersetzung von einem transducer realisiert werden kann, der Strom-basiert und mit konstantem Speicheraufwand realisiert werden kann.Die drei Definierbarkeitsprobleme, mit denen wir uns im Speziellen beschäftigen wollen sind diese:1. Ist es entscheidbar, ob eine gegebene funktionale bottom-up Baumtransformation auch durch eine top-down transducer realisierbar ist?2. Ist es entscheidbar, ob die Transformation eines gegebenen attributwerten transducers auch mit Hilfe eines top-down transducers realisiert werden kann?3. Ist eine gegebene macro tree transformation genau dann durch einen attributierten Transducer darstellbar, wenn diese einen linearen Wachstum von Größe des Eingabebaums nach Anzahl der distinction Ausgabeunterbäume besitzt?

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Belgien, Frankreich, Niederlande
• Kooperationspartner: Professor Dr. Joost Engelfriet; Dr. Emmanuel Filiot; Professor Dr. Jean-Marc Talbot