Weighted Transducer Algorithms


Description

Weighted finite-state transducers, or weighted transducers, are used in a variety of applications such as computational biology, image processing, text and speech processing. Many essential weighted automata and transducer algorithms are relatively recent. This pages lists several weighted automata and transducer algorithms and some of the references for their implementation in the FSM Library or OpenFst.



Tutorial chapters

Mehryar Mohri.
Weighted automata algorithms.
In Manfred Droste, Werner Kuich, and Heiko Vogler, editors, Handbook of Weighted Automata. Monographs in Theoretical Computer Science, pages 213-254. Springer, 2009.

Mehryar Mohri.
Statistical Natural Language Processing.
In M. Lothaire, editor, Applied Combinatorics on Words. Cambridge University Press, 2005.


Learning Weighted Automata

Borja Balle and Mehryar Mohri.
Spectral learning of general weighted automata via constrained matrix completion.
In Advances in Neural Information Processing Systems (NIPS 2012). Lake Tahoe, Nevada, 2012. MIT Press.


Rational Operations: Sum, Product, and Closure of Weighted Finite-State Transducers

Mehryar Mohri, Fernando C. N. Pereira, and Michael Riley.
The Design Principles of a Weighted Finite-State Transducer Library.
Theoretical Computer Science, 231:17-32, January 2000.


Elementary Unary Operations: Reversal, Inversion, Projection.

Mehryar Mohri, Fernando C. N. Pereira, and Michael Riley.
The Design Principles of a Weighted Finite-State Transducer Library.
Theoretical Computer Science, 231:17-32, January 2000.


Composition of Weighted Finite-State Transducers, Intersection of Weighted Automata, Difference of Automata

Mehryar Mohri, Fernando C. N. Pereira, and Michael Riley.
Weighted Automata in Text and Speech Processing.
In Proceedings of the 12th biennial European Conference on Artificial Intelligence (ECAI-96), Workshop on Extended finite state models of language. Budapest, Hungary, 1996. ECAI.

Fernando C. N. Pereira and Michael Riley.
Speech Recognition by Composition of Weighted Finite Automata .
In E. Roche and Y. Schabes, editors, Finite-State Language Processing. MIT Press, Cambridge, Massachusetts. 1997.

Cyril Allauzen and Mehryar Mohri.
N-way composition of weighted finite-state transducers.
International Journal of Foundations of Computer Science, 20(4):613-627, 2009.


Epsilon-Removal of Weighted Finite-State Transducers

Mehryar Mohri.
Generic Epsilon-Removal and Input Epsilon-Normalization Algorithms for Weighted Transducers.
International Journal of Foundations of Computer Science, 13(1):129-143, 2002.

Mehryar Mohri.
Generic Epsilon-Removal Algorithm for Weighted Automata.
In Sheng Yu and Andrei Paun, editor, 5th International Conference, CIAA 2000, London Ontario, Canada. volume 2088 of Lecture Notes in Computer Science, pages 230-242. Springer-Verlag, Berlin-NY, 2001.


Disambiguation of Finite Automata and Finite-State Transducers

Mehryar Mohri and Michael D. Riley.
On the disambiguation of weighted automata.
ArXiv 1405.0500. May 2014.

Mehryar Mohri.
On the disambiguation of finite automata and functional transducers.
International Journal of Foundations of Computer Science, 24(6):847-862, 2013.


Determinization of Finite-State Transducers

Mehryar Mohri.
On some Applications of Finite-State Automata Theory to Natural Language Processing.
Journal of Natural Language Engineering, 2:1-20, 1996.

Cyril Allauzen and Mehryar Mohri.
An Optimal Pre-Determinization Algorithm for Weighted Transducers.
Theoretical Computer Science, 328(1-2):3-18, November 2004.

Cyril Allauzen and Mehryar Mohri.
Finitely Subsequential Transducers.
International Journal of Foundations of Computer Science, 14(6):983-994, 2003.


Determinization of Weighted Automata and Weighted Finite-State Transducers

Mehryar Mohri.
Finite-State Transducers in Language and Speech Processing.
Computational Linguistics, 23:2, 1997.


Minimization of Finite-State Transducers

Mehryar Mohri.
Minimization Algorithms for Sequential Transducers.
Theoretical Computer Science, 234:177-201, March 2000.

Mehryar Mohri.
Minimization of Sequential Transducers.
In Maxime Crochemore and Dan Gusfield, editors, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching (CPM '94). volume 807 of Lecture Notes in Computer Science, pages 151-163, Asilomar, California, June 5-8 1994. Springer-Verlag, Berlin-NY.


Minimization of Weighted Automata and Weighted Transducers

Mehryar Mohri.
Finite-State Transducers in Language and Speech Processing.
Computational Linguistics, 23:2, 1997.


Equivalence of Subsequential Weighted Automata

Mehryar Mohri.
Finite-State Transducers in Language and Speech Processing.
Computational Linguistics, 23:2, 1997.


Equivalence of Subsequential Finite-State Transducers

Mehryar Mohri.
Minimization Algorithms for Sequential Transducers.
Theoretical Computer Science, 234:177-201, March 2000.


Divergences/Distances between Weighted Automata

Corinna Cortes, Mehryar Mohri, Ashish Rastogi, and Michael Riley.
On the computation of the relative entropy of probabilistic automata.
International Journal of Foundations of Computer Science, 19(1):219-242, 2008.

Corinna Cortes, Mehryar Mohri, and Ashish Rastogi.
Lp Distance and Equivalence of Probabilistic Automata.
International Journal of Foundations of Computer Science, 18(4):761-780, 2007.

Mehryar Mohri.
Edit-Distance of Weighted Automata: General Definitions and Algorithms.
International Journal of Foundations of Computer Science, 14(6):957-982, 2003.

Mehryar Mohri.
Edit-Distance of Weighted Automata.
In Jean-Marc Champarnaud and Denis Maurel, editor, Seventh International Conference, CIAA 2002, Tours, France. volume 2608 of Lecture Notes in Computer Science, pages 1-23. Springer, Berlin-NY, April 2003.


Synchronization of Weighted Finite-State Transducers

Mehryar Mohri.
Edit-Distance of Weighted Automata: General Definitions and Algorithms.
International Journal of Foundations of Computer Science, 14(6):957-982, 2003.

Mehryar Mohri.
Edit-Distance of Weighted Automata.
In Jean-Marc Champarnaud and Denis Maurel, editor, Seventh International Conference, CIAA 2002, Tours, France. volume 2608 of Lecture Notes in Computer Science, pages 1-23. Springer, Berlin-NY, April 2003.


Input Epsilon-Normalization of Weighted Finite-State Transducers

Mehryar Mohri.
Generic Epsilon-Removal and Input Epsilon-Normalization Algorithms for Weighted Transducers.
International Journal of Foundations of Computer Science, 13(1):129-143, 2002.


Weight Pushing

Mehryar Mohri,
Formal Languages and Applications. chapter Weighted Finite-State Transducer Algorithms: An Overview, Physica-Verlag, Heidelberg, (to appear), 2004.

Mehryar Mohri.
General Algebraic Frameworks and Algorithms for Shortest-Distance Problems. Technical Memorandum 981210-10TM, AT&T Labs - Research, 62 pages, 1998.

Mehryar Mohri.
Finite-State Transducers in Language and Speech Processing.
Computational Linguistics, 23:2, 1997.


Ambiguity of Weighted Automata

Cyril Allauzen, Mehryar Mohri, and Ashish Rastogi.
General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers.
International Journal of Foundations of Computer Science, 22(4), 2011.

Cyril Allauzen, Mehryar Mohri, and Ashish Rastogi.
General algorithms for testing the ambiguity of finite automata.
In Proceedings of Twelfth International Conference Developments in Language Theory (DLT 2008). volume 5257 of Lecture Notes in Computer Science, Kyoto, Japan, September 2008. Springer, Heidelberg, Germany.


Generic Single-Source and All-Pairs Shortest-Distance Algorithms

Mehryar Mohri.
Semiring Frameworks and Algorithms for Shortest-Distance Problems.
Journal of Automata, Languages and Combinatorics, 7(3):321-350, 2002.

Mehryar Mohri.
General Algebraic Frameworks and Algorithms for Shortest-Distance Problems. Technical Memorandum 981210-10TM, AT&T Labs - Research, 62 pages, 1998.


N-Best-Paths and N-Best-String Algorithms

Mehryar Mohri and Michael Riley.
An Efficient Algorithm for the N-Best-Strings Problem.
In Proceedings of the International Conference on Spoken Language Processing 2002 (ICSLP '02). Denver, Colorado, September 2002.