ylfink@water.waterloo.edu (ylfink) (01/19/88)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
ARTIFICIAL INTELLIGENCE SEMINAR
- Friday, January 22, 1988
Dr. David J. Weir, of the University of Pennsylvania,
will speak on ``Characterizing Mildly Context-Sensitive
Grammatical Formalisms''.
TIME: 11:30 AM
ROOM: MC 5158
ABSTRACT
Recent research suggests that Context-Free Grammars
(CFG's) lack the necessary expressive power on which to
base a linguistic theory. This has led computational
linguists to consider grammatical formalisms whose
generative power exceeds CFG's, but to only a limited
extent. We investigate the mathematical and
computational properties of several of these
formalisms, comparing them on the basis of their weak
generative capacity, and aspects of their strong
generative capacity. In particular, we consider
properties of their structural descriptions (or tree
sets); and the types of dependencies (nested, crossed,
etc.) that can be exhibited by each formalism.
Our work on structural descriptions leads us to
characterize a class of formalisms called Linear
Context-Free Rewriting Systems (LCFRS's), which
includes a wide range of grammatical formalisms with
restricted power. We prove that all members of this
family generate only semilinear languages that can be
recognized in polynomial time.
We show the weak equivalence of several LCFRS's that
are notationally quite different (Tree Adjoining
Grammars, Head Grammars, and Linear Indexed Grammars).
These formalisms produce languages exhibiting nested
and serial dependencies, in addition to limited
crossed-serial dependencies, which occur in certain
natural languages (e.g., Dutch). By formalizing the
relationship between crossed-serial dependencies and
the nested dependencies produced by CFG's we define an
infinite hierarchy of formalisms (belonging to
LCFRS's). These formalisms exhibit increasingly complex
dependencies and generate more complex structural
descriptions, yet maintain the desirable linguistic and
computational properties of Context-Free Grammars.