GENERIC ∊-REMOVAL AND INPUT ∊-NORMALIZATION ALGORITHMS FOR WEIGHTED TRANSDUCERS

作     者：MEHRYAR MOHRI 

作者机构：AT&T Labs - Research 180 Park Avenue Room E135 Florham Park NJ 07932 USA 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：2002年第13卷第1期

页      面：129-143页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：finite automata finite-state transducers rational power series semirings ∊-removal shortest-paths algorithms 

摘      要：We present a new generic ∊-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 illustrate the use of the algorithm with several semirings. We also describe an input ∊-normalization algorithm for weighted transducers based on the general shortest-distance algorithm. The algorithm, which works with all semirings covered by our framework, admits an on-the-fly implementation.