Decomposing A k-Valued Transducer into k Unambiguous Ones
Decomposing A k-Valued Transducer into k Unambiguous Ones
复制标题
将 k 值换能器分解为 k 个明确的换能器
DOI：
10.1051/ita/1996300503791
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
M. Weber
中科院分区：
文献类型：
--
作者：
M. Weber
我们研究了有限值有限换能器的内部结构。我们的传感器模型是归一化有限传感器（NFT）和非确定性广义序列机（NGSM），这是一种实时 NFT。我们证明： k 值 NGSM M 可以有效地分解为 k 个明确的 NGSM M1,..., M k ，使得 M 实现的换能是 M1..., M k 实现的换能的并集。每个M i 具有双指数大小并且可以在确定性双指数时间内构造。通过约简，这个结果可以扩展到 NFT。因此，k 值 NGSM 和 k 模糊 NGSM (NFT) 具有相同的生成能力。
We investigate the inner structure of finite-valued finite transducers. Our transducer models are the normalized finite transducer (NFT) and the non-deterministic generalized sequential machine (NGSM), which is a real-time NFT. We show: A k-valued NGSM M can be effectively decomposed into k unambiguous NGSMs M1,..., M k such that the transduction realized by M is the union of the transductions realized by M1..., M k . Each M i is of double exponential size and can be constructed in deterministic double exponential time. By reduction, this result can be extended to NFTs. As a consequence, the k-valued and the k-ambiguous NGSMs (NFTs) have the same generative power.