Paper: Two monolingual parses are better than one (synchronous parse)

ACL ID N10-1033
Title Two monolingual parses are better than one (synchronous parse)
Venue Human Language Technologies
Session Main Conference
Year 2010
Authors

We describe a synchronous parsing algorithm that is based on two successive monolingual parses of an input sentence pair. Although the worst-case complexity of this algorithm is and must be O(n6) for binary SCFGs, its average-case run-time is far better. We demonstrate that for a number of common synchronous parsing problems, the two-parse algorithm substantially outperforms alterna- tive synchronous parsing strategies, making it efficient enough to be utilized without resort- ing to a pruned search.