A O(|G|n~6) time extension of inversion transduction grammars

摘要

Range concatenation grammars are viewed as a hierarchy of synchronous grammars. It is shown how inversion transduction grammars (ITGs) and extensions thereof, including synchronous tree-adjoining grammars, are captured by the hierarchy, and the expressivity and linguistic relevance of subclasses of the hierarchy are discussed. A O(|G|n~6) time extension of ITGs is proposed. The extension translates cross-serial dependencies into nested ones and handles complex kinds of discontinuous translation units and so-called inside-out alignments. In fact, our O(|G|n~6) time extension generates all possible alignments. It is shown that this additional expressivity comes at the cost of probabilistic parsing.