Categorial and Non-Categorial Languages

CATEGORIAL AND NON-CATEGORIAL LANGUAGES Joyce Friedman Ramarathnam Venkatesan ABSTRACT Computer Science Department Boston University 111 Cummington Street Boston, Massachusetts 02215 USA PREL1MIN A R IES We study the formal and linguistic proper- ties of a class of parenthesis-free categorial grammars derived from those of Ades and Steed- man by varying the set of reduction rules. We characterize the reduction rules capable of gen- erating context-sensitive languages as those having a partial combination rule and a combination rule in the reverse direction. We show that any categorial language is a permutation of some context-free language, thus inheriting properties dependent on symbol counting only. We compare some of their properties with other contem- porary formalisms. INTRODUCTION Categorial grammars have recently been the topic of renewed interest, stemming in part from their use as the underlying formalism in Montague grammar. While the original categorial grammars were early shown to be equivalent to context-free grammars, 1, 2, 3 modifications to the formalism have led to systems both more and less powerful than context-free grammars. Motivated by linguistic considerations, Ades and Steedman 4 introduced categorial grammars with some additional cancellation rules. Full cancellation rules correspond to application of functions to arguments. Their partial cancellation rules correspond to functional composition. The new backward combination rule is motivated by the need to treat preposed elements. They also modified the formalism by making category symbols parenthesis-free, treating them in general as governed by a convention of association to the left, but violat- ing this convention in certain of the rules. This treatment of categorial grammar suggests a family of eategorial systems, differing in the set of can- cellation rules that are allowed. Earlier, we began a study of the mathematical properties of that family of systems, s showing that some members are fully equivalent to context-free grammars, while others yield only a subset of the context-free languages, or a super- set of them. In this paper we continue with these investigations. We characterize the rule systems that can obtain context-sensitive languages, and compare the sets of categorial ]ar~guages with the context-free languages. Finally, we discuss the linguistic relevance of these results, and compare categorial grammars with TAG systems i, this regard. A categorial grammar under a set R of reduction rules is a quadruple CGR (VT, VA, S, F), whose ele- ments are defined as follows: VT is a finite set of mor- phemes. VA is a finite set of atomic category symbols. S EVA is a distinguished element of VA. To define F, we must first define CA, the set of category symbols. CA is given by:i) ifAEVA,thenA ECA;ii) ifX EUA and A EVA, then X/A ECA; andiii) nothing elselsin CA . F is the lexicon, a function from VT to 2 ea such that for every aEVT, F(a) is finite. We often write CGR to denote a categorial grammar with rule set R, when the elements of the quadruple are known. Notation: Morphemes are denoted by a, b; mor- pheme strings by u,v,w. The symbols S,A,B,C …

Content truncated to 500 words