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) $M$ is called $k$ -valued if f for every input tree there are at mostk different output trees. $M$ is called finite-valued if it is $k$ -valued for some $k$ . We show that it is decidable for every $k$ whether or not a given FST $M$ is $k$ -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