DECOMPOSING A k-VALUED TRANSDUCER INTO k UNAMBIGUOUS ONES

摘要

Dans cette article, les transducteurs d'image bornée sont examinés en liaison avec leur structure interne. Les modèles de transducteurs qui sont considérés sont les transducteurs finis normalisés (NFT) et les NGSM, qui sont des NFT à temps réel. Il est démontré qu'un NGSM d'image k-bornée M peut être effectivement décomposé en k NGSM non ambigus M_1, …, M_k de telle manière que la transduction réalisée par M soit égale à l'union des transductions réalisées par M_1, …, M_k. Chaque transducteur M_i a une taille doublement exponentielle et peut être calculé en temps déterministe doublement exponentiel. On peut étendre ce résultat aux NFT. En conséquence, les NGSM (resp. NFT) d'image k-bornée et les NGSM (resp. NFT) k-ambigus réalisent la même classe de transductions.%In this article finite-valued transducers are investigated in connection with their inner structure. The transducer models considered are the normalized finite transducer (NFT) and the nondeterministic generalized sequential machine (NGSM), which is a real-time NFT. It is shown that a k-valued NGSM M can be effectively decomposed into k unambiguous NGSMs M_1, …, M_k such that the transduction realized by M is the union of the transductions realized by M_1, …, M_k. Each transducer M_i has double exponential size and can be computed in deterministic double exponential time. This result can be extended to NFTs. As a consequence, the k-valued NGSMs (NFTs) and the k-ambiguous NGSMs (NFTs, respectively) realize the same class of transductions.