On the valuedness of finite transducers (Q1120286)

We investigate the valuedness of finite transducers in connection with their inner structure. We show: the valuedness of a finite-valued nondeterministic generalized sequential machine (NGSM) M with n states and output alphabet \(\Delta\) is at most the maximum of \((1-\lfloor 1/\#\Delta \rfloor)\cdot (2^{k_ 1}\cdot k_ 3)^ n\cdot n^ n\cdot \#\Delta^{n^ 3\cdot k_ 4/3}\) and \(\lfloor 1/\#\Delta \rfloor \cdot (2^{k_ 2}\cdot k_ 3\cdot (1+k_ 4))^ n\cdot n^ n\) where \(k_ 1\leq 6.25\) and \(k_ 2\leq 11.89\) are constants and \(k_ 3\geq 1\) and \(k_ 4\geq 0\) are local structural parameters of M. There are two simple criteria which characterize the infinite valuedness of an NGSM. By these criteria, it is decidable in polynomial time whether or not an NGSM is infinite-valued. In both cases, {\#}\(\Delta\) \(>1\) and {\#}\(\Delta\) \(=1\), the above upper bound for the valuedness is almost optimal. By reduction, all results can be easily generalized to normalized finite transducers.