We study the problem of finding the best headdriven parsing strategy for Linear Context- Free Rewriting System productions. A headdriven 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. © 2011 Association for Computational Linguistics.
Optimal head-driven parsing complexity for Linear Context-Free Rewriting Systems
MARINO, ANDREA;
2011-01-01
Abstract
We study the problem of finding the best headdriven parsing strategy for Linear Context- Free Rewriting System productions. A headdriven 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. © 2011 Association for Computational Linguistics.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
