On the lengths of values in a finite transducer (Q1323379)

We investigate finite transducers and their inner structure with regard to the lengths of values. Our transducer models are the normalized finite transducer (NET) and the nondeterministic generalized sequential machine (NGSM), which is a real-time NFT. The length-degree of an NFT is defined to be the maximal number of different lengths of values for an input word or is infinite, depending on whether or not a maximum exists. We show: An NGSM \(M\) with finite length-degree can be effectively decomposed into finitely many NGSMs \(M_ 1,\dots,M_ N\) having length-degree at most 1 such that the transduction realized by \(M\) is the union of the transductions realized by \(M_ 1,\dots,M_ N\). Using this decomposition, the equivalence of NGSMs with finite length-degree is recursively decidable. Whether or not an NGSM has finite length-degree can be decided in deterministic polynomial time. By reduction, all these results can be generalized to NFTs.