Highly Constrained Unification Grammars

Project description

Objective: To define constraints on unification grammars that guarantee efficient processing.

Researchers: Daniel Feinstein, Hadas Peled, and Shuly Wintner.

Status: Complete

Funding: Israeli Science Foundation (grants 136/01).

Abstract

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.

Resources

None.

Publications

• Hadas Peled and Shuly Wintner. Polynomially-parsable Unification Grammars. Journal of Logic and Computation 25(5):1167-1202, October 2015. 

• Hadas Peled. Polynomially-parsable Unification Grammars, University of Haifa M.Sc. thesis, November 2011.

• Daniel Feinstein and Shuly Wintner. Highly Constrained Unification Grammars. Journal of Logic, Language and Information 17(3):345-381, July 2008. 

• Daniel Feinstein and Shuly Wintner. Highly Constrained Unification Grammars. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pages 1089-1096, Sydney, Australia, July 2006.

• Daniel Feinstein. Computational properties of Unification Grammars. October 2004. University of Haifa M.Sc. Thesis.