Combinatory Categorial Grammars: Generative Power and Relationship to Linear Context-Free Rewriting Systems

COMBINATORY CATEGORIAL GRAMMARS: GENERATIVE POWER AND RELATIONSHIP TO LINEAR CONTEXT-FREE REWRITING SYSTEMS" David J. Weir Aravind K. Joshi Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104-6389 Abstract Recent results have established that there is a family of languages that is exactly the class of languages generated by three independently developed grammar formalisms: Tree Adjoining Grammm~, Head Grammars, and Linear Indexed Grammars. In this paper we show that Combina- tory Categorial Grammars also generates the same class of languages. We discuss the slruclm'al descriptions pro- duced by Combinawry Categorial Grammars and com- pare them to those of grammar formalisms in the class of Linear Context-Free Rewriting Systems. We also discuss certain extensions of CombinaWry Categorial Grammars and their effect on the weak generative capacity. 1 Introduction There have been a number of results concerning the rela- tionship between the weak generative capacity (family of string languages) associated with different grammar for- malisms; for example, the thecxem of Oaifman, et al. [3] that Classical Categorial Grammars are weakly equivalent to Context-Free Grammars (CFG's). Mote recently it has been found that there is a class of languages slightly larger than the class of Context-Free languages that is generated by several different formalisms. In pardodar, Tree Ad- joining Grammars (TAG's) and Head Grammars (HG's) have been shown to be weakly equivalent [15], and these formalism are also equivalent to a reslriction of Indexed Grammars considered by Gazdar [6] called Linear In- dexed Grammars (LIG's) [13]. In this paper, we examine Combinatory Categorial Grammars (CCG's), an extension of Classical Catego- rial Grammars developed by Steedman and his collab- orators [1,12,9,10,11]. The main result in this paper is *This work was partially mpported by NSF gnmts MCS-82-19116- CER. MCS-82-07294, DCR-84-10413, ARO grant DAA29-84-9-0027. and DARPA gnmt N0014-85-K0018. We are very grateful to Mark Steedmm, ]C Vijay-Shanker and Remo Pare~:hi for helpful disctmiem. that CCG's are weakly equivalent to TAG's, HG's, and LIG's. We prove this by showing in Section 3 that Com- binatory Categorlal Languages (CCL's) are included in Linear Indexed Languages (LIL's), and that Tree Adjoin- ing Languages (TAL's) are included in CCL's. After considering their weak generative capacity, we investigate the relationship between the struclzwal descrip- tions produced by CCG's and those of other grammar for- malisms. In [14] a number of grammar formalisms were compared and it was suggested that an important aspect of their descriptive capacity was reflected by the deriva- tion structures that they produced. Several formalisms that had previously been descn2~d as mildly context- sensitive were found to share a number of properties. In particular, the derivations of a grammar could be repre- senled with trees that always formed the tree set of a context-free grammar. Formalisms that share these prop- erties were called Linear Context-Free Rewriting Systems ('LCFRS's) [14]. On the basis of their weak generative capacity, it ap- pears that CCG's should be classified as mildly context- sensitive. In Section 4 we consider whether CCG's should be included in the class of LCFRS's. The …

Content truncated to 500 words