Discontinuous Data-Oriented Parsing through Mild Context-Sensitivity
Andreas van Cranenburgh

Abstract:
It has long been argued that incorporating a notion of discontinuity
in phrase-structure is desirable, given phenomena such as
topicalization and extraposition, and particular features of languages
such as cross-serial dependencies in Dutch and the German
Mittelfeld. Up until recently this was mainly a theoretical topic, but
advances in parsing technology have made treebank parsing with
discontinuous constituents possible, with favorable results.

We improve on this by applying Data-Oriented Parsing (DOP) to a mildly
context-sensitive grammar formalism which allows for discontinuous
trees.  Decisions during parsing are conditioned on all possible
fragments, resulting in improved performance. Despite the fact that
both DOP and discontinuity present formidable challenges in terms of
computational complexity, the model is reasonably efficient. Our
results emulate and surpass the state of the art in discontinuous
parsing.