This Issue


International Journal of Foundations of Computer Science: Vol. 13, No. 01
Print ISSN: 0129-0541
Online ISSN: 1793-6373

 
writing-guides   ealerts
Connect with WS
 


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

Received: 13 December 2000
Revised: 6 April 2001

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.

Keywords: finite automata; finite-state transducers; rational power series; semirings; ∊-removal; shortest-paths algorithms
Cited by (17):
, . (2015) Parallel Fuzzy Regular Expression and its Conversion to Epsilon-Free Fuzzy Automaton. The Computer Journal, bxv104. Online publication date: 17-Dec-2015. [CrossRef]
, . (2014) The most probable string: an algorithmic study. Journal of Logic and Computation 24:2, 311-330. Online publication date: 1-Apr-2014. [CrossRef]
. (2013) A Note on Probabilistic Models over Strings: The Linear Algebra Approach. Bulletin of Mathematical Biology 75:12, 2529-2550. Online publication date: 1-Dec-2013. [CrossRef]
, , , , . (2013) Algorithmic probabilistic game semantics. Formal Methods in System Design 43:2, 285-312. Online publication date: 1-Oct-2013. [CrossRef]
, . (2013) THE VALIDITY OF WEIGHTED AUTOMATA. International Journal of Algebra and Computation 23:04, 863-913. Online publication date: 1-Jun-2013. [Abstract | PDF (1050 KB) | PDF Plus (1061 KB)]
, . (2013) Efficient algorithm for rational kernel evaluation in large lattice sets. 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, 3133-3137. [CrossRef]
, . (2013) Speech Recognition Algorithms Using Weighted Finite-State Transducers. Synthesis Lectures on Speech and Audio Processing 9:1, 1-162. Online publication date: 15-Jan-2013. [CrossRef]
, , , , . (2011) WFST Enabled Solutions to ASR Problems: Beyond HMM Decoding. IEEE Transactions on Audio, Speech, and Language Processing. Online publication date: 1-Jan-2011. [CrossRef]
, . (2010) On the construction of probabilistic diagnosers. IFAC Proceedings Volumes 43:12, 229-234. Online publication date: 1-Jan-2010. [CrossRef]
, , . (2008) Kernel methods for learning languages. Theoretical Computer Science 405:3, 223-236. Online publication date: 1-Oct-2008. [CrossRef]
, , , . (2008) ON THE COMPUTATION OF THE RELATIVE ENTROPY OF PROBABILISTIC AUTOMATA. International Journal of Foundations of Computer Science 19:01, 219-242. Online publication date: 1-Feb-2008. [Abstract | PDF (1286 KB) | PDF Plus (353 KB)]
, , . (2007) Lp DISTANCE AND EQUIVALENCE OF PROBABILISTIC AUTOMATA. International Journal of Foundations of Computer Science 18:04, 761-779. Online publication date: 1-Aug-2007. [Abstract | PDF (1030 KB) | PDF Plus (322 KB)]
, , . (2007) PATH-EQUIVALENT DEVELOPMENTS IN ACYCLIC WEIGHTED AUTOMATA. International Journal of Foundations of Computer Science 18:04, 799-811. Online publication date: 1-Aug-2007. [Abstract | PDF (684 KB) | PDF Plus (257 KB)]
. (2003) EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS. International Journal of Foundations of Computer Science 14:06, 957-982. Online publication date: 1-Dec-2003. [Abstract | PDF (1400 KB) | PDF Plus (531 KB)]
. (2003) Morphology in Machine Translation Systems: Efficient Integration of Finite State Transducers and Feature Structure Descriptions. Machine Translation 18:3, 217-238. Online publication date: 1-Sep-2003. [CrossRef]
, , , . A generalized construction of integrated speech recognition transducers. 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing, I-761-4. [CrossRef]
, , . Large vocabulary continuous Mandarin speech recognition using finite state machine. SympoTIC '04. Joint 1st Workshop on Mobile Future & Symposium on Trends In Communications (IEEE Cat. No.04EX877), 5-8. [CrossRef]