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.
Optimal Head-Driven Parsing Complexity for Linear Context-Free Rewriting Systems / P. Crescenzi; D. Gildea; A. Marino; G. Rossi; G. Satta. - ELETTRONICO. - (2011), pp. 450-459. (Intervento presentato al convegno The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies tenutosi a Portland, Oregon, USA nel 19-24 June, 2011).
Optimal Head-Driven Parsing Complexity for Linear Context-Free Rewriting Systems
CRESCENZI, PIERLUIGI;MARINO, ANDREA;
2011
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.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
