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

Anders SøgaardMach. Transl 2011 · OpenReview

Abstract

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 $${\mathcal{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 $${\mathcal{O}(|G|n^6)}$$ time extension generates all possible alignments. It is shown that this additional expressivity comes at the cost of probabilistic parsing.
BibTeX
@inproceedings{sgaard2011o,
  author = {Anders Søgaard},
  title = {{A O(|G|n time extension of inversion transduction grammars.6)}},
  booktitle = {Mach. Transl},
  year = {2011},
  url = {https://openreview.net/forum?id=COEyPLQgnqk},
}

Loading related content...

Figure