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.
Download: PDF Reference: Bibtex