A Polynomial-Time Parsing Algorithm for TT-MCTAG

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 994–1002, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP A Polynomial-Time Parsing Algorithm for TT-MCTAG Laura Kallmeyer Collaborative Research Center 441 Universit¨at T¨ubingen T¨ubingen, Germany lk@sfs.uni-tuebingen.de Giorgio Satta Department of Information Engineering University of Padua Padova, Italy satta@dei.unipd.it Abstract This paper investigates the class of Tree- Tuple MCTAG with Shared Nodes, TT- MCTAG for short, an extension of Tree Adjoining Grammars that has been pro- posed for natural language processing, in particular for dealing with discontinuities and word order variation in languages such as German. It has been shown that the uni- versal recognition problem for this formal- ism is NP-hard, but so far it was not known whether the class of languages generated by TT-MCTAG is included in PTIME. We provide a positive answer to this ques- tion, using a new characterization of TT- MCTAG. 1 Introduction For a large range of linguistic phenomena, exten- sions of Tree Adjoining Grammars (Joshi et al., 1975), or TAG for short, have been proposed based on the idea of separating the contribution of a lex- ical item into several components. Instead of sin- gle trees, these grammars contain (multi-)sets of trees. Examples are tree-local and set-local mul- ticomponent TAG (Joshi, 1985; Weir, 1988), MC- TAG for short, non-local MCTAG with dominance links (Becker et al., 1991), Vector-TAG with dom- inance links (Rambow, 1994) and, more recently, Tree-Tuple MCTAG with Shared Nodes (Lichte, 2007)), or TT-MCTAG for short. For some of the above formalisms the word recognition problem is NP-hard. This has been shown for non-local MCTAG (Rambow and Satta, 1992), even in the lexicalized case (Champollion, 2007). Some others generate only polynomial lan- guages but their generative capacity is too limited to deal with all natural language phenomena. This has been argued for tree-local and even set-local MCTAG on the basis of scrambling data from lan- guages such as German (Becker et al., 1992; Ram- bow, 1994). In this paper, we focus on TT-MCTAG (Lichte, 2007). So far, it has been shown that the univer- sal recognition problem for TT-MCTAG is NP- hard (Søgaard et al., 2007). A restriction on TT- MCTAG has been proposed in (Kallmeyer and Parmentier, 2008): with such a restriction, the uni- versal recognition problem is still NP-hard, but the class of generated languages is included in PTIME, i.e., all these languages can be recognized in deterministic polynomial time. In this paper, we address the question of whether for general TT- MCTAG, i.e., TT-MCTAG without the constraint from (Kallmeyer and Parmentier, 2008), the class of generated languages is included in PTIME. We provide a positive answer to this question. The TT-MCTAG definition from (Lichte, 2007; Kallmeyer and Parmentier, 2008) imposes a con- dition on the way different tree components from a tree tuple in the grammar combine with each other. This condition is formulated in terms of mapping between argument and head trees, i.e., in order to test such a …

Content truncated to 500 words