Deciding whether an Attributed Translation can be realized by a Top-Down Transducer

Sebastian Maneth, Martin Vu

We prove that for a given partial functional attributed tree transducer with monadic output, it is decidable whether or not an equivalent top-down transducer (with or without look-…