Decomposing Finite-Valued Transducers and Deciding Their Equivalence
Andreas Weber⋆ · SIAM Journal on Computing · 1993
In this paper finite-valued finite transducers are investigated in connection with their inner structure. The following results are shown: A finite-valued nondeterministic generalized sequential machine (NGSM) M can be effectively decomposed into finitely many single-valued NGSMs $M_1 , \ldots ,M_N $ such that the transduction realized by M is the union of the transductions realized by $M_1 , \ldots ,M_N $. Using this decomposition, the equivalence of finite-valued NGSMs is decidable in deterministic double exponential time. By reduction, both results can be generalized to normalized finite transducers.