Date(s) - 11/09/2012 - 12/09/2012
3:00 pm - 4:30 pm
Introduction to Tabular Parsing Algorithms Giorgio Satta, Department of Information Engineering University of Padua, Italy
A mini-course to be held in two parts:
Tues 11 Sep, IF 1.15 3:00-4:30
Wed 12 Sep, IF 3.02 1:00-2:30
Tabular parsing, also known as chart parsing, is considered the most prominent paradigm in natural language parsing. In these two lectures I will investigate some tabular parsing algorithms, including CKY and Earley, as well as more recent tabular methods for projective and non-projective dependency parsing.
The presentation follows a well-established framework, originally introduced by Bernard Lang (1974), which allows relating tabular methods to underlying push-down nondeterministic automata. This discloses deep similarities between superficially different methods, and greatly simplifies the investigation of mathematical properties of these methods.
Bernard Lang, Deterministic techniques for efficient non-deterministic parsers. Automata, Languages and Programming. Lecture Notes in Computer Science, 1974, Springer Berlin / Heidelberg, 255-269.