Optimal Head-Driven Parsing Complexity for Linear Context-Free Rewriting Systems

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 450–459, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Optimal Head-Driven Parsing Complexity for Linear Context-Free Rewriting Systems Pierluigi Crescenzi Dip. di Sistemi e Informatica Universit`a di Firenze Daniel Gildea Computer Science Dept. University of Rochester Andrea Marino Dip. di Sistemi e Informatica Universit`a di Firenze Gianluca Rossi Dip. di Matematica Universit`a di Roma Tor Vergata Giorgio Satta Dip. di Ingegneria dell’Informazione Universit`a di Padova Abstract We study the problem of finding the best head- driven parsing strategy for Linear Context- Free Rewriting System productions. A head- driven strategy must begin with a specified righthand-side nonterminal (the head) and add the remaining nonterminals one at a time in any order. We show that it is NP-hard to find the best head-driven strategy in terms of either the time or space complexity of parsing. 1 Introduction Linear Context-Free Rewriting Systems (LCFRSs) (Vijay-Shankar et al., 1987) constitute a very general grammatical formalism which subsumes context- free grammars (CFGs) and tree adjoining grammars (TAGs), as well as the synchronous context-free grammars (SCFGs) and synchronous tree adjoin- ing grammars (STAGs) used as models in machine translation.1 LCFRSs retain the fundamental prop- erty of CFGs that grammar nonterminals rewrite independently, but allow nonterminals to generate discontinuous phrases, that is, to generate more than one span in the string being produced. This important feature has been recently exploited by Maier and Søgaard (2008) and Kallmeyer and Maier (2010) for modeling phrase structure treebanks with discontinuous constituents, and by Kuhlmann and Satta (2009) for modeling non-projective depen- dency treebanks. The rules of a LCFRS can be analyzed in terms of the properties of rank and fan-out. Rank is the 1To be more precise, SCFGs and STAGs generate languages composed by pair of strings, while LCFRSs generate string lan- guages. We can abstract away from this difference by assuming concatenation of components in a string pair. number of nonterminals on the right-hand side (rhs) of a rule, while fan-out is the number of spans of the string generated by the nonterminal in the left- hand side (lhs) of the rule. CFGs are equivalent to LCFRSs with fan-out one, while TAGs are one type of LCFRSs with fan-out two. Rambow and Satta (1999) show that rank and fan-out induce an infi- nite, two-dimensional hierarchy in terms of gener- ative power; while CFGs can always be reduced to rank two (Chomsky Normal Form), this is not the case for LCFRSs with any fan-out greater than one. General algorithms for parsing LCFRSs build a dynamic programming chart of recognized nonter- minals bottom-up, in a manner analogous to the CKY algorithm for CFGs (Hopcroft and Ullman, 1979), but with time and space complexity that are dependent on the rank and fan-out of the gram- mar rules. Whenever it is possible, binarization of LCFRS rules, or reduction of rank to two, is there- fore important for parsing, as it reduces the time complexity needed for dynamic programming. This …

Content truncated to 500 words