Endliche Automaten für die Sprachverarbeitung
PD Dr. Karin Haenelt

Sprachtechnologie und Computerlinguistik
Fraunhofer Gesellschaft e.V. und Universität Heidelberg
2009
Literatur
 


Stand 11.04.2007

Zur Einführung empfohlen

Beesley Kenneth R. und Lauri Karttunen (neue Auflage in Vorbereitung - mit Software)
Finite-State Morphology. Distributed for the Center for the Study of Language and Information. 696 p. (est.). 2003 Series: (CSLI-SCL) Studies in Computational Linguistics.
Neue Software: http://www.stanford.edu/~laurik/fsmbook/home.html http://www.fsmbook.com
Hopcroft, John E. Rajeev Motwani und Jeffrey D. Ullman (2001)
Einführung in die Automatentheorie, Formale Sprachen und Komplexität. Pearson Studium
engl. Original: Introduction to Automata Theory, Languages and Computation. Addison-Wesley. www-db.stanford.edu/~ullman/ialc.html
[modernisierte Ausgabe von Hopcroft/Ullman 1988 (s.u.), aber ohne Beweise]
Jurafsky, Daniel; Martin James H. (2007, ¹2000)
Regular Expressions and Automata. In: Jurafsky, Daniel; Martin James H. (2007, ¹2000) mit Beiträgen von Andrew Kehler, Keith Vander Linden, Nigel Ward Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition Upper Saddle River, N.J.: Prentice Hall.
Mohri, Mehryar (1997)
Finite State Transducers in Language and Speech Processing. In: Computational Linguistics, 23, 2, 1997, S. 269-311. citeseer.ist.psu.edu/mohri97finitestate.html

Grundlagen: Mathematik - allgemein

Peter H. Starke (2000)
Logische Grundlagen der Informatik. Skript zur Vorlesung Theoretische Informatik I. http://www2.informatik.hu-berlin.de/lehrstuehle/automaten/logik/skript.pdf

Grundlagen: Automatentheorie

Jean Berstel und Dominique Perrin (2004)
Algorithms on Words. [ps] In: M.Lothaire (ed). (2004). Applied Combinatorics on Words.
Klabunde, Ralf (2001)
Automatentheorie und formale Sprachen. In: Kai-Uwe Carstensen, Christian Ebert, Cornelia Endriss, Susanne Jekat, Ralf Klabunde und Hagen Langer (eds.): Computerlinguistik und Sprachtechnologie. Heidelberg/Berlin: Spektrum Akademischer Verlag, 2001. S. 59-86.
Hopcroft, John E. und Jeffrey D. Ullman (1988)
Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Bonn u. a.: Addison-Wesley, 1988 (engl. Original Introduction to automata theory, languages and computation). [Anm.: Diese Fassung enthält die Beweise, die zugleich die Algorithmen zur Transformation der Automaten sind]
Hopcroft, John E. Rajeev Motwani und Jeffrey D. Ullman (2001)
Introduction to Automata Theory, Languages and Computation. Addison-Wesley. www-db.stanford.edu/~ullman/ialc.html [modernisierte Ausgabe mit vielen Beispielen]
Lawson, Mark V. (2004)
Finite Automata. Boca Raton, London, New York, Washington D.C.: Chapman&Hall/CRC. [eine Einführung in die mathematische Theorie endlicher Automaten]
Lawson, Mark V. (2004)
Finite Automata. In: D. Hristu-Varsakelis and W. S. Levine (eds.): Handbook of networked and embedded control systems
Starke, Peter H.(1969)
Abstrakte Automaten. VEB Deutscher Verlag der Wissenschaften: Berlin (ältere, aber sehr gute mathematische Darstellung)

Handbücher zur Sprachverarbeitung

Allen, James (1995)
Natural Language Understanding. 2nd edition. Addison-Wesley Publishing Co.
Jurafsky, Daniel; Martin James H. (2007, ¹2000) mit Beiträgen von Andrew Kehler, Keith Vander Linden, Nigel Ward
Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition Upper Saddle River, N.J.: Prentice Hall.
Manning, Christopher D.; Schütze, Hinrich (1999)
Foundations of Statistical Natural Language Processing. Cambridge, Mass., London: The MIT Press. http://www-nlp.stanford.edu/fsnlp/promo

Anwendungen: Übersichten und Sammelbände

Karttunen, Lauri (2003)
Finite-State Technology. In: Ruslan Mitkov (ed.) The Oxford Handbook of Computational Linguistics. Oxford: Oxford University Press, 2003. S. 339-357.
Kornai, András (Ed.) (1999)
Extended Finite State Models of Language. (Studies in Natural Language Processing). Cambridge: Cambridge University Press.
Roche, Emmanuel und Yves Schabes (Eds.) (1997)
Finite-State Language Processing. Cambridge (Mass.) und London: MIT Press.

Anwendungen: Morphologie

Beesley Kenneth R. und Lauri Karttunen (2003)
Finite-State Morphology. Distributed for the Center for the Study of Language and Information. 696 p. (est.). 2003 Series: (CSLI-SCL) Studies in Computational Linguistics
Koskenniemi, Kimmo (1983)
Two-level morphology: a general computational model for word-form recognition and production. Publication 11, University of Helsinki. Helsinki: Department of Genral Linguistics.

Anwendungen: Part-of-Speech-Tagging

Cutting, Doug; Kupiec, Julian; Pedersen, Jan; Sibun, Penelope (1992)
An practical Part-of-Speech Tagger.In: Proceedings of the Third Conference on Applied Natural Language Processing'92 ftp://parcftp.xerox.com/pub/tagger/anlp92.ps

Anwendungen: Parsing

Abney, Steven (1996)
Partial Parsing via Finite-State Cascades. In: Workshop on Robust parsing, 8th European Summer School in Logic, Language and Information (ESSLLI). Prag, 1996, S. 8-15. http://citeseer.ist.psu.edu/abney96partial.html und Web-Seite: Steven Abney: Papers
Abney, Steven (1991)
Parsing By Chunks. In: Robert Berwick and Steven Abney and Carol Tenny, Principle-Based Parsing, Kluwer Academic Publishers, 1991.
http://whorf.sfs.nphil.uni-tuebingen.de/~abney/Abney_90e.ps.gz
Ait-Mokhtar, Salah; Chanod, Jean-Pierre (1997)
Incremental Finite State Parsing. In: ANLP'97 citeseer.ist.psu.edu/ait-mokhtar97incremental.html
Dreyer, Markus
Syntaktisches Parsing zur prosodischen Merkmalsgenerierung. Magisterarbeit. Universität Heidelberg. Februar 2002. http://www.rzuser.uni-heidelberg.de/~mdreyer/thesis/
Ejerhed, Eva (1999) (1996)
Finite State Segmentation of Discourse into Clauses. In: Proceedings of the Ecai '96 Workshop on Extended finite state models of language http://www.kornai.com/ECAI/ejerhed.html
auch in: Kornai, András (Ed.) (1999) Extended Finite State Models of Language. (Studies in Natural Language Processing). Cambridge: Cambridge University Press.
Ejerhed, Eva (1998)
Finding Clauses in Unrestricted Text by Finitary and Stochastic Methods . In: Proceedings of Second Conference on Applied Natural Language Processing, S. 219-227.
Grefenstette, Gregory (1999)
Light Parsing as Finite State Filtering. In: Kornai 1999, S. 86-94. frühere Version: In: Workshop on Extended finite state models of language, Budapest, Hungary, Aug 11--12, 1996. ECAI'96." http://citeseer.ist.psu.edu/grefenstette96light.html
Pereira Fernando C.N. und Rebecca N. Wright (1997)
Finite-State Approximation of Phrase-Structure Grammars. In: Roche, Emmanuel und Yves Schabes (Eds.) (1997)
Finite-State Language Processing.
Roche, Emmanuel (1997)
Parsing with Finite-State Transducers. In: Roche, Emmanuel und Yves Schabes (Eds.) (1997)
Finite-State Language Processing.

Anwendungen: Gesprochene Sprache / Speech

Mohri, Mehryar (1997)
Finite State Transducers in Language and Speech Processing. In: Computational Linguistics, 23, 2, 1997, S. 269-311. citeseer.ist.psu.edu/mohri97finitestate.html

Algorithmen

Zusammenstellungen
Mohri, Mehryar (2009)
Weighted automata algorithms. In Werner Kuich, Heiko Vogler, and Manfred Dorste, editors, Handbook of weighted automata. Springer (to appear), 2009.
Mohri, Mehryar (1997)
Finite State Transducers in Language and Speech Processing. In: Computational Linguistics, 23, 2, 1997, S. 269-311. citeseer.ist.psu.edu/mohri97finitestate.html
Mohri, Mehryar (2004)
Statistical Natural Language Processing. [ps] In: M.Lothaire (ed). (2004). Applied Combinatorics on Words.
Mohri, Mehryar (1996)
On some Applications of Finite-state Automata Theory to Natural Language Processing. In: Journal of Natural Language Engineering, Bd. 2, S. 1- 20.
Einzelne Algorithmen
Frakes, William; Baeza-Yates, Ricardo (Eds.) (1992)
Information Retrieval. Data Structures and Algorithms. Englewood Cliffs, N.J.: Prentice Hall. (Stoppwortlisten mit minimalen Automaten) Site.es: Table of Contents and Source Code, Site.cl: Table of Contents and Source Code
Mäurer, Ina (2002)
Zur Minimalisierung und Determinisierung von sequentiellen Transducern. Diplomarbeit. TU Dresden.
Komplexität
Barton Jr., G. Edward; Berwick, Robert, C. und Eric Sven Ristad (1987)
Computational Complexity and Natural Language. MIT Press.

Implementierung

Ladd, Scott Robert (1997)
Java Algorithms. New York etc.: McGraw-Hill. (Chapter 7: Finite State Machines and Evolving Software) + CD-ROM.

Systeme

XEROX Finite State Compiler
www.xrce.xerox.com/competencies/content-analysis/fsCompiler/fsnetwork.html

Programmbibliotheken

Arnaud Adant (2000)
Beschreibung: Study and implementation of a weighted finite-state library-application to speech synthesis.
Bibliothek: WFST-Library
Cyril Allauzen, Mehryar Mohri und Brian Roark (2005).
The Design Principles and Algorithms of a Weighted Grammar Library. International Journal of Foundations of Computer Science, 16(3):403-421, 2005.
Mehryar Mohri, Fernando C.N. Pereira, Michael Riley (2003)
AT&T FSM Library - Finite-State Machine Library
Lee Hetherington (2005)
The MIT FST Toolkit
Stepahn Kanthak, Hermann Ney (2004)
An Efficient and Flexible C++ Toolkit for Finite State Automata Using On-Demand Computation". In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL 2004), Barcelona, Spain, pp. 510-517, July, 2004.
Bibliothek: The RWTH FSA Toolkit
Gertjan van Noord
FSA6.2xx: Finite State Automata Utilities