Elamur Research⌕
☰
home / papers / 1997 / Finite-State Transducers in Language and Speech Processing

Finite-State Transducers in Language and Speech Processing

Summary

Mohri lays out a theoretical and algorithmic framework for sequential transducers: finite-state machines whose input side is deterministic and which emit strings or weights. The motivation is efficiency on the very large lexicons, grammars and lattices common in language and speech work. With a sequential machine, processing time depends only on input length, not on machine size.

The paper first covers string-to-string transducers. It restates classical characterization results, adds new ones, and introduces p-subsequential transducers to model bounded linguistic ambiguity. It then turns to string-to-weight transducers, which can encode language models and phone or word lattices. For these it provides:

  • a determinization algorithm,
  • a characterization of which unambiguous machines can be determinized, with a test for this property,
  • a minimization method as fast as classical automaton minimization.

Determinization runs on the fly, expanding only the parts that are needed. Experiments in speech recognition show large reductions in lattice size. The work became a cornerstone of weighted finite-state methods in ASR and NLP toolkits.

Key points

  • A sequential string-to-string transducer is formalized as a 7-tuple: states, initial state, final states, input and output alphabets, a transition function, and an output function. Applying it takes time linear in the input length.
  • Subsequential transducers (Schützenberger 1977) add one final output string per final state. p-subsequential transducers (Mohri 1994a) allow up to p final outputs, which covers finite ambiguity in morphology, grammars and pronunciation dictionaries.
  • Theorem 1 states closure under composition: composing a p-subsequential function with a q-subsequential one yields a pq-subsequential function. The purely sequential case was originally proved by Choffrut (1978).
  • For weighted (string-to-weight) transducers, the paper gives determinization, a determinizability test, and minimization. Under certain conditions, minimization can be done through determinization, with a correctness proof in the appendix.
  • The methods are applied in speech recognition to language models and to phone and word lattices. On-the-fly determinization saves both time and memory.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

122 papers of our library cite it (of the 140884 whose bibliographies we read); 2 of them have a page here, 120 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@article{mohri1997finite,
  title = {{Finite-State Transducers in Language and Speech Processing}},
  author = {Mohri, Mehryar},
  journal = {Computational Linguistics},
  year = {1997},
  url = {https://aclanthology.org/J97-2003/}
}

References

31 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Choffrut, Christian. 1978. Contributions t~ l'dtude de quelques familles remarquables de fonctions rationnelles. Ph.D. thesis, (th~se de doctorat d'Etat), Universit~ Paris 7, LITP, Paris. find
  2. Cormen, T., C. Leiserson, and R. Rivest. 1992. Introduction to Algorithms. The MIT Press, Cambridge, MA. find
  3. Courcelle, Brtmo, Damian Niwinski, and Andreas Podelski. 1991. A geometrical view of the determinization and minimization of finite-state automata. Mathematical Systems Theory, 24:117-146. find
  4. Crochemore, Maxirne. 1986. Transducers and repetitions. Theoretical Computer Science, 45. find
  5. Eilenberg, Samuel. 1974-1976. Automata, Languages and Machines, volume A-B. Academic Press. find
  6. Elgot, C. C. and J. E. Mezei. 1965. On relations defined by generalized finite automata. IBM Journal of Research and Development, 9. find
  7. Ginsburg, S. and G. F. Rose. 1966. A characterization of machine mappings. Canadian Journal of Mathematics, 18. find
  8. Gross, Maurice. 1989. The use of finite automata in the lexical representation of natural language. Lecture Notes in Computer Science, 377. find
  9. Hopcroft, John E. and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, Reading, MA. find
  10. Kaplan, Ronald M. and Martin Kay. 1994. Regular models of phonological rule systems. Computational Linguistics, 20(3). find
  11. Karlsson, Fred, Atro Voutilainen, Juha Heikkila, and Atro Anttila. 1995. Constraint Grammar, A Language-Independent System for Parsing Unrestricted Text. Mouton de Gruyter. find
  12. Karttunen, Lauri, Ronald M. Kaplan, and Annie Zaenen. 1992. Two-level morphology with composition. In Proceedings of the Fifteenth International Conference on Computational Linguistics (COLING-92), Nantes, France. COLING. find
  13. Krob, Daniel. 1994. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Journal of Algebra and Computation, 4. find
  14. Kuich, Werner and Arto Salomaa. 1986. Semirings, Automata, Languages. EATCS Monographs on Theoretical Computer Science, Number 5. Springer-Verlag, Berlin. find
  15. Mohri, Mehryar. 1994a. Compact representations by finite-state transducers. find
  16. In Proceedings of the 32 nd Annual Meeting, Las Cruces, New Mexico. Association for Computational Linguistics. find
  17. Mohri, Mehryar. 1994b. Minimization of sequential transducers. Lecture Notes in Computer Science, 807. find
  18. Mohri, Mehryar. 1994c. On some applications of finite-state automata theory to natural language processing: Representation of morphological dictionaries, compaction, and indexation. Technical Report IGM 94-22, Institut Gaspard Monge, Noisy-le-Grand. find
  19. Mohri, Mehryar. 1994d. Syntactic analysis by local grammars automata: An efficient algorithm. In Proceedings of the International Conference on Computational Lexicography (COMPLEX 94). Linguistic Institute, Hungarian Academy of Science, Budapest, Hungary. find
  20. Mohri, Mehryar. 1995. Matching patterns of an automaton. Lecture Notes in Computer Science, 937. find
  21. Mohri, Mehryar, 1996a. On The Use of Sequential Transducers in Natural Language Processing. In Yves Shabes, editor, Finite State Devices in Natural Language Processing. MIT Press, Cambridge, MA. To appear. find
  22. Mohri, Mehryar. 1996b. On some applications of finite-state automata theory to natural language processing. Journal of Natural Language Engineering, 2:1-20. find
  23. Mohri, Mehryar, Fernando C. N. Pereira, and Michael Riley. 1996. Weighted automata in text and speech processing. In ECAI-96 Workshop, Budapest, Hungary. ECAI. find
  24. Mohri, Mehryar and Richard Sproat. 1996. An efficient compiler for weighted rewrite rules. In Proceedings of the 34th Annual Meeting, Santa Cruz, California. Association for Computational Linguistics. find
  25. Nerode, Anti. 1958. Linear automaton transformations. In Proceedings of AMS, volume 9. find
  26. Pereira, Fernando C. N. and Michael Riley, 1996. Weighted Rational Transductions and their Application to Human Language Processing. In Yves Shabes, editor, Finite State Devices in Natural Language Processing. MIT Press, Cambridge, MA. To appear. find
  27. Perrin, Dominique. 1990. Finite automata. In J. Van Leuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics. Elsevier, Amsterdam, pages 1-57. find
  28. Reutenauer, Christophe and Marcel Paul Schiitzenberger. 1995. Vari~t~s et fonctions ratlonnelles. Theoretical Computer Science, 145. find
  29. Revuz, Dominique. 1992. Minimisation of acyclic deterministic automata in linear time. Theoretical Computer Science, 92:181-189. find
  30. Roche, Emmanuel. 1993. Analyse syntaxique transformationnelle du fran~ais par transducteurs et lexique-grammaire. Ph.D. thesis, Universit6 Paris 7, Paris. find
  31. Salomaa, Arto and Matti Soittola. 1978. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/mohri-1997-finite-state-transducers-language-speech/