Helmut Seidl. Equivalence of Finite-Valued Bottom-up Finite State Tree Transducers Is Decidable. In André Arnold, editor, CAAP, volume 431 of Lecture Notes in Computer Science, pages 269-284, Copenhagen, Denmark, May 1990. Springer.
A bottom-up finite state tree transducer (FST) A is called k-valued iff for every input tree there are at most k different output trees. A is called finite-valued iff it is k-valued for some k. We show: it is decidable for every k whether or not a given FST A is k-valued, and it is decidable whether or not A is finite-valued. We give an effective characterization of all finite-valued FST's and derive a (sharp) upper bound for the valuedness provided it is finite. We decompose a finite-valued FST A into a finite number of single-valued FST's. This enables us to prove: it is decidable whether or not the translation of an FST A is included in the translation of a finite-valued FST A'.
Reference: Bibtex The original publication is available at www.springerlink.com