ylfink@water.waterloo.edu (ylfink) (05/07/88)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
ARTIFICIAL INTELLIGENCE SEMINAR
- Thursday, May 12, 1988
Dr. Remo Pareschi, University of Pennsylvania, will
speak on ``A Definite Clause Version of Categorial
Grammar''.
TIME: 11:00 AM
ROOM: DC 1302
ABSTRACT
Categorial Grammar is a framework for natural language
analysis where grammatical constituents are viewed
either as functions or arguments, and are associated
with corresponding syntactic types. We present a
first-order version of such a framework, based on the
idea of encoding syntactic types as definite clauses.
Under this approach, there are no explicit requirements
of adjacency between combinable constituents, and
word-order constraints are obtained simply by allowing
subformulae of complex types to share variables ranging
over string positions. It is in this way possible to
give a straightforward account of problematic syntactic
constructions involving discontinuous constituents,
which are particularly common in natural language. The
second half of this enterprise consists of showing 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 consequence,
standard Prolog-like Horn logic theorem proving is not
powerful enough. We tackle this problem by adopting an
intuitionistic treatment of implication, which has
been proposed elsewhere as a useful extension of
Prolog for implementing hypothetical reasoning and
modular logic programming. We then provide a parsing
algorithm in terms of a decision procedure which tries
to assign a type to a given input string, where the
size of the logic program needed for a type
assignment is always linear with respect to the length
of the input.