Conversions between D and MCFG: Logical Characterizations of the Mildly Context-Sensitive Languages

Abstract

The Displacement Calculus (DC) of Morrill et al. (2011) extends Lambek categorial grammar with wrapping operations for handling discontinuous dependencies. In this paper, we study two computationally attractive fragments of DC and relate them via equivalence proofs to the wellnested Multiple Context Free Grammars (MCFG) of Kanazawa (2009). A first fragment, firstorder DC, has been shown in earlier work to enjoy polynomial parsability, but it sacrificies the hypothetical reasoning facilities that form a central feature of the syntax-semantics interface in logic grammars. Our main result then is to identify a second fragment, restricted two-dimensional DC, that allows for hypothetical reasoning, and to provide a conversion of Displacement Contextfree Grammar, a formalism equivalent to well-nested MCFG, into our restricted two-dimensional Displacement Grammar.