Shape preserving top-down tree transducers

As top-down tree transducers generalize generalized sequential machines, shape preserving top-down tree transducers naturally generalize length preserving generalized sequential machines. For instance, top-down relabeling tree transducers are shape preserving top-down tree transducers. We show that a top-down tree transducer is shape preserving if and only if it is equivalent to a top-down relabeling tree transducer. We also prove that it is decidable if a top-down tree transducer is shape preserving.

Authors

• Zoltán Fülöp
• Zsolt Gazdag

Keywords

No keywords are indexed for this paper.