caa a22 4500 467989842 CHVBK 20180323112541.0 cr unu---uuuuu 170328e19900901xx s 000 0 eng 10.1007/BF00264285 doi (NATIONALLICENCE)springer-10.1007/BF00264285 Weber Andreas Fachbereich Informatik, J.W. Goethe-Universität, Postfach 111932, D-6000, Frankfurt am Main 11, Federal Republic of Germany aut On the valuedness of finite transducers [Elektronische Daten] [Andreas Weber] Summary: 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 Δ is at most the maximum of (1-⌊1/#Δ⌋) · (2 k 1 · k 3 ) n · n n ·#Δ n 3 ·k 4 / 3 and ⌊1/#Δ⌋·(2 k 2 ·k 3 ·(1+k 4 )) n ·n n where k 1≦6.25 and k 2≦11.89 are constants and k 3≧1 and k 4≧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, #Δ > 1 and #Δ = 1, the above upper bound for the valuedness is almost optimal. By reduction, all results can be easily generalized to normalized finite transducers. Springer-Verlag, 1990 Acta Informatica Springer-Verlag 27/8(1990-09-01), 749-780 0001-5903 27:8<749 1990 27 236 https://doi.org/10.1007/BF00264285 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00264285 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Weber Andreas Fachbereich Informatik, J.W. Goethe-Universität, Postfach 111932, D-6000, Frankfurt am Main 11, Federal Republic of Germany aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 27/8(1990-09-01), 749-780 0001-5903 27:8<749 1990 27 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer