Synchronous Context-Free Grammars and Optimal Parsing Strategies

Abstract

The complexity of parsing with Synchronous Context-Free Grammars
is polynomial in the sentence length for a fixed grammar,
but the degree of the polynomial depends on the grammar.
Specifically, the degree depends on the length of rules,
the permutations represented by the rules, and the parsing strategy
adopted to decompose the recognition of a rule into smaller steps.
We address the problem of finding the best parsing strategy for
a rule, in terms of space and time complexity.  We show
that it is NP-hard to find the binary strategy with the lowest
space complexity.  We also show that any algorithm for
finding the strategy with the lowest time complexity would
imply improved approximation algorithms for finding the
treewidth of general graphs of fixed degree.