Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Linear context-free rewriting systems (LCFRSs) are grammar formalisms with the capability of modeling discontinuous 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 efficient 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. | An Optimal-Time Binarization Algorithm for Linear Context-Free Rewriting Systems with Fan-Out Two Carlos Gomez-Rodriguez Departamento de Computacion Universidade da Coruna 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 discontinuous 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 efficient 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 natural language. There has been a considerable interest in rewriting systems that enlarge the generative power of context-free grammars still remaining far below the power of the class of contextsensitive grammars see Joshi et al. 1991 for discussion. 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 community. LCFRSs allow the derivation of tuples of strings 1 i.e. discontinuous phrases that turn out to be very useful in modeling languages with relatively free word order. This feature has recently been used for mapping non-projective dependency grammars into discontinuous phrase structures 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. .
