Generic epsilon -Removal Algorithm for Weighted Automata
Generic epsilon -Removal Algorithm for Weighted Automata
复制标题
加权自动机的通用 epsilon 去除算法
DOI：
10.1007/3-540-44674-5_19
复制
发表时间：
2000
影响因子：
--
通讯作者：
Mehryar Mohri
中科院分区：
文献类型：
--
作者：
Mehryar Mohri
我们提出了一个新的通用的e-删除算法的加权自动机和转换器定义在一个半环。该算法可以用于任何半环覆盖我们的框架和工程与任何队列纪律。它特别适用于定义在热带半环上的非加权自动机和变换器以及加权自动机和变换器。它是基于我们简要描述的一般最短距离算法。我们给出了一个完整的描述，包括它的伪代码和它的运行时间复杂度的算法，讨论了更有效的情况下，无环自动机，一个在飞行中实现的算法和近似算法的情况下，我们的框架不包括半环。我们还用几个半环说明了该算法的使用。
We present a new generic e-removal algorithm for weighted automata and transducers defined over a semiring. The algorithm can be used with any semiring covered by our framework and works with any queue discipline adopted. It can be used in particular in the case of unweighted automata and transducers and weighted automata and transducers defined over the tropical semiring. It is based on a general shortest-distance algorithm that we briefly describe. We give a full description of the algorithm including its pseudocode and its running time complexity, discuss the more efficient case of acyclic automata, an on-the-fly implementation of the algorithm and an approximation algorithm in the case of the semirings not covered by our framework. We also illustrate the use of the algorithm with several semirings.