A Definite Clause Version of Categorial Grammar

A DEFINITE CLAUSE VERSION OF CATEGORIAL GRAMMAR Remo Pareschi," Department of Computer and Information Science, University of Pennsylvania, 200 S. 33 rd St., Philadelphia, PA 19104, t and Department of Artificial Intelligence and Centre for Cognitive Science, University of Edinburgh, 2 Buccleuch Place, Edinburgh EH8 9LW, Scotland remo(~linc.cis.upenn.edu ABSTRACT We introduce a first-order version of Catego- rial Grammar, based on the idea of encoding syn- tactic types as definite clauses. Thus, we drop all explicit requirements of adjacency between combinable constituents, and we capture word- order constraints simply by allowing subformu- lae of complex types to share variables ranging over string positions. We are in this way able to account for constructiods involving discontin- uous constituents. Such constructions axe difficult to handle in the more traditional version of Cate- gorial Grammar, which is based on propositional types and on the requirement of strict string ad- jacency between combinable constituents. We show then how, for this formalism, parsing can be efficiently implemented as theorem proving. Our approach to encoding types:as definite clauses presupposes a modification of standard Horn logic syntax to allow internal implications in definite clauses. This modification is needed to account for the types of higher-order functions and, as a con- sequence, standard Prolog-like Horn logic theorem proving is not powerful enough. We tackle this * I am indebted to Dale Miller for help and advice. I am also grateful to Aravind Joshi, Mark Steedman, David x, Veir, Bob Frank, Mitch Marcus and Yves Schabes for com- ments and discussions. Thanks are due to Elsa Grunter and Amy Feh.y for advice on typesetting. Parts of this research were supported by: a Sloan foundation grant to the Cog- nitive Science Program, Univ. of Pennsylvania; and NSF grants MCS-8219196-GER, IRI-10413 AO2, ARO grants DAA29-84-K-0061, DAA29-84-9-0027 and DARPA grant NOOO14-85-K0018 to CIS, Univ. of Pezmsylvani& t Address for correspondence problem by adopting an intuitionistic treatment of implication, which has already been proposed elsewhere as an extension of Prolog for implement- ing hypothetical reasoning and modular logic pro- gramming. 1 Introduction Classical Categorial Grammar (CG) [1] is an ap- proach to natural language syntax where all lin- guistic information is encoded in the lexicon, via the assignment of syntactic types to lexical items. Such syntactic types can be viewed as expressions of an implicational calculus of propositions, where atomic propositions correspond to atomic types, and implicational propositions account for com- plex types. A string is grammatical if and only if its syntactic type can be logically derived from the types of its words, assuming certain inference rules. In classical CG, a common way of encoding word-order constraints is by having two symmet- ric forms of "directional" implication, usually in- dicated with the forward slash / and the backward slash \, constraining the antecedent of a complex type to be, respectively, right- or left-adjacent. A word, or a string of words, associated with a right- (left-) oriented type can then be thought of as a right- (left-) oriented function looking for an ar- gument …

Content truncated to 500 words