[xtag-meeting]: Talks by Alexander Koller

Alexander Koller from the University of Saarland is visiting Penn 25-30 April. 
During his visit he will be giving two talks.

The first talk will be in the form of an  informal presentation/discussion, 
invited by the DLTAG group, to be held at the group's regular meeting time, 
i.e., on Friday at 3:00pm at the back conference room (413) at IRCS.  

Title: "Computational Linguistics and Theorem Proving in a Computer Game"
Speaker: Alexander Koller
Place: Back conference room (413) at IRCS
Date: Friday, April 26th
Time: 3-4:30


Title: TAG Generation as Dependency Parsing
Speaker: Alexander Koller
Place: Large conference room at IRCS (to be confirmed)
Date: Monday, April 29th
Time: 12-1:30

TAG Generation as Dependency Parsing
(joint work with Kristina Striegnitz)

This is a talk about some computational issues related to realization with 
TAG. I will first prove that realization from a flat input semantics (i.e. a 
multiset of atomic formulas) is an NP-complete problem. Then I will show how 
this problem can be reduced to a parsing problem with dependency grammar, 
which essentially computes a TAG derivation tree. Using a modern dependency 
parser, we can in practice largely avoid the combinatorial explosion 
associated with NP-complete problems. Initial runtime experiments with 
generating from the XTAG grammar display encouraging results.