An Optimal-Time Binarization Algorithm for Linear Context-Free Rewriting Systems with Fan-Out Two

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 985–993, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP An Optimal-Time Binarization Algorithm for Linear Context-Free Rewriting Systems with Fan-Out Two Carlos G´omez-Rodr´ıguez Departamento de Computaci´on Universidade da Coru˜na, Spain cgomezr@udc.es Giorgio Satta Department of Information Engineering University of Padua, Italy satta@dei.unipd.it Abstract Linear context-free rewriting systems (LCFRSs) are grammar formalisms with the capability of modeling discontinu- ous constituents. Many applications use LCFRSs where the fan-out (a measure of the discontinuity of phrases) is not allowed to be greater than 2. We present an ef- ficient algorithm for transforming LCFRS with fan-out at most 2 into a binary form, whenever this is possible. This results in asymptotical run-time improvement for known parsing algorithms for this class. 1 Introduction Since its early years, the computational linguistics field has devoted much effort to the development of formal systems for modeling the syntax of nat- ural language. There has been a considerable in- terest in rewriting systems that enlarge the generat- ive power of context-free grammars, still remain- ing far below the power of the class of context- sensitive grammars; see (Joshi et al., 1991) for dis- cussion. Following this line, (Vijay-Shanker et al., 1987) have introduced a formalism called linear context-free rewriting systems (LCFRSs) that has received much attention in later years by the com- munity. LCFRSs allow the derivation of tuples of strings,1 i.e., discontinuous phrases, that turn out to be very useful in modeling languages with rel- atively free word order. This feature has recently been used for mapping non-projective depend- ency grammars into discontinuous phrase struc- tures (Kuhlmann and Satta, 2009). Furthermore, LCFRSs also implement so-called synchronous 1In its more general definition, an LCFRS provides a framework where abstract structures can be generated, as for instance trees and graphs. Throughout this paper we focus on so-called string-based LCFRSs, where rewriting is defined over strings only. rewriting, up to some bounded degree, and have recently been exploited, in some syntactic vari- ant, in syntax-based machine translation (Chiang, 2005; Melamed, 2003) as well as in the modeling of syntax-semantic interface (Nesson and Shieber, 2006). 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), or TAG for short, can be viewed as a special kind of LCFRS with f = 2, since each elementary tree generates two strings, and r given by the maximum number of adjunction sites in an elementary tree. Several parsing algorithms for LCFRS or equi- valent formalisms are found in the literature; see for instance (Seki et al., 1991; Boullier, 2004; Bur- den and Ljungl¨of, 2005). All …

Content truncated to 500 words