Strong Equivalence of TAG and CCG

Strong Equivalence of TAG and CCG Lena Katharina Schiffer and Andreas Maletti Faculty of Mathematics and Computer Science, Universit¨at Leipzig, Germany P.O. Box 100 920, D-04009 Leipzig, Germany {schiffer,maletti}@informatik.uni-leipzig.de Abstract Tree-adjoining grammar (TAG) and combina- tory categorial grammar (CCG) are two well- established mildly context-sensitive grammar formalisms that are known to have the same expressive power on strings (i.e., generate the same class of string languages). It is demon- strated that their expressive power on trees also essentially coincides. In fact, CCG with- out lexicon entries for the empty string and only first-order rules of degree at most 2 are sufficient for its full expressive power. 1 Introduction Combinatory categorial grammar (CCG) (Steedman, 2000; Steedman and Baldridge, 2011) is one of several grammar formalisms that were introduced as an extension of context-free gram- mars. In particular, CCG extends the classical cate- gorial grammar (Bar-Hillel et al., 1960), which has the same expressivity as context-free grammar, by rules that are inspired by combinatory logic (Curry et al., 1958). CCG is a mildly context-sensitive grammar formalism (Joshi, 1985). Context- sensitive grammar formalisms are formalisms that are efficiently parsable (i.e., in polynomial time) and have expressivity beyond the context- free languages. They are able to express a limited amount of cross-serial dependencies and have the constant growth property. Because of these fea- tures and its notion of syntactic categories, which is quite intuitive for natural languages, CCG has become widely applied in compuational linguis- tics (Steedman, 2000). Further, it can be enhanced by semantics through the lambda calculus. CCG is based on a lexicon and a rule system. The lexicon assigns syntactic categories to the symbols of an input string and the rule system describes how neighboring categories can be combined to new categories. Each category has a target, which is similar to the return type of a function, and optionally, a number of arguments. Different from functions, each argument has a directionality that indicates if it is expected on the left or the right side. If repeated combination of categories leads to a (binary) derivation tree that comprises all input symbols and is rooted in an initial category, then the input string is accepted. When defining CCG, there are many degrees of freedom yielding a number of different variants (Steedman, 2000; Baldridge, 2002; Steedman and Baldridge, 2011; Kuhlmann et al., 2015). This is a consequence of the linguistically motivated need to easily express specific structures that have been identified in a particular theory of syntax for a given natural language. However, we and others (Kuhlmann et al., 2015) are interested in the expressive power of CCGs as generators of formal languages, since this allows us to disentan- gle the confusion of subtly different formalisms and identify the principal structures expressible by a common core of the formalisms. As linguis- tic structure calls for a representation that goes beyond strings, we aim for a characterization of expressive power in terms of the generated trees. The most famous result on the expressive power of …

Content truncated to 500 words