Description

Tutorial chapters

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

On the Rademacher complexity of weighted automata.

In Proceedings of The 26th International Conference on Algorithmic Learning Theory (ALT 2015). volume 9355, pages 179-193, Banff, Canada, October 2015. Springer, Heidelberg, Germany.

Learning weighted automata.

In Proceedings of The 6th International Conference on Algebraic Informatics (CAI 2015). volume to appear, Stuttgart, Germany, September 2015. Springer, Heidelberg, Germany.

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

The Design Principles of a Weighted Finite-State Transducer Library.

Theoretical Computer Science, 231:17-32, January 2000.

Elementary Unary Operations: Reversal, Inversion, Projection.

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

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.

Speech Recognition by Composition of Weighted Finite Automata .

In E. Roche and Y. Schabes, editors,

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

Generic Epsilon-Removal and Input Epsilon-Normalization Algorithms for Weighted Transducers.

International Journal of Foundations of Computer Science, 13(1):129-143, 2002.

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

A disambiguation algorithm for weighted automata.

Theoretical Computer Science, 10909, to appear, 2016.

On the disambiguation of weighted automata.

In Proceedings of the 20th International Conference on Implementation and Application of Automata (CIAA 2015). Umeå, Sweden, August 2015.

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

On some Applications of Finite-State Automata Theory to Natural Language Processing.

Journal of Natural Language Engineering, 2:1-20, 1996.

An Optimal Pre-Determinization Algorithm for Weighted Transducers.

Theoretical Computer Science, 328(1-2):3-18, November 2004.

Finitely Subsequential Transducers.

International Journal of Foundations of Computer Science, 14(6):983-994, 2003.

Determinization of Weighted Automata and Weighted Finite-State Transducers

Finite-State Transducers in Language and Speech Processing.

Computational Linguistics, 23:2, 1997.

Minimization of Finite-State Transducers

Minimization Algorithms for Sequential Transducers.

Theoretical Computer Science, 234:177-201, March 2000.

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

Finite-State Transducers in Language and Speech Processing.

Computational Linguistics, 23:2, 1997.

Equivalence of Subsequential Weighted Automata

Finite-State Transducers in Language and Speech Processing.

Computational Linguistics, 23:2, 1997.

Equivalence of Subsequential Finite-State Transducers

Minimization Algorithms for Sequential Transducers.

Theoretical Computer Science, 234:177-201, March 2000.

Divergences/Distances between Weighted Automata

On the computation of the relative entropy of probabilistic automata.

International Journal of Foundations of Computer Science, 19(1):219-242, 2008.

L

International Journal of Foundations of Computer Science, 18(4):761-780, 2007.

Edit-Distance of Weighted Automata: General Definitions and Algorithms.

International Journal of Foundations of Computer Science, 14(6):957-982, 2003.

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

Edit-Distance of Weighted Automata: General Definitions and Algorithms.

International Journal of Foundations of Computer Science, 14(6):957-982, 2003.

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

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

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

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

Finite-State Transducers in Language and Speech Processing.

Computational Linguistics, 23:2, 1997.

Ambiguity of Weighted Automata

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.

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

Semiring Frameworks and Algorithms for Shortest-Distance Problems.

Journal of Automata, Languages and Combinatorics, 7(3):321-350, 2002.

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

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.

Compression

Automata and graph compression.

In IEEE International Symposium on Information Theory (ISIT 2015). Hong Kong, China, 2015.