Wintersemester 2005/2006
Mildly context-sensitive grammar formalisms
TAG and related frameworks
Hauptseminar
Laura Kallmeyer
Montag 11-13, Seminarraum 1.01
A large range of grammar formalisms proposed for natural language processing
were developed with the idea that the formalism itself should characterize the
class of (formal) languages natural languages belong to. In other words, one
tries to keep the class of languages of a formalism as small as possible while
making sure to be able to deal a formalism as small as possible while making
sure to be able to deal with natural languages. These formalisms are mostly
part of the so-called mildly context-sensitive grammar formalisms, and among
them the most frequently used is Tree Adjoining Grammar (TAG). TAG is a
tree-rewriting grammar, i.e., the elements of the grammar are so-called
elementary trees and from these trees larger trees are generated by the
operations adjunction and substitution. An important characteristic of TAG is
that the elementary trees allow to localize dependencies even between lexical
items that are far from each other in the surface structure (i.e.,
dependencies that are traditionally called `unbounded').
In this course, Tree Adjoining Grammars and other related formalisms will be
introduced and discussed with respect to a) their formal properties, and b)
linguistic applications. Concerning the latter, we will consider syntactic
analyses of different phenomena in TAG and variants of TAG and, if time
permits, we will also
discuss recent work on the TAG syntax-semantics interface.
Final exam: Thursday 9.2.2006, 11h-13h, room 1.13 SfS.
Script of the course (to be completed)
1 Introduction
Part I: Lexicalized Tree Adjoining Grammars (LTAG)
2 Extending CFG for natural languages
3 Tree Adjoining Grammars (TAG)
4 Formal properties of Tree Adjoining
Languages
5 Linguistic analyses with LTAG
6 The XTAG grammar
7 LTAG and minimalist grammar
Part II: Mildly context-sensitive grammars and extensions of TAG
8 Mildly context-sensitive grammars and linear context-free rewriting systems
9 Multicomponent TAG
10 Limitations of TAG: Scrambling in German
11 Other extensions/variants of TAG
Bibliography
Solutions of the exercises
Bibliography
(for an extended bibliography see the script of the course)
-
Frank, R.: 2002. Phrase Structure Composition and Syntactic Dependencies.
MIT Press. Cambridge, Mass.
This book is concerned with TAG as a linguistic theory. It formulates
principles of minimalist grammar in TAG.
- Joshi, A. K.: 1985. Tree
adjoining grammars: How much contextsensitivity is required ro provide
reasonable structural descriptions?. In D. Dowty, L. Karttunen
and A. Zwicky (eds), Narural Language Parsing. Cambridge
University Press. pp. 206--250.
This paper brings forward
the notion of mildly context-sensitivity. It contains interesting
facts about the classes of languages generated by TAG without
adjoining constraints and TAG with adjoining constraints. However, the
definition of adjoining constraints is not the one currently used
(even though the results hold for both.).
-
Joshi, A. K.: 1987. An introduction to Tree Adjoining Grammars. In
A. Manaster-Ramer (ed.), Mathematics of Language. John Benjamins.
Amsterdam. pp. 87--114.
-
Joshi, A. K. and Schabes, Y.: 1997. Tree-Adjoning Grammars. n
G. Rozenberg and A. Salomaa (eds), Handbook of Formal Languages.
Springer. Berlin. pp. 69--123.
Good Introduction to TAG treating the formalism, formal properties, aspects
of lexicalization, and parsing.
-
Rambow, O.: 1994. Formal and Computational Aspects of Natural Language
Syntax. PhD thesis. University of Pennsylvania.
Very good proposal of an extension of TAG in order to deal with
scrambling in so-called free word order languages.
-
Shieber,
S.~M. 1985. Evidence against the context-freeness of natural language.
Linguistics and Philosophy 8, 333--343.
Convincing proof that natural languages are not weakly
context-free. The argument considers cross-serial dependencies in
Swiss German.
-
Vijay-Shanker, K.: 1987. A Study of Tree Adjoining Grammars. PhD
thesis. University of Pennsylvania.
Thesis on TAG and its
mathematical properties, contains among others a pumping lemma for TAG
and an automaton for TAG. Introduces Feature-Structure-Based TAG
(FTAG).
-
Weir, D. J.: 1988. Characterizing mildly context-sensitive grammar
formalisms. PhD thesis. University of Pennsylvania.
Introduces linear context-free rewriting systems and relates them to MCTAG.
-
The XTAG Research Group: 2001. A Lexicalized Tree Adjoining Grammar for
English. Technical report. Institute for Research in Cognitive
Science.
Detailed description of the English TAG developed in Philadelphia. Available
from here.
Laura Kallmeyer. 5.1.2006