Helmut Seidl. Equivalence of Finite-Valued Tree Transducers Is Decidable. Mathematical Systems Theory, 27(4):285-346, 1994.
A bottom-up finite state tree transducer (FST) is called
-valued if f for every input tree there are at mostk different output trees.
is called finite-valued if it is
-valued for some
. We show that it is decidable for every
whether or not a given FST
is
-valued. We give an effective characterization of all finite-valued FSTs and derive a (sharp) upper bound for the valuedness provided it is finite. We decompose a finite-valued FSTM into a finite number of single-valued FSTs. This enables us to prove: it is decidable whether or not the translation of an FSTM is included in the translation of a finite-valued FSTM'. We also consider these questions for size-valuedness.