A Project Seminar

Martin Kay

An introduction to complexity theory and the core algorithms for (non-statistical) computational linguistics. String searchng, suffix trees and arrays, finite-state technology and morphological analysis, backtracking and chart parsers and generators for context-free and unification grammars.

Slides:

Complexity (PDF)

Finite-state Automata: Motivation(PDF)

Mathematics (PDF)

Rewriting Rules (PDF)

String Search (PDF)

Suffix Trees—Ukkonen's Algorithm(PDF)

BackTrack Parsing (PDF)

Chart Parsing (PDF)

Unification (PDF)

program (PDF)