Is it possible for MSO graph/tree transducers to reflect themselves, namely to create an interpreter of tree/graph transducers using tree/graph transducers? If yes, I'll be happy for some design guidelines.

  • $\begingroup$ 1. Rather than modifying the question in a way that invalidates the answer to your original question, it's probably better to leave the original one and ask a new question.... 2. How do you want the input tree transducer to be represented? I suspect the answer might depend on the representation. Presumably you want it to be represented as a tree somehow, but it's not clear to me what that might look like (a tree isn't exactly the most obvious representation for such a transducer). $\endgroup$
    – D.W.
    Commented Aug 21, 2016 at 18:30
  • $\begingroup$ will accept your answer and open a new question with a better desc of what i really want, thanks! what i really want is a language that can reason over itself, but having a complete logic. like mltt, but mltt isn't complete, it's decidability window is quite narrow $\endgroup$ Commented Aug 21, 2016 at 20:38
  • $\begingroup$ as for your second point, a transducer is trivially represented as a graph $\endgroup$ Commented Aug 21, 2016 at 22:30
  • $\begingroup$ So do you only want to ask the question about graph transducers? Or do you still want to ask about tree transducers, too? if so, how do you plan to address that, for tree transducers? $\endgroup$
    – D.W.
    Commented Aug 21, 2016 at 22:37
  • $\begingroup$ the question meant for either trees or graphs, not trees and graphs (and mso over graphs is reducible to mso over trees) $\endgroup$ Commented Aug 21, 2016 at 23:19

1 Answer 1


Not in any straightforward way, because a tree transducer only accepts a single input, while an interpreter needs two inputs.

An interpreter needs two inputs: a transducer $R$ and a tree $T$, and would output the $R(T)$. But a tree transducer can only accept one input.

Consequently, there appears to be no way to build such an interpreter (unless you accept some crazy way of pre-processing the inputs to bring them into a form that they can be provided to a tree transducer -- but it's hard to see how to define that in a way that rules out trivial solutions where it's the pre-processor that's actually doing all the interpreting).

  • $\begingroup$ sure, guess i need to rephrase the question. i still need to think how to write it correctly. in general, i'd like to implement (if possible) a programming language being basically MSO over graphs to interpret itself, where the language looks like prolog (kb and query). $\endgroup$ Commented Aug 21, 2016 at 11:54
  • $\begingroup$ another reformulation would be remaining the question as-is, just replacing "interpreter" with "compiler", to say assembly code $\endgroup$ Commented Aug 21, 2016 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.