patternMinor
Can Tree Transducers Self-Interpret?
Viewed 0 times
caninterprettransducerstreeself
Problem
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.
Solution
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).
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).
Context
StackExchange Computer Science Q#62746, answer score: 2
Revisions (0)
No revisions yet.