**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.