Several recent stochastic parsers use bilexical grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present O(n^4) parsing algorithms for two bilexical formalisms, improving the prior upper bounds of O(n^5). For a common special case that was known to allow O(n^3) parsing (Eisner, 1997), we present an O(n^3) algorithm with an improved grammar constant.
Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars
SATTA, GIORGIO
1999
Abstract
Several recent stochastic parsers use bilexical grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present O(n^4) parsing algorithms for two bilexical formalisms, improving the prior upper bounds of O(n^5). For a common special case that was known to allow O(n^3) parsing (Eisner, 1997), we present an O(n^3) algorithm with an improved grammar constant.File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
