---
title: "Finite-State Transducers in Language and Speech Processing — Mohri 1997"
description: "Mohri lays out a theoretical and algorithmic framework for sequential transducers: finite-state machines whose… 31 references, cited by 122 papers here."
authors: ["Mehryar Mohri"]
year: 1997
venue: "Computational Linguistics"
source: "https://aclanthology.org/J97-2003/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/mohri-1997-finite-state-transducers-language-speech/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/mohri-1997-finite-state-transducers-language-speech/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1997](https://md.research.elamur.ai/free/en/papers/1997/) / Finite-State Transducers in Language and Speech Processing

# Finite-State Transducers in Language and Speech Processing

**Authors:** Mehryar Mohri · **Year:** 1997 · **Venue:** Computational Linguistics · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/J97-2003/) · [PDF](https://aclanthology.org/J97-2003.pdf) · [OpenAlex](https://openalex.org/W2125529971)

**Citations:** 899 citations (OpenAlex, 2026-10-14) · [122](https://md.research.elamur.ai/free/en/papers/mohri-1997-finite-state-transducers-language-speech/cited-by/) in our library, of the 140,884 papers whose bibliographies we read

## 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](https://md.research.elamur.ai/free/en/shelves/nlp/)

Topics: [🎙️ Speech & spoken language](https://md.research.elamur.ai/free/en/topics/speech/)

## Institutions

- [AT&T](https://md.research.elamur.ai/free/en/companies/at-t/) — Company, Bedminster, United States · 19 works · 12,873 citations

## Cite

Cite as: Mehryar Mohri. 1997. Finite-State Transducers in Language and Speech Processing. Computational Linguistics.

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

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

- [← previous Three Generative, Lexicalised Models for Statistical Parsing](https://md.research.elamur.ai/free/en/papers/collins-1997-three-generative-lexicalised-models-statistical/)
- [next → Using Lexical Chains for Text Summarization](https://md.research.elamur.ai/free/en/papers/barzilay-1997-lexical-chains-text-summarization/)
- [↑ back to papers of 1997](https://md.research.elamur.ai/free/en/papers/1997/)

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