tailieunhanh - Báo cáo khoa học: "PARSING AND DERIVATIONAL EQUIVALENCE"

It is a tacit assumption of m u c h 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 priori reason to assume that a g r a m m a r must have this property. If a grammar exhibits derivational equivalence, whereby distinct derivations of a string assign 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. | Parsing and Derivational Equivalence Mark Hepple and Glyn Morrill Centre for Cognitive Science University of Edinburgh 2 Buccleuch Place Edinburgh EH8 9LW Scotland Abstract It is a tacit assumption of much linguistic inquừy 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 priori reason to assume that a grammar must have this property. If a grammar exhibits derivational equivalence whereby distinct derivations of a string assign 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 parsing with grammars exhibiting derivational equivalence. With grammar regarded as analogous to logic derivations are proofs what we are advocating is proof-reduction and normal form proof the invocation of these logical techniques adds a further paragraph to the story of parsing-as-deduction. Introduction The phenomenon of derivational equivalence is most evident in work on generalised categorial grammars where it has been referred to as spurious ambiguity . It has been argued that the capacity to assign left-branching and therefore incrementally interpretable analyses makes these grammars of particular psychological interest. We will illustrate our methodology by reference to generalised categorial grammars using a combinatory logic as opposed to say lambda-calculus semantics. In particular we consider combinatory categorial grammars with rules and generalised rules We thank Mike Reape for criticism and suggestions in relation to this material and Inge Bethke and Henk Zee-vat for reading a late draft. All errors are our own. The work was carried out by the alphabetically first author under ESRC Postgraduate Award 000428722003 and by the second under ESRC Postgraduate Award C00428522008 and an SERC .