[ont.events] Characterizing Mildly Context-Sensitive Grammatical Formalisms.

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.