[CLG logo] Computational Linguistics Group
Department of Computer Science
University of Haifa

[Haifa logo]

Highly Constrained Unification Grammars

Project description

To define constraints on unification grammars that guarantee efficient processing.
Daniel Feinstein, Hadas Peled, and Shuly Wintner
Israeli Science Foundation (grant 136/01)


Unification grammars are Turing equivalent in their generative capacity: determining whether a given string is generated by a given grammar is as hard as deciding whether a Turing machine halts on the empty input.

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 context-sensitive grammars. A range of such formalisms is well-established (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 context-sensitive 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 +972-4-8288180
Fax +972-4-8249331
E-mail shuly@cs.haifa.ac.il

Computational Linguistics Group, http://cl.haifa.ac.il/
Department of Computer Science, University of Haifa
Maintained by shuly@cs.haifa.ac.il, modified Sunday December 13, 2015.