On Gapping Grammars

A Gapping Grammar (GG) has rewriting rules of the form: \[\alpha_{1}, {gap}(x_{1}), \alpha_{2}, {gap}(x_{2}), \ldots, \alpha_{n-1}, {gap}(x_{n-1}), \alpha_{n} \rightarrow \beta\] \[\alpha_{i} \epsilon V_{N} \bigcup V_{T}\] \{ {\em gap}(x_{1}),{\em gap}(x_{2}), \ldots,{\em gap}(x_{n-1}) \}\] \[x_{i} \epsilon V_{T}^{*}\] \[\beta \epsilon V_{N}^{*} \bigcup V_{T}^{*} \bigcup G^{*}\] where $V_{T}$ and $V_{N}$ are the terminal and non-terminal vocabularies of the Gapping Grammar. Intuitively, a GG rule allows one to deal with unspecified strings of terminal symbols called {\em gaps}, represented by $x_{1}, x_{2}, \ldots, x_{n-1}$, in a given context of specified terminals and non-terminals, represented by $\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n}$ and then to distribute them in the right hand side $\beta$ in any order. GG's are a generalization of Fernando Pereira's {Extrapontion Grammars} where rules have the form (using our notation ): \begin{eqnarray*} \alpha_{1},{gap}(x_{1}), \alpha_{2}, {gap}(x_{2}), \ldots, {gap}(x_{n-1}), \alpha_{n} \rightarrow \\ \beta, { gap}(x_{1}), {gap}(x_{2}), \ldots, {gap}(x_{n-1}) \end{eqnarray*} i.e., gaps are rewritten in their sequential order in the rightmost positions of the rewriting rule. In this paper we motivate GG's by presenting grammatical examples where XGs are not adequate and we describe and discuss alternative implementations of GGs in logic.