REFERENCES TO FINITE-STATE METHODS IN NATURAL LANGUAGE PROCESSING

If you already know what regular expressions are or you only want to find out some details about our notation or about certain specific operators, you should skip the introduction and go directly to the relevant section. If you are a novice reader who is not completely familiar with the concept of a regular expression, start with the introduction.

RECENT SURVEYS :

Karttunen et al. 1996.
Lauri Karttunen, Jean-Pierre Chanod, Gregory Grefenstette, Anne Schiller. 1996. Regular Expressions for Language Engineering CUP Journals: Natural Language Engineering 2 (4) 305-328.Cambridge University Press

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

CONFERENCES :

WIA'96
International Workshop on Implementing Automata. August 29 -31 , 1996. University of Western Ontario, London, Ontario, Canada.

WIA'97
Second International Workshop on Implementing Automata. September 18-20, 1997. University of Western Ontario, London, Ontario, Canada.

WIA'98
Third International Workshop on Implementing Automata. September 17-19, 1998. Université of Rouen, Rouen, France.

WIA'99
Forth International Workshop on Implementing Automata. July 17-19, 1999. Potsdam University, Potsdam, Germany.

CIAA'2000
Fifth International Conference on Implementation and Application of Automata (Formerly WIA). July 24-25, 2000. University of Western Ontario, London, Ontario, Canada.

CIAA'2001
Sixth International Conference on Implementation and Application of Automata. July 23-25, 2001. University of Pretoria, Pretoria, South Africa.

CIAA'2002
Seventh International Conference on Implementation and Application of Automata. July 3-6, 2002. University of Tours, France.

CIAA'2003
Eighth International Conference on Implementation and Application of Automata. July 16-18, 2003. University of California, Santa Barbara, CA, USA.

CIAA'2004
Ninth International Conference on Implementation and Application of Automata. July 22-24, 2004. Queen's University, Kingston, Ontario, Canada.

CIAA'2005
Tenth International Conference on Implementation and Application of Automata. June 27-29, 2005. University of Nice, Sophia Antipolis, France.

FSMNLP'2001
International Workshop on Finite-State Methods in Natural Language Processing. August 20-24, 2001. Helsinki, Finland.

FSMNLP'2005
International Workshop on Finite-State Methods and Natural Language Processing. September 1-2, 2005. University of Helsinki, Finland.

GENERAL INTRODUCTIONS :

Berstel 1979
 Jean Berstel. 1979. Transductions and Context-Free Languages. B.G. Teubner in Stuttgart.

Eilenberg 1974
 Samuel Eilenberg. 1974. Automata, Languages, and Machines. Academic Press.

Perrin 1990
 Dominique Perrin. 1990. Finite Automata. In J. Van Leuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pages 1-57. Elsevier, Amsterdam.

Roche and Schabes 1997
 Emmanuel Roche and Yves Schabes, eds. 1997. Finite-State Language Processing. 1997. MIT Press, Cambridge, Massachusetts.

Watson 1995
 Bruce W. Watson. 1995. Taxonomies and Toolkits of Regular Language Algorithms. Eindhoven University of Technology. Department of Mathematics and Computer Science. Eindhoven. The Neatherlands.

CLASSICS :

Kaplan and Kay 1994
 Ronald M. Kaplan and Martin Kay. 1994. Regular Models of Phonological Rule Systems. Computational Linguistics, 20:3, pages 331-378.

Koskenniemi 1983
Kimmo Koskenniemi. 1983. Two-level Morphology.  A General Computational Model for Word-FormRecognition and Production. Department of General Linguistics. University of Helsinki.

Schuetzenberger 1977
 Marcel Paul Schützenberger. 1977. Sur une variante des fonctions sequentielles. Theoretical Computer Science, 4, pages 47-57.

Johnson 1972
 Johnson, C. Douglas. Formal Aspects of Phonological Description. Mouton. The Hague. 1972

TECHNICAL MANUALS :

Karttunen and Beesley 1992
 Lauri Karttunen and Kenneth R. Beesley 1992. Two-level Rule Compiler. Technical Report. ISTL-92-2. Xerox PARC. June 1992. Palo Alto, California. (HTML).

Karttunen 1993
 Lauri Karttunen 1993. Finite-State Lexicon Compiler. Technical Report. ISTL-NLTT-1993-04-02. Xerox PARC. April 1993. Palo Alto, California. (HTML).

Karttunen et al. 1997
Lauri Karttunen, Tamás Gaál, and André Kempe 1997. Xerox Finite-State Tool. Technical Report. Xerox Research Centre Europe, Grenoble. June 1997. Meylan, France. (HTML).

OTHER REFERENCES :

Beesley 1998
 Kenneth R. Beesley. 1998. Arabic Morphological Analysis on the Internet. To appear in the Proceedings of the International Conference and Exhibition on Multi-lingual Computing (Arabic and English), ICEMCO-98 (Postscript, 114K).

Karttunen 1991
 Lauri Karttunen. 1991. Finite-State Constraints. In The Proceedings of the International Conference on Current Issues in Computational Linguistics., June 10-14, 1991. Universiti Sains Malaysia, Penang, Malaysia (HTML, Postscript, 668K).

A later version of the paper appeared under the same title in The Last Phonological Rule, John Goldsmith, ed. University of Chicago Press. Chicago, Ill. 1993.

Karttunen et al. 1992
 Lauri Karttunen, Ronald M. Kaplan, and Annie Zaenen. 1992. Twol-level Morphology with Composition. In The Proceedings of the International Conference on Computational Linguistics. Coling 92, July 25-28, Nantes France (HTML, Postscript, 467K).

Karttunen 1994
 Lauri Karttunen. 1994. Constructing Lexical Transducers. In The Proceedings of the Fifteenth International Conference on Computational Linguistics. Coling 94, I, pages 406-411, Kyoto, Japan (HTML, Postscript, 312K).

Karttunen 1995
 Lauri Karttunen. 1995. The Replace Operator. In The Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics. ACL-95, pages 16-23, Boston, Massachusetts. (HTML, Postscript, 344K)

Karttunen 1996
 Lauri Karttunen. 1996. Directed Replacement. In The Proceedings of the 34rd Annual Meeting of the Association for Computational Linguistics. ACL-96, Santa Cruz, California. (HTML, Postscript, 169K)

Karttunen 1998
 Lauri Karttunen. 1998. The Proper Treatment of Optimality in Computational Phonology. To appear in the Proceedings of the International Workshop on Finite-State Methods in Natural Language Processing, FSMNLP'98, pages 1-12. June 29-July 1. Bilkent University, Ankara, Turkey. (HTML, Postscript, 278K).

Kempe and Karttunen 1996
 André Kempe and Lauri Karttunen. 1996. Parallel Replacement in the Finite-State Calculus. In The Proceedings of the Sixteenth International Conference on Computational Linguistics. Coling 96. Copenhagen, Denmark. (Postscript, 176K)

Mohri 1996
 Mehryar Mohri. 1996. On Some Applications of Finite-State Automata Theory to Natural Language Processing. Natural Language Engineering 1:1.

Roche and Schabes 1995
 Emmanuel Roche and Yves Schabes. 1995. Deterministic Part-of-Speech Tagging. Computational Linguistics, 21:2, pages 227-53.

MISCELLANEOUS :

Finite-state publication list
 of the Xerox Research Centre, Grenoble, France (HTML).

Jan Daciuk's finite-state page
 on algorithms, tools, research groups, conferences, and related sites (HTML). Alfa Informatica, Rijksuniversiteit Groningen, The Netherlands.

We welcome your comments and suggestions.

Back to Finite State Technology homepage