Determinacy and Rewriting of Top-Down and MSO Tree Transformations

Michael Benedikt, Joost Engelfriet, Sebastian Maneth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

A query is determined by a view, if the result to the query can be reconstructed from the result of the view. We consider the problem of deciding for two given tree transformations, whether one is determined by the other. If the view transformation is induced by a tree transducer that may copy, then determinacy is undecidable, even for identity queries. For a large class of non-copying views, namely compositions of functional extended linear top-down tree transducers with regular look-ahead, we show that determinacy is decidable, where queries are given by deterministic top-down tree transducers with regular look-ahead or by MSO tree transducers. We also show that if a query is determined, then it can be rewritten into a query that works directly over the view and is in the same class as the given query. The proof relies on the decidability of equivalence for the two considered classes of queries, and on their closure under composition.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2013
Subtitle of host publication38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages13
ISBN (Electronic)978-3-642-40313-2
ISBN (Print)978-3-642-40312-5
Publication statusPublished - 2013


Dive into the research topics of 'Determinacy and Rewriting of Top-Down and MSO Tree Transformations'. Together they form a unique fingerprint.

Cite this