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)