Optimal Rank Reduction for Linear Context-Free Rewriting Systems with Fan-Out Two

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 525–533, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Optimal rank reduction for Linear Context-Free Rewriting Systems with Fan-Out Two Benot Sagot INRIA & Universit´e Paris 7 Le Chesnay, France benoit.sagot@inria.fr Giorgio Satta Department of Information Engineering University of Padua, Italy satta@dei.unipd.it Abstract Linear Context-Free Rewriting Systems (LCFRSs) are a grammar formalism ca- pable of modeling discontinuous phrases. Many parsing applications use LCFRSs where the fan-out (a measure of the dis- continuity of phrases) does not exceed 2. We present an efficient algorithm for opti- mal reduction of the length of production right-hand side in LCFRSs with fan-out at most 2. This results in asymptotical run- ning time improvement for known parsing algorithms for this class. 1 Introduction Linear Context-Free Rewriting Systems (LCFRSs) have been introduced by Vijay- Shanker et al. (1987) for modeling the syntax of natural language. The formalism extends the generative capacity of context-free grammars, still remaining far below the class of context-sensitive grammars. An important feature of LCFRSs is their ability to generate discontinuous phrases. This has been recently exploited for modeling phrase structure treebanks with discontinuous constituents (Maier and Søgaard, 2008), as well as non-projective dependency treebanks (Kuhlmann and Satta, 2009). The maximum number f of tuple components that can be generated by an LCFRS G is called the fan-out of G, and the maximum number r of nonterminals in the right-hand side of a production is called the rank of G. As an example, context- free grammars are LCFRSs with f = 1 and r given by the maximum length of a production right-hand side. Tree adjoining grammars (Joshi and Levy, 1977) can also be viewed as a special kind of LCFRS with f = 2, since each auxil- iary tree generates two strings, and with r given by the maximum number of adjunction and sub- stitution sites in an elementary tree. Beyond tree adjoining languages, LCFRSs with f = 2 can also generate languages in which pair of strings derived from different nonterminals appear in so- called crossing configurations. It has recently been observed that, in this way, LCFRSs with f = 2 can model the vast majority of data in discontinu- ous phrase structure treebanks and non-projective dependency treebanks (Maier and Lichte, 2009; Kuhlmann and Satta, 2009). Under a theoretical perspective, the parsing problem for LCFRSs with f = 2 is NP-complete (Satta, 1992), and in known parsing algorithms the running time is exponentially affected by the rank r of the grammar. Nonetheless, in natu- ral language parsing applications, it is possible to achieve efficient, polynomial parsing if we suc- ceed in reducing the rank r (number of nontermi- nals in the right-hand side) of individual LCFRSs’ productions (Kuhlmann and Satta, 2009). This process is called production factorization. Pro- duction factorization is very similar to the reduc- tion of a context-free grammar production into Chomsky normal form. However, in the LCFRS case some productions might not be …

Content truncated to 500 words