Computational Linguistics Group Department of Computer Science University of Haifa

The main objective of this work is to define constraints on unification grammars which will guarantee efficient (polynomial) processing. There are naive constraints which restrict the expressiveness of unification grammars in a way which ensures polynomial parsing time, but they are too strong. For example, a possible restriction is to disallow reentrancies in feature structures. The resulting class of grammars is equivalent to CFGs. Another example is Generalized Phrase Structure Grammar (GPSG). Among current syntactic theories, GPSG provides an appealing solution for describing natural languages with its modular system of composite categories, rules, constraints and feature propagation principles. GPSG is known to be equivalent to CFG, thus inducing a polynomial recognition parsing time. In both cases above, however, the resulting formalisms are equivalent to CFG which is not enough for describing natural languages.
It is now widely accepted that natural languages can be adequately described by mildly contextsensitive grammars. A range of such formalisms is wellestablished (e.g., Tree Adjoining Grammars, Linear Indexed Grammars, Combinatory Categorial Grammars, Head Grammars, and also Stabler's Minimalist Grammars). Our goal in this work, and its expected main contribution, is to define an effectively testable syntactic constraint on unification grammars which will ensure that grammars satisfying the constraint generate all and only the mildly contextsensitive languages. Other possible extensions of this work include a definition of more restrictive constraints on unification grammars that would guarantee, for example, cubic recognition time, linear recognition time etc.
Mailing address  Shuly Wintner Department of Computer Science University of Haifa 31905 Haifa, Israel. 
Phone  +97248288180 
Fax  +97248249331 
shuly@cs.haifa.ac.il 
http://cl.haifa.ac.il/
shuly@cs.haifa.ac.il
,
modified Sunday December 13, 2015.