Synchronous Context-Free Grammars and Optimal Linear Parsing Strategies
This addresses a computational complexity issue for researchers in computational linguistics and parsing algorithms, but it is incremental as it builds on known SCFG properties.
The paper tackled the problem of parsing with Synchronous Context-Free Grammars (SCFGs), showing that finding linear parsing strategies with minimum space and time complexity is NP-hard for given input permutations.
Synchronous Context-Free Grammars (SCFGs), also known as syntax-directed translation schemata, are unlike context-free grammars in that they do not have a binary normal form. In general, parsing with SCFGs takes space and time polynomial in the length of the input strings, but with the degree of the polynomial depending on the permutations of the SCFG rules. We consider linear parsing strategies, which add one nonterminal at a time. We show that for a given input permutation, the problems of finding the linear parsing strategy with the minimum space and time complexity are both NP-hard.