zbMATH — the first resource for mathematics

On the valuedness of finite transducers. (English) Zbl 0672.68027
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.
Reviewer: A.Weber

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI