Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 276–284, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems Carlos Gómez-Rodríguez1, Marco Kuhlmann2, and Giorgio Satta3 1Departamento de Computación, Universidade da Coruña, Spain, cgomezr@udc.es 2Department of Linguistics and Philology, Uppsala University, Sweden, marco.kuhlmann@lingfil.uu.se 3Department of Information Engineering, University of Padua, Italy, satta@dei.unipd.it Abstract The use of well-nested linear context-free rewriting systems has been empirically moti- vated for modeling of the syntax of languages with discontinuous constituents or relatively free word order. We present a chart-based pars- ing algorithm that asymptotically improves the known running time upper bound for this class of rewriting systems. Our result is obtained through a linear space construction of a binary normal form for the grammar at hand. 1 Introduction Since its earliest years, one of the main goals of computational linguistics has been the modeling of natural language syntax by means of formal gram- mars. Following results by Huybregts (1984) and Shieber (1985), special attention has been given to formalisms that enlarge the generative power of con- text-free grammars, but still remain below the full generative power of context-sensitive grammars. On this line of investigation, mildly context-sensitive grammar formalisms have been introduced (Joshi, 1985), including, among several others, the tree ad- joining grammars (TAGs) of Joshi et al. (1975). Linear context-free rewriting system (LCFRS), in- troduced by Vijay-Shanker et al. (1987), is a mildly context-sensitive formalism that allows the deriva- tion of tuples of strings, i.e., discontinuous phrases. This feature has been used to model phrase structure treebanks with discontinuous constituents (Maier and Søgaard, 2008), as well as to map non-projective de- pendency trees into discontinuous phrase structures (Kuhlmann and Satta, 2009). Informally, in an LCFRS G, each nonterminal can generate string tuples with a fixed number of compo- nents. The fan-out of G is defined as the maximum number of tuple components generated by G. During a derivation of an LCFRS, tuple components gener- ated by the nonterminals in the right-hand side of a production are concatenated to form new tuples, possibly adding some terminal symbols. The only re- striction applying to these generalized concatenation operations is linearity, that is, components cannot be duplicated or deleted. The freedom in the rearrangement of components has specific consequences in terms of the computa- tional and descriptional complexity of LCFRS. Even for grammars with bounded fan-out, the universal recognition problem is NP-hard (Satta, 1992), and these systems lack Chomsky-like normal forms for fixed fan-out (Rambow and Satta, 1999) that are es- pecially convenient in tabular parsing. This is in con- trast with other mildly context-sensitive formalisms, and TAG in particular: TAGs can be parsed in poly- nomial time both with respect to grammar size and string size, and they can be cast in normal forms having binary derivation trees only. It has recently been argued that LCFRS might be too powerful for modeling languages with discontin- uous constituents or with relatively …

Content truncated to 500 words