Deciding Whether an Attributed Translation can be Realized by a Top-Down Transducer

We prove that for a given partial deterministic attributed tree transducer with monadic output, it is decidable whether or not an equivalent top-down tree transducer (with or without look-ahead) exists. We present a procedure that constructs such an equivalent top-down tree transducer (with or without look-ahead) if it exists. We then show that our results can be extended to arbitrary nondeterministic attributed tree transducer with look-around that have monadic output.