Weighted Finite-State Automata (WFSA)

Overview

Inhalt dieses Kurses ist die Theorie und Anwendung von gewichteten Automaten. Gewichtete Automaten sind eine Generalisierung von normalen Automaten, die auf der algebraischen Theorie der Halbringe beruht. Wir führen zunächst die wichtigsten Konzepte aus der Theorie der Automaten und Halbringe ein, und stellen dann die Bibliothek OpenFST vor, in der wir mittels Python gewichtete Automaten erstellen und manipulieren. Wir werden dann verschiedene Anwendungen entwickeln, etwa eine Rechtschreibkontrolle, einen Tokenizer sowie evtl. ein System zur automatischen Alinierung zweisprachiger Korpora. Gleichzeitig sollen aber auch die theoretischen Aspekte besprochen werden, die diese Anwendungen möglich machen.

Course content

Course script [Download]

Here are some of the topics covered by this course:

  1. Sprachen, Automaten, Relationen
  2. Halbringe
  3. Gewichtete Sprachen und Relationen
  4. Gewichtete Automaten
  5. Operationen auf gewichteten Sprachen, Relationen, Relationen
  6. Tokenisierung mit gewichteten endlichen Automate
  7. Implementierung eines Tokenizers
  8. Implementierung eines Spell-checkers
  9. Komposita-Zerlegung in OpenFST
  10. Weitere Themen: maschinelle Übersetzung, …
  11. Gewichtete Baumautomaten

Slides:

  1. Indroduction to Openfst: PDF

Software

  • OpenFst Library (Finite-State Transducer Library).
  • PyFst (A Python interface to OpenFst) .
  • graphviz (Graphviz is open source graph visualization software).
  • Ipython Notebook (The IPython Notebook is a web-based interactive computational environment where you can combine code execution, text, mathematics, plots and rich media into a single document).
  • VirtualBox (VirtualBox is a general-purpose full virtualizer for x86 hardware, targeted at server, desktop and embedded use.)
  • You can get the course virtual machine from here: [ download ]. (You need a password).

Location and Time

Room: 23.21.01.42

Thursday: 12:30 – 14:00.

Homework assignments: