On the Decidability of the Equivalence for k-Valued Transducers

摘要

We give a new proof for the decidability of the equivalence of two k-valued transducers, a result originally established by Culik and Karhumaki and independently by Weber. Our proof relies on two constructions we have recently introduced to decompose a k-valued transducer and to decide whether a transducer is k-valued. As a result, our proof is entirely based on the structure of the transducers under inspection, and the complexity it yields is of single exponential order on the number of states. This improves Weber's result by one exponential.