# Can Tree Transducers Self-Interpret?

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.

• 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). – D.W. Aug 21 '16 at 18:30
• 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 – Troy McClure Aug 21 '16 at 20:38
• as for your second point, a transducer is trivially represented as a graph – Troy McClure Aug 21 '16 at 22:30
• 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? – D.W. Aug 21 '16 at 22:37
• the question meant for either trees or graphs, not trees and graphs (and mso over graphs is reducible to mso over trees) – Troy McClure Aug 21 '16 at 23:19

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.