Introduction to weighted string and tree automata

Weighted string and tree automata have a lot of applications in
computational linguistics, ranging from speech synthesis and analysis,
morphology, tagging, machine translation, robust parsing to full parsing.
They also have a nice underlying theory which allows the weights to come
from arbitrary sets as long as certain mathematical conditions are met.
The two week course will introduce into the theory and applications of
weighted automata and will cover the following topics:

  • Semirings as a suitable weight structure for automata

  • Weighted finite-state string automata, their algebra and closure properties

  • Weighted tree acceptors/transducers

  • Parsing with weighted automata

The course will be practically accompanied by programming exercises
based on the tools fsm2 (for weighted string automata) and talib/tasl
(for weighted tree automata).


Dr. Thomas Hanneforth works at the Institute of Linguistics at Potsdam University.