NLP Research at the NLP group at Córdoba

This talk will be divided in two parts. In the first part I will focus on a common technique that is used by almost all state of the art parser: the transformation of phrase structure trees into dependency trees. Typically, a set of rules is used to determine the head of each constituent and then, using this information, phrase structures can algorithmically be transform into dependencies. The set of rules is constructed manually. I will show experimental results showing that a hardly better set of rules can obtained by a optimization procedure and that actually the search space is quite
stable, meaning that it does not actually matter that much how the transformation is made. The second part of the talk will focus on Non-terminally Separated (NTS) grammars, a formalism that was introduced by Alexander Clark for learning Context Free Grammars. In the talk, I will show that learning an NTS grammar from a tree-bank is an NP problem: I will show that this problem is equivalent to decide for every ambiguous string that appears in the tree-bank if it should be used as a constituent in the NTS grammar. I will show searching for the optimal decisions is equivalent to the maximum weight stable set problem, a well known NP problem.