Paper: Parsing And Derivational Equivalence

ACL ID E89-1002
Title Parsing And Derivational Equivalence
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1989

It is a tacit assumption of much linguistic inquiry that all distinct derivations of a string should assign distinct meanings. But despite the tidiness of such derivational uniqueness, there seems to be no a pri- ori reason to assume that a gramma r must have this property. If a grammar exhibits derivational equiv- alence, whereby distinct derivations of a string as- sign the same meanings, naive exhaustive search for all derivations will be redundant, and quite possibly intractable. In this paper we show how notions of derivation-reduction and normal form can be used to avoid unnecessary work while pars- ing with grammars exhibiting derivational equiv- alence. With grammar regarded as analogous to logic, derivations are proofs; what we are advocat- ing is proof-reduction, and normal form ...