Abstract
This paper is a review of some of the major applications of finite-state transducers in Natural Language Processing ranging from morphological analysis to finite-state parsing. The analysis and generation of inflected word forms can be performed efficiently by means of lexical transducers. Such transducers can be compiled using an extended regular expression calculus with restriction and replacement operators. These operators facilitate the description of complex linguistic phenomena involving morphological alternations and syntactic patterns. Because regular languages and relations can be encoded as finite-automata, new languages and relations can be derived from them directly by the finite-state calculus. This is a fundamental advantage over higher-level linguistic formalisms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kenneth R. Beesley and Lauri Karttunen. Finite-State Morphology: Xerox Tools and Techniques. Cambridge University Press, 2000. To appear.
Kenneth R. Beesley and Lauri Karttunen. Finite-state non-concatenative morphotactics. In Lauri Karttunen Jason Eisner and Alain Thériault, editors, SIGPHON-2000, pages 1–12, August 6 2000. Proceedings of the Fifth Workshop of the ACL Special Interest Group in Computational Phonology.
N. Chomsky. Syntactic Structures. Mouton, Gravenhage, Netherlands, 1957.
Noam Chomsky and Morris Halle. The Sound Pattern of English. Harper and Row, New York, 1968.
Edmund Grimley-Evans, George Anton Kiraz, and Stephen G. Pulman. Compiling a partition-based two-level formalism. In Proceedings of the 16th International Conference on Computational Linguistics, Copenhagen, 1996.
C. Douglas Johnson. Formal Aspects of Phonological Description. Mouton, The Hague, 1972.
Ronald M. Kaplan and Martin Kay. Phonological rules and finite-state transducers. In Linguistic Society of America Meeting Handbook, Fifty-Sixth Annual Meeting, New York, December 27-30 1981. Abstract.
Ronald M. Kaplan and Martin Kay. Regular models of phonological rule systems. Computational Linguistics, 20(3):331–378, 1994.
Lauri Karttunen. Finite-state lexicon compiler. Technical Report ISTL-NLTT-1993-04-02, Xerox Palo Alto Research Center, Palo Alto, CA, April 1993.
Lauri Karttunen. The replace operator. In ACL’95, Cambridge, MA, 1995. cmp-lg/9504032.
Lauri Karttunen. Directed replacement. In ACL’96, Santa Cruz, CA, 1996. cmp-lg/9606029.
Lauri Karttunen and Kenneth R. Beesley. Two-level rule compiler. Technical Report ISTL-92-2, Xerox Palo Alto Research Center, Palo Alto, CA, October 1992.
Lauri Karttunen, Jean-Pierre Chanod, Gregory Grefenstette, and Anne Schiller. Regular expressions for language engineering. Journal of Natural Language Engineering, 2(4): 305–328, 1996.
Lauri Karttunen, Kimmo Koskenniemi, and Ronald M. Kaplan. A compiler for two-level phonological rules. Technical report, Xerox Palo Alto Research Center and Center for the Study of Language and Information, Stanford University, June 25 1987.
André Kempe and Lauri Karttunen. Parallel replacement in finite-state calculus. In COLING’96, Copenhagen, August 5-9 1996. cmp-lg/9607007.
Kimmo Koskenniemi. Two-level morphology: A general computational model for word-form recognition and production. Publication 11, University of Helsinki, Department of General Linguistics, Helsinki, 1983.
Mehryar Mohri and Richard Sproat. An efficient compiler for weighted rewrite rules. In ACL’96, Santa Cruz, CA, 1996.
Gertjan van Noord and Dale Gerdemann. An extendible regular expression compiler for finite-state approaches in natural language processing. In O. Boldt, H. Juergensen, and L. Robbins, editors, Workshop on Implementing Automata; WIA99 Pre-Proceedings, Potsdam Germany, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Karttunen, L. (2001). Applications of Finite-State Transducers in Natural Language Processing. In: Yu, S., Păun, A. (eds) Implementation and Application of Automata. CIAA 2000. Lecture Notes in Computer Science, vol 2088. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44674-5_2
Download citation
DOI: https://doi.org/10.1007/3-540-44674-5_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42491-8
Online ISBN: 978-3-540-44674-3
eBook Packages: Springer Book Archive