Determinacy and rewriting of functional top–down and MSO tree transformations

M. Benedikt, J. Engelfriet, S. Maneth

Research output: Contribution to journalArticlepeer-review


A query is determined by a view, if the result of the query can be reconstructed from the result of the view. We consider the problem of deciding for two given (functional) 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. For a large class of noncopying views, namely compositions of extended linear top–down tree transducers, we show that determinacy is decidable, where queries are either deterministic top–down tree transducers (with regular look-ahead) or deterministic MSO tree transducers. We also show that if a query is determined by a view, then it can be rewritten into a query that works over the view and is in the same class of transducers as the query. The proof relies on the decidability of equivalence for the considered classes of queries, and on their composition closure.
Original languageEnglish
Pages (from-to)57-73
Number of pages17
JournalJournal of Computer and System Sciences
Early online date22 Nov 2016
Publication statusPublished - May 2017


  • View–query determinacy
  • Top–down tree transducers
  • MSO definable tree transducers


Dive into the research topics of 'Determinacy and rewriting of functional top–down and MSO tree transformations'. Together they form a unique fingerprint.

Cite this