clarke@csri.toronto.edu (Jim Clarke) (07/27/88)
NATURAL LANGUAGE SEMINAR, Thursday, August 4 at 11 a.m., SF3207
(SF = Sandford Fleming Building, 10 King's College Road)
Remo Pareschi
University of Pennsylvania
and
University of Edinburgh
``A Definite Clause Version
of Categorial Grammar"
Categorial Grammar is a framework for natural language analysis where gram-
matical 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 require-
ments of adjacency between combinable constituents, and word-order con-
straints 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 for-
malism, parsing can be efficiently implemented as theorem proving. Our
approach to encoding types as definite clauses presupposes a modifica-
tion 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.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke