tailieunhanh - Báo cáo khoa học: "COMBINATORY CATEGORIAL RELATIONSHIP TO LINEAR GRAMMARS: GENERATIVE POWER AND CONTEXT-FREE REWRITING SYSTEMS""

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 Combinatory Categorial Grammars also generates the same class of languages. We discuss the slruclm'al descriptions produced by Combinawry Categorial Grammars and compare them to those of grammar formalisms in the class of 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 Grammars Head Grammars and Linear Indexed Grammars. In this paper we show that Combinatory Categorial Grammars also generates the same class of languages. We discuss the structural descriptions produced by Combinatory Categorial Grammars and compare them to those of grammar formalisms in the class of Linear Context-Free Rewriting Systems. We also discuss certain extensions of Combinatory Categorial Grammars and their effect on the weak generative capacity. 1 Introduction There have been a number of results concerning the relationship between the weak generative capacity family of string languages associated with different grammar formalisms for example the theorem of Gaifman et al. 3 that Classical Categorial Grammars are weakly equivalent to Context-Free Grammars CFG s . More 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 particular Tree Adjoining Grammars TAG S and Head Grammars HG s have been shown to be weakly equivalent 15 and these formalism are also equivalent to a restriction of Indexed Grammars considered by Gazdar 6 called Linear Indexed Grammars LIG s 13 . In this paper we examine Combinatory Categorial Grammars CCG s an extension of Classical Categorial Grammars developed by Steedman and his collaborators 1 12 9 10 11 . The main result in this paper is This woik WM partially supported by NSF grants MCS-82-19116-CER MCS-82-07294 DCR-84-10413 ARO grant DAA29-84-9-0027 and DARPA grant N0014-85-K0018. We are .