**Editor for this issue:** <>

Jean Veronis asks the following question: "In most of the work I know, unification of two disjunctive feature structures involves unfactoring the two features structures to their disjunctive normal form. In that case, it seems that there is no way to assign a particular disjunctive format to the resulting feature structure: it has to be in disjunctive normal form too. However, it seems to me that in many cases, the result of the unification has a possible disjunctive format. For example, it seems reasonable to think that the unification of the two following feature structures +-- --+ +-- --+ | A: a1 | | A: a1 | | | | E: e1 | | / \ | | | | | +- -+ | | | / \ | | | | B: b1 | | | | | +- -+ | | | | | C: c1 | | | | | | B: b1 | | | | / +- -+ \ | | | | D: d1 | | | | \ +- -+ / | | / +- -+ \ | | | | B: b2 | | | | \ +- -+ / | | | | C: c2 | | | | | | B: b2 | | | | | +- -+ | | | | | D: d2 | | | | \ / | | | +- -+ | | +-- --+ | \ / | +-- --+ will yield a feature structure formatted in the following way: +-- --+ | A: a1 | | E: e1 | | | | / \ | | | +- -+ | | | | | B: b1 | | | | | | C: c1 | | | | | | D: d1 | | | | / +- -+ \ | | \ +- -+ / | | | | B: b2 | | | | | | C: c2 | | | | | | D: d2 | | | | | +- -+ | | | \ / | +-- --+ Of course, this is a simple case where the two feature structures have very similar formats. In the general case, it is more difficult to define what the resulting format should be. Does anybody know a definition a unification for disjunctive feature structures that would assign a disjunctive format to the result? Any reference?" Ron Kaplan and I have developed a general purpose approach to this problem that we describe in [5,6]. Our approach works by turning disjunctions into conjunctions of implications. For example, the disjunctive constraints: (<f B>=b1 & <f C>=c1) V (<f B>=b2 & <f C>=c2) can be converted into the logically equivalent: (p -> <f B>=b1) & (p -> <f C>=c1) & (~p -> <f B>=b2) & (~p -> <f C>=c2) where p is a new propositional variable. We call a constraint of the form (P -> C) a "contexted" constraint, where P is the "context" and C is the "base" constraint. It is easy to make deductions on contexted constraints. If C1 & C2 --> C3, then (P -> C1) & (Q -> C2) --> (P & Q -> C3) where P and Q are arbitrary boolean combinations of propositional variables. In particular, (P -> <f B>=b1) & (Q -> <f B>=b2) --> (P & Q -> b1=b2). If b1 and b2 are distinct constants, then the base constraint b1=b2 is unsatisfiable. This means that P & Q is an invalid combination of propositional variables. Contexted constraints can be modeled using a contexted feature structure. Thus the disjunction (<f B>=b1 & <f C>=c1) V (<f B>=b2 & <f C>=c2) can be modeled as: +- -+ | B: / p -> b1 \ | | \~p -> b2 / | | C: / p -> c1 \ | | \~p -> c2 / | +- -+ Notice that the propositional variables are embedded under the attributes, and that they keep track of the dependencies between the value of B and the value of C. Applying this approach to the original example gives us: +-- --+ +-- --+ | A: a1 | | A: a1 | | | | E: e1 | | B: / p -> b1 \ | | B: / q -> b1 \ | | \~p -> b2 / | | \~q -> b2 / | | C: / p -> c1 \ | | D: / q -> c1 \ | | \~p -> c2 / | | \~q -> c2 / | +-- --+ +-- --+ Unifying these together, we get: +-- --+ | A: a1 | | E: e1 | | / p -> b1 \ | | B: / ~p -> b2 \ | | \ q -> b1 / | | \~q -> b2 / | | C: / p -> c1 \ | | \~p -> c2 / | | D: / q -> c1 \ | | \~q -> c2 / | +-- --+ >From the values under the B attribute we also deduce that (p & ~q -> b1=b2) and (~p & q -> b1=b2). (We also get (p & q -> b1=b1) and (~p & ~q -> b2=b2) but since b1=b1 and b2=b2 are tautologies these deductions are ignored.) Since these are unsatisfiable, the only valid combinations of propositional variables are p & q and ~p & ~q. This has been a very brief sketch of this approach. You might also be interested in some work by Eisele and Dorre[4,5] that is based on Karttunen's disjunctive values[5]. If you have any further questions, please address them directly to me since I am not on the Linguist distribution list. Cheers, John Maxwell [1] J. Maxwell and R. Kaplan. An overview of disjunctive constraint satisfaction. In Proceedings of the International Workshop on Parsing Technologies, 1989. [2] J. Maxwell and R. Kaplan. A method for disjunctive constraint satisfaction. In M. Tomita, editor, Current Issues in Parsing Technology, Kluwer Academic Publishers, 1991. [3] A. Eisele and J. Dorre. Unification of disjunctive feature descriptions. In Proceedings of the 26th Annual Meeting of the ACL, Buffalo, New York, 1988. [4] J. Dorre and A. Eisele. Feature logic with disjunctive unification. In Proceedings of COLING 1990, Helsinki, 1990. [5] L. Karttunen. Features and values. In Proceedings of COLING 1984, Stanford, Calif, 1984.Mail to author|Respond to list|Read more issues|LINGUIST home page|Top of issue