Efficient parsing algorithm for CFG with robust dependency constraints

A context-free grammar (CFG) in which dependency constraints are tucked into production rules has been proposed, where syntactic categories are subdivided by the headword of the phrase. It's difficult to collect all necessary rules expressing dependency constraints in the grammar, so taking superordinate-subordinate relations in the word hierarchy into the grammar as production rules has been considered. However, because there are huge number of syntactic trees for an input sentence in this grammar, how to select a preferable syntactic tree is very important. This paper shows an efficient parsing algorithm, specialized to the heuristics for selecting the most plausible syntactic tree.