LINGUIST List 2.561

Thu 26 Sep 1991

Disc: Feature structures

Editor for this issue: <>

Directory

1. , Re: Q: Feature structures

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.