Bob Carpenter (carp@research.bell-labs.com)
Mon, 25 Nov 1996 13:36:21 -0500 (EST)
R. D. Borsley writes: > Has anyone thought about the implications for HPSG-type theories of the > observations and ideas about coordination in Bayer's recent Language > paper on coordination? It seems to me that he presents quite strong > evidence for including some sort of disjunction and conjunction within > categories, but also that there are objections to some features of his > approach. As I understand it, he assumes that the work that is done in > HPSG-type grammars by underspecification should be done entirely by > disjunction (join). This would seem to entail that object position would > have to be identified as a position allowing an [NPdefsing or NPindefsing > or NPdefplur or NPindefplur] (at least). This seems pretty undesirable. If you look at the logic of 'underspecification' in HPSG, it's just disjunction in a very strong sense. Specifically, if we have a type A with subtypes B and C, then we'd always get exactly the same resulting signs by replacing any occurrence of A with (B or C). > Unlike an underspecification appproach, this approach also does not lead one > to expect the same range of options in different positions, e.g. object > of a verb and object of a preposition. This must be a disadvantage. But underspecification doesn't lead you to believe anything either. Rather the other way around -- the fact that something behaves two ways leads you to analyze it as underspecification or disjunction in HPSG. Given HPSG's architecture ala Pollard and Sag 1994, any disjunction could be replaced with an underspecification and appropriate subtypes for the disjuncts or vice-versa. > further point is that his join introduction, which allows an X to count > as an [X or Y], must surely lead to computational problems. Actually, the logic presented by Bayer and Johnson is *decidable* because it is just a directed instance of propositional logic. And this in the general case (no matter what the lexicon looks like). For instance, theorem proving in propositional logic isn't made undecidable because we can conclude A or B from any instance of proposition A. Rather, we can use a goal-driven search. The idea computationally is very similar to top-down parsing when you only postulate an empty category if you need one. The fact that there are infinitely many possible locations for an empty category doesn't cause a problem -- you only use the ones you need, and going top down, you know when you need one. Correspondingly, in logic, you only try to derive an (A or B) if you need an (A or B). The same concerning decidability *cannot* be said for HPSG, although most of the lexicons presented that I'm aware of are in fact decidable. But you have put your finger on the important issue of implementations, which is where underspecifications are very useful. But the point here is that underspecification can be used in type-logical categorial grammars, too, for implementation. It is important to keep in mind that 'underspecification' is nothing more than an implicit universal quantifier. That is: np(X), which can be instantiated to np(nom) or np(acc), using DCG notation, should really be listed as (ALL x)np(x) with the logic of universal instantiation allowing weakening to np(nom) or np(acc) in the usual way. Now what's interesting is that if you restrict x, as in HPSG, say to: (ALL x IN {nom, acc})np(x) then this is logically equivalent to: np(nom) AND np(sing) in the usual way that finite quantifications are the same as conjunctions, and then weakening is used in the same way. This points out the history of underspecification and unification, which was introduced in the 1960s in the theorem-proving literature (and in the 1930s, I think, in the logical literature) to represent universal quantifiers for resolution theorem proving. What limits HPSG's expressive power (but not its computational power) is that you can *only* use wide-scope universal quantifiers. If you write down np(X)/n(X) then you get a wide-scope universal quantifier over X. And if you write down a disjunction in a lexical entry, it distributes over the whole entry. Prolog enforces the same restriction (that's where the term 'definite clause' comes from -- a single conclusion without disjunction and wide-scope quantification -- a Prolog rule is of the form of a definite clause: ALL x1,...xN [ (A1 AND ... AND Am) -> A0 ] HPSG has assumed the same kind of normal form, most likely because a lot of us working on HPSG came to it through logic programming or through PATR, etc., which itself descended from logic programming. > It would be > better I would have thought, if disjunction was a consequence of conjoining > unlike categories and not a prerequisite for such coordination. I assume too > that his antecedent strengthening, which allows an element requiring an X > to count as an element requiring an [X and Y] must also lead to > computational problems. Again, it would seem better if conjunction were a > consequence of coordination of categories with different requirements and > not a prerequisite. > No! There are no computational problems. Again, by simple logic, you should read the A/B categories as an implication from B to A logically (this is a deep connection via the Curry-Howard morphism and also relates to semantic types and lambda terms and normalized derivations, which themselves relate closely to decidability by limiting the search space to a finite one. Then it's easy to see why vp/(np OR adj) is equivalent to (vp/np AND vp/adj). This is for the same reason that (A or B) -> C is equivalent to ((A -> C) and (B -> C)) in propositional logic. But the other thing to notice is that any finite disjucntion can be represented by a scope-restricted universal quantifier, as shown above. They're logically equivalent mechanisms. Thus underspecification just *is* a kind of implicit disjunction. What may not be clear from an HPSG/unification grammar perspective is that in logic, there is a duality between disjunction and conjunction in so-called positive and negative occurrences of propositions. In A->B, A is negative and B is positive (consider the equivalence of A->B to ~A or B). Now the issue here is that de Morgan's law converts conjuncts to disjuncts inside of negative contexts, because ~(A or B) == ~A and ~B, and ~(A and B) == ~A or ~B. This is why (A or B) -> C is equivalent to (A -> C) and (B -> C) whereas A->(B or C) is not equivalent to (A -> B) AND (A -> C) [and in intuitionistic and linear logic is not even equivalent to ((A -> B) or (A -> C)]. The interesting thing here is that the logic of simple classical disjunction and conjunction (specifying that something can be either an A or a B, or that it can be both an A and a B) has exactly the right consequences for reasoning about linguistic categories. It's just a natural way to reason about any kinds of categories. But what's even more interesting is that the type-logical theory gets the semantics right of conjunction and disjunction. Conjunction corresponds to product (pairing) and disjunction to disjoint union. See Glyn Morrill's book on Type Logical Grammar or my forthcoming book on Type Logical Semantics for details. It's really quite beautiful the way it all works out without stipulation, as a linguist would say :-). This is just what you get in any theory with lexical ambiguity, and there aren't 'computational problems' at all. It's all well within propositional logic. Of course that's NP complete, but given that simple unification with disjunction/ambiguity in HPSG is also NP complete, this shouldn't give anyone on this list problems sleeping. > Does anyone have any thoughts on any of this? > > Bob Borsley > > Department of Linguistics | URL: http://www.linguistics.bangor.ac.uk/ > University of Wales, Bangor | FAX: +44 1248 38 29 28 > Bangor LL57 2DG | > Wales | Visit our web pages! - Bob ------------------------------------------------------------------------------ Bob Carpenter Email: carp@research.bell-labs.com Lucent Technologies Bell Labs WWW: http://macduff.andrew.cmu.edu/carpenter 600 Mountain Avenue, 2D-329 Voice: 908 582-5790 Murray Hill, NJ 07974 Fax: 908 582-3306 ------------------------------------------------------------------------------
This archive was generated by hypermail 2.0b3 on Fri Dec 18 1998 - 20:33:30 PST