Detailseite
Projekt Druckansicht

Definierbarkeit von Baumtransformationen

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
 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung