Modularizing Contexted Constraints 
John Griffith* 
Seminar fiir Sprachwissenschaft 
Universitgt 'Fiibingen 
K1. Wilhehnstr. 113, 
D-72074 Tiibingen, Germany 
griflith4~)sfknphil.uni-tuebingen.de 
Abstract 
This paper describes a nlethod for com- 
piling a constraint-based grammar into 
a potentially inore efficient form for pro- 
cessing. This method takes dependent 
disjunctions within a constraint formula 
and factors them into non-interacting 
groups whenever possibh; by determining 
their independence. When a group of de- 
pendent disjunctions is split into slnaller 
groups, an exponential amount of redun- 
dant information is reduced. At runtime, 
this ineans that all exponential alnount 
of processing can be saved as well. Since 
the performance of an algorithm ibr pro- 
cessing constraints with dependent dis- 
jmmtions is highly deterxnined by its in- 
put, the transformatioll presented in this 
paper should prove beneficial for all such 
algorithms. 
1 Introduction 
There are two facts that conspire to make tile 
treatment of disjunction an important consider- 
ation when building a natural language process- 
ing (NLP) system. The first fact is that nat- 
ural languages are full of ambiguities, and in 
a grammar many of these ambiguities are de- 
scribed by disjunctions. The second fact is that 
the introduction of disjmmtion into a grammar 
causes processing tilne to increase exponentially 
in the number of disjunets. This means that a 
nearly linear-time operation, such as uififieation of 
Imrely conjunctive feature structures, becomes an 
exponential-time problem as soon as disjunctions 
are included, t Since disjunction is unlikely to dis- 
* This work was sponsored by Teilprojekt B4 
"t~¥om Constraints to Rules: Compilation of lipS(;" 
of the Sonderforsehungsbereieh 340 of the Deutsche 
Forsehungsgemeinschaft. I would also like to thank 
Dale Gerdemann and Guido Minnen for helpfltl com- 
ments on the ideas presented here. All remaining er- 
rors are of course my own. 
tAssuming P # NIL 
appear from natur~fl language gralnlnars, control- 
ling its form (:all save exponential amounts of time. 
This paper introduces all etficient normal tbrm 
for processing dependent disjunctive constraints 
and an operation for compilation into this normal 
form. This ot)eration , modularization, can reduce 
exponential alnounts of redtmdant information in 
a grainmar and can consequently save correspond- 
ing alnounts of processing time. While this oper- 
ation is general enough to be applied to a wide 
variety of constraint systems, it; was originally de- 
signed to optimize processing of dependent dis- 
junctions in featm'e structure-based grammars. In 
particular, modular fea.tuie structures are more 
eflicient R)r unification than non-Inodulm' ones. 
Since ill many current NLP systems, a signiti- 
cant amount of tilne is spent performing unifica- 
tion, optimizing feature structures for unillcatioll 
shouhl increase the tmrtbrmance of these, syst;ems. 
Many algorithms for etticient mfitication of lea 
tare structures with dependent disjunctions have 
been propose.d (Maxwell and Kaplan, 1989; F, isele 
and DSrre, 1990; Gerdemann, 1991; StrSmbSek, 
1992; Griflith, 1.996). However, all of these al- 
gorithms sutfer from a common problem: thc.ir 
performance is highly deternfined by their inputs. 
All of these algorithms will perform at their best 
when their dependent disjunctions interact as lit- 
tle as possible, but if all of the disjunctions inter- 
act, then these algorithms may perform redundant 
computations. The need for ef\[icient inputs has 
been noted in the literature 2 but there have been 
few attempts to automatically optilnize gr;mnnars 
tor disjunetiw; unification algorithms. 
The modularization algorithm presented in this 
paper takes existing dependent disjunctions and 
splits them into independent groups by deterlnin- 
ing which disjunctions really interact. Indel}en- 
dent groups of disjunctions can be processed sepa- 
rat;ely during unification rathe, r than having to try 
every combination of one group with every com- 
bination of every other group. 
This pat)er is organized as follows: Section 2 
gives an informal introduction to dependent dis- 
~Cf. (Maxwell and Kaplan, \]991) fl)r instance. 
448 
juncl;ions and shows how r(,ctundani; int(;raclli(lns 
lml,w(;en groups of (tisju:n(:l;ions (:mi bc r(;du(:ed. 
S(;c:i;ion 3 shows how normal disjunctions c;m t)(; 
r(;l)lac(;d t)y (:ont, cxtx;d constrainl:s. S(,(:tion 4 t;hcn 
,<d~ows how t, hcs('~ cont(;xl;(',d (',onstraints can en- 
cod(, del)(',nd(;ni, disjunctions. S(!(:l;ion 5 1)r(!s(',nts 
the mo(hllm'ization a,lgorii;hm for conlx~xi;ed (',on-. 
si;ra.ini;s. Ih)wever, e, ven though this algor{l;hm is 
t~ (;omt)ih>t,im(', ot)(;ralJ(m , it itself has (;xt)on(nitial 
comt)lexity, so lilil, l(ing it IllOl(', (~tli(',i(mi; should ~Jso 
1)(; a (:onc:(,rn. A i;h(~or(;m will l,hc, Ii \])(; i)r(~s(mix;d 
ill S('x'J;iOll (i t\]mL t)(!rllli(;s ;I, li (',xt)olt(!tll;ial t)&rt; ()\[ 
i,tl(; nm(hllarizal;ion algo\]'il,hm I;()I)c rct)l;t(:(',(l 1 W 
combinatorial aam.lysis. 
2 Dependent disjunctions 
l)(:l)enchull; disjuncl;ions are lik(' \]u)\]mai dis.iun(:-- 
dons cxc',c;1)t dial; (;very (lis.iun(:l;ion has a nanL(', 
mid l;h(; disjuncts of disjuimti(ms wii;h tim sam(: 
IlllIll(~ IllltSt; |)(; ch()s(~ll ill SyllC. FoF (~xmnt)l('. , 
(<, g,, d/, (//') A (<t ',?, ~/)', ~//') is a (:,,ni.n,:i:io,~ ,)r i:wo 
dcl)cn(hmt disjml(:dons with tim s.~/lil(; lt~l,l\[l(,., (/. 
Wtl;l,l; this m('.;ms ix llha.l; if l,h(', s(;('oml (lisjun(:l: in 
1;ho, til'sl; (tis.iul~(:tion, (//, ix (:hoscn, lJicn l;h(~ s(!(> 
ond dis.jun(:t, of th(; ()th(;r disjun(:llion, '~//, Inllsl; 
t)(; chos(m as well. (Not(; thai; wilful; kind (if con- 
sLrainl;s the ¢/)s a.n(I 'l/~s are ix not iml)ortmfl; here.) 
'Fh(', (',oIlll)lll;&/;iOll&l l'e;/,soll \[()1 llSill{,; (h~t)(,,u(hml; 
(lis.iun('.i;ions ovc, r norma,\] (tisjunc'.tions ix t;hal; (h> 
l)(;n(lcnl; disjun(:dons Mlow for more (:Oral)a(;1, a.nd 
(dlici(;nl; sl;tllCi;/ll(~.s. 'Fhis is l)mdcularly lain(; whcli 
(h;1)cn(l(;nl; (lisjunc:l;ious arc (',lnl)(!d(hxt iusi(h; of 
\[ea,l, urc sl;rutJl;llr(;s. This is \[let',raise in l;li;tl, c.aso 
(lisjlln(:l;i(ins C}l,ll lic kept hi('a,l ill it dirc;(:l;('d gl'ltlih 
Sl,\]'llCI;lll'(1 t;hllS s:4Villl r l:(xhut(la.nl; \['(;;tl;ure I);~l;lis. 
Wc slty I;tiaA; disjuncl;ions with l;\]i(; sani(; name', 
arc in l;h(; sa,mc g'ro'u,p. Oltc (lisl;inguishing fea- 
1;llr(~ of a, group of (lisjun('dons ix i;tl&l; (;~(;}1 dis- 
jun(;t;ion lnusi; ha, v(~ tim stun(', numl)(',r of dis- 
junclis. This is (;sscntially who!re! r(xlun(lalit int, cr- 
a(',l;ions origina, l;(',, l"or inslia,lL(m~ in (<l (l)> (lJ, (I/, qi)') A 
(,1 '~1~, '~//, '~/~, '~//) (;ac:h disjun(:ti()n has four (tisjun(',ts, 
\[)111; r(;ally Oll\]y l;WO values. Bul; 111()I'( ~, iml)O\]'- 
l;;~.nl;ly, no nla.l;l;(;r whal; wahl(,, of l,h0 lirsl; (lisjun(> 
lion ix (:hos(m ((/) or ell) t;hc; sallle v~-I, lll(~S a,l(; t)(3s-. 
sibh; for i;h(*, s(;(',on(1 (9 or 'l//). hi ol;hcr words, 
thos(' disjunctions at(; a(:tually ind(;p(mdcnt from 
one; anol;hcr, and Can t)0, put into (lifl'er(',nl; groups: 
(d' +, ¢') A (d" "/2, +'). This is th(: In OC(;Ss ,)t ,nod- 
ulmiz~tl;ion which will b(; forina,lized in s(;c;l;ion 5. 
One mi<ghl; t)c l;(mll)tc(l to l;hink thal; ul()(lulm'- 
izg-t,|;ion ix llllnCCCSS~l,l'y siIl(;(~ ~I'3,IlIIlI}LI wril;(;rs ~-/,1"(~ 
unlikely to writ('. (h;t)endc;nt; disjunctions which 
(',ontain iild(~,l)cm(tcn(; parts. Ih:)w('v(~r, gramma, r 
writers m;~y not b(; (;hi; only sotlr(;(! o\[ (\[(;\[)(;n(l(;ifl, 
disjunc:tions. Mmiy grajmnar l)ro(:(;ssing sysi;(;ms 
use high-level dose:tit)lions whic:h arc I;hcn trans- 
form(;d into lttOr(; cxt)lic:il; \[ow(~l'-hw(;1 grmmnars. 
This trimsJbrmatioIl proc:c;ss may very w('.ll in- 
l;rodu(;(; large' :tlllllll)(;l',<-; of dc;t)en(h;nl; disjunctions 
with (;×a(:l,ly this t)rol)(;rl,y. 
()IIC ('×alnt)l(~ of who;r(; this can ha,l)l)(;n is in 
the; ('xmipilm;ion o1' h;xi(:a,1 ruh',s in (Mcmr('rs and 
Mimmn, 1995). In this t)apc!r, M(mr(ns mM Min 
n(;n (t('s(:rib(~ a (:omt)ih, whic:h f, rmml~m;s a. s(,t of 
LIPS(; h;xi(:al ruh;s aim th(;ir int(;ra, l:d()n into (h;l- 
init;e r(Jations usc,d 1,o constrain h'xical (~niai(~s. 
In (Mem(us and Mimmn, 199(i), th('y show how 
nn oil'-lin(; COml)ila, tion te(:hniqu(; (:a,lh~d constraint 
l)roi)a,gation can I)e us(;d to inll)rov(; tim (leNnit(~ 
c:la,us(' (;nc:()cting produ(:(;d 1)y l;heir (:Oml)ih, t() a,1- 
h)w for m()r(~ (dti(:i(~nl; t)ro(:('ssing. Tim use o\[ (h' 
iron(hint disjunctions t)rovid(,.s ml a.l;tr;~(:dv(~ ~dLer- 
\]mlJv(~ 1;o I;tm (:olisl,rainl, t)\]op;~gal;ion ~q)l)roa(:h 1) 3, 
st)(;('.ifying all t;h(; information associ;~lxxl with a 
h'xi(:al (;nl,ry dir(;c:dy as a singh', (h't)(;nd(;nl; f(!m 
l;llre sI;r/I(:LIII'(; r&l;h(;r th;tn hidd(m in a set; of (h~ti- 
nii;e (:la.us(;s. :~ C'onsidc.r the AheM lmh)w: 
PIt()N ~ ll,d ...... lielnu,, lleht, li,d,I } 
i. d 
VI,'()I(M { I)se, hse, fin I lilt} 
d 
.% Ull.I \[-/ I 
{ ~ vn,'()aM ~,.,,, 
'lichen 
L au(~ I '" I I 
\[VI,'()ILM hsE( \[ 11 
\[ VI,'()I{M I!he\] } i,.\]J > 
)' ( \[(X)N'r )' ( ) 
This comph'.x lexicM entry relsrcs(;nl;s the ha.so lex 
ical enlay fl)r t;ll('. Gcrnmn verb lichen, "to love", 
mM tim t;hree lcxical c!ntrics l;haA; (:all 1)0. derived 
from il; given th(! lcxi(:~d ruh;s prcsc;nl;c,xl in (Me.ur- 
ers and Mimmn, \]99(i). Tho difl'(;renc:es tml,wc'x;n 
i;hese h~xi(:M (miaic;s arc (,nc:oded 1)y th(; (h~pc',nch;nl; 
disjunctions all o1" which a,rc in th(~ .~mnc gr(ml), 
d. The first (\[i~}llll(;l; ill c&ch (tisjun(;l,ioll (:()rr(~- 
Sill)nits to l;tm b;ts(; t'Olln~ (;hi; S(;(;()II(I (:orr('st)c)n(ls 
to the al)pli(:~l;ion of l;lm Compl('mc;nt F, xtracl;ic)u 
l,exicM lhtl(;, the third corrc'sl)onds to the al)pli- 
cation of the Finitivization L(;xical ltuh;, mid I;he 
last COrlTo, s1)oIl(ls l;o Lhe apt)lication of t)ol;h rltles. '1 
Modulariz~tion can l)e ilSc.(l t;o ilclak(; this t'('~tur(~ 
sl;ructur(; (wen more (dlichuit by st)litl;ing all(; gro/ip 
d into two new gt'()llpS dl a, nd (12 as showu lmlow. 
aln I;he case of infinite h;xica, detinitc clauses arc. 
still necc.ss;try to encode recursive informal;ion. 
4q'ht',se lexical rules air(! simplitied versions of those 
presented in (Polb~rd ~md Sag, \]994). 
449 
PIION ~ lleben, liebt / 
\[dl 
VFORM ~ bse, fill} 
I, el 
SUBJ \[\] 
f rVFORM bse\] \] ) 
\[lieben -\] 
\[AaG~ 2t!\]\] 
{ rv,,'OaMbsol } 
s,,,,s,, 
d2 
Another example of where modularization 
might prove useful is in the treatment of typed 
feature structures presented in (Gerdemann and 
King, 1994). Their approach produces a set of 
feature structures from a satisfiability algorithm 
such that all of the feature structures have the 
same shape but the nodes may be labeled by dif- 
ferent types. They then collapse this set down to 
a single feature structure where nodes are labeled 
with dependent disjunctions of types. Many of the 
groups of disjunctions in their feature structures 
can be made more efficient via modularization. 
A final example is in the compaction algo- 
rithm for feature structures, presented in (Grigith, 
1995). Compaction is another operation designed 
to optimize feature structures for unification. It 
takes a disjunction of feature structures, trans- 
forms them into a single feature structure with 
dependent disjunctions, and then pushes the dis- 
junctions down in the structure as far as possible. 
The result is a large number of dependent dis- 
junctions in the same group. Many of these can 
probably be split into new independent groups. 
3 Contexted constraints 
Maxwell and Kaplan (1989) showed how a dis- 
junction of constraints could be replaced by 
an equi-satisfiable conjunction of contexted con- 
straints as in lemma 1 below. 5 
Lemma 1 (Contexted Constraints) 
¢1 V ¢2 is satisfialtle if\] (t) -+ ¢1) A (~ --4 ¢2) is 
satisfiable, where p is a new propositional variable. 
Disjunctions are replaced by conjunctions of im- plications 
from contexts (propositional formulae) 
to the base constraints fie. ¢:t and ¢2)- The na- 
ture of the base constraints is irrelevant as long 
as there is a satisfaction algorithm for them. The 
key insight is that solving disjunctions of the base 
constraints is no longer necessary since they are 
purely conjunctive. 
SFor a proof see (Maxwell and Kaplan, 1989). 
Maxwell and Kaplan's goal in doing this was 
to have an efficient method for solving disjunctive 
constraints. The goal in this paper is compilin.q 
disjunctive constraints into more efficient ones for 
fllture solution. To this end a somewhat different 
notion of contexted constraint will be used as show 
in lemma 2. 
Lemma 2 (Alternative-Case Form) 
(/)1 V ¢2 is satisfiable iff (al -4- ¢\]) A (a2 ~- ¢:~) A 
(al V a2) is satisfiable, where al and a2 arc new 
propositional variables. 
We (:an see that this formulation is nearly equiva- 
lent to Maxwell and Kaplan's by substituting p 
for at and p for a2. To make the formulation 
completely equivalent;, we would need to enforce 
the uniqueness of a solution by conjoining al V g2. 
However, this is unnecessary since we want to per- 
mit both solutions to be simultaneously true. The 
reason for using the modified version of contexted 
constraints in lemma 2 is that we can separate the 
representation of disjunctions into a conjunction 
of the values that the disjuncts can have, called 
the alternatives, and the way in which the we can 
choose the values, called the cases. The alterna- 
tives are the conjunction (al -~ ¢1) A (a2 -+ (/52) 
and the cases are the disjunction (al V a2). 
While we could use repeated applications of 
lemma 2 to turn a disjunction of n disjuncts into 
an alternative-case form, it will simplify the expo- 
sition to have a more general way of doing this, as 
shown in lemma 3. 
v----I~l~)ma 3 (N-ary Aiternative-CaseA (ai -~ ¢i) A vFarm)ai 
ieN is satisfiable iff icN icN iS 
satisfiable, where each ai is a new propositional 
variablA°(ai--~ ¢i) V a{ 
Itere iGN are the alternatives and icN 
are the cases. So for example, ¢1 V ¢2 V Ca V ¢4 
is satisfiable just in case (at -~ ¢1) A (a2 -+ ¢2) A 
(a3 ~+ q~3) A (a4 -~ (~4) A (a:, V a2 V a3 V a4) is 
satisfiable. 
4 Dependent disjunctions as 
contexted constraints 
The usefulness of the alternative-case form only 
becomes apparent when considering dependent 
disjunctions. Dependent disjunctions can be rep- 
resented by alternative-cast forms as shown in def- 
inition 1 below. 
Definition 1 (Dependency Group) 
A dependency group is a conjunction of dependent 
disjunctions with the same name, d, where each 
V* A*, 
6ieN and ieN are disjunctions and conjunctions 
of formulae ¢i, respectively, where each i is a member 
of the set of indices, N. 
450 
disjunction is an alternative-case form such that 
there is one alternative for every disjunct of ev- 
ery disjunction in the group, and there is one case 
for each disjunct in the group which is a co*one- 
tion of the alternative variables for that disjunct 
<.M A A(a}-~¢}) V A a} 
: i6Mj6N AJ6NiC-M 
where each a} is a new propositional variable and 
N = {L<...,n}. 
So l;he dependent disjunction (,l ¢,0,¢') A 
(d ¢,'~//, 0'} is the alternative-case form with al- 
ternatives (a I -+ 0) A (a~ -~ 0) A (a:~ -+ 4/) A 
(,4 -" ¢) A ¢') A "/") and eases 
((a I Aa~) V (a~ Aa~) V (a~ A<)). The cases enforce 
that the corresponding disjuncts of every disjunet 
in the group inust be simultaneously satisfiable. 
We, can now start to see where redundancy in 
dependent disjmmtions originates. Because, every 
disjunction in a group of (lepen(le, nt disjunctions 
nmst have the, same nund)er of disjuncts, some, of 
those disjunets may appear more, than once. In 
the above exmnple t:br instance, 5 occurs twice in 
the first disjunction and ~// occurs twi(:e in the 
second disjunction. To resolve this problem we 
impose the following condition, called alternative 
compactness: if a base constraint ¢} equals an- 
other base constraint from the same disjunction, 
¢\[,, then the alternatives variables associated with 
those base constraints, (,ji and a~, are also equal. 7 
Doing this allows us to express the alternatives 
t;'om the example above as (d -~ ¢) A (4 -~ 
¢') A (~ --~ ¢) a (a~ ~ ¢'), an(1 the case,~ as 
((at: A a~t) V (all A (t 2) V (8,12 A a2)).8 One advall- 
tage of this is that the number of base constraints 
that must be checked during satisfaction (:an po- 
tentially be exponentially reduced. 
'File nexl; section will show how an alt;ernative- 
case form for a, group of det)tndent disjuncl;ions 
can be split into a conjunction of two (or more) 
equivalent forms, thereby (potentially) exponen- 
tially reducing the munbtr of alternative varial)le 
interactions that must be checked during satisfac- 
l;ion, 
5 Modularization 
Consider again tile example from section 2: 
(d (/5, (I), ¢', (/)') A (d 0, "~t/, ~1~, %/)'). i{epresented as a 
compact alternative-case form, the alternatives 
becomes: (al 0)A((4 ¢')A(d 
',//), with cases: ((a I A a~) V (al A a~) V (a.~ A 
a~) V (a 1 A a~)). The key to determining that 
the two disjunctions (:all be split into different 
rNote that this requires being able to determine 
equality of the base constraints. 
Sin this example, equivalent alternative variables 
have been replaced by representatives of theirequiva- 
lence chess. So a~ has been replaced by al and a?a has 
been replaced by a.~. 
groups then involves determining that cases can 
be split into a conjunction of two smaller cases 
(a', V a~) A (a~ V a~). If the cases can be split in 
this manner, we say the cases (and by extension 
tilt group of dependent disjunctions) are indepen- 
dent. 
Definition 2 (Independence) 
A case \]orrn is independent iff it is equivalent to 
"j~{N i6M ~ j(iN' i6M' A jcN" i6M" 
where M' and M" partition M. 
So in the above examph',, M = {1,2} where 1 rep- 
r(!sents l;he first disjunel;ion and 2 represents l;he 
second. That makes M' = {1} and M" = {2}. 
While M' and M" are derived Dora M, the ele- 
aleuts of the Ns are arbitrary. But a consequence 
of definil;ion 2 is that \[N\[ =- IN'\[ x \[N"\[. This 
will be proved in section 6. The size of the Ns, 
however, represent the nmnber of cases. So for 
instance in the above example, N might equal 
{1,2,3,4} since there are four disjuncts in the 
original ease form, while N' might equal {1,2} 
and N", {1,2}, since the smaller case forms each 
contain two disjuncts. 
The process of splitting a group of dependent 
disjunctions into smallel" groups is called modu- 
larization. Modularizing a group of dependent 
disjunctions amounts to finding a conjunction of 
ease forms that in equivalent; to the original ease 
form. The modularization algorithm consists of 
two main steps. Tile first is to take the original 
case form and to construct a pair of possibly in- 
dep(mdent ease forms from it:. The second step is 
to check if these (:as(', forms are actually indepen- 
(lent from each other with respect to the original 
one. The modularizatioil algorithm performs both 
of these steps repeatedly until either a pmr of in- 
depe, ndent ease R)rms is found or until all possi- 
ble pMrs have been checked. If tile later, then we 
know that; the original dependent disjunction in al- 
ready nn)(lulai'. If on the ottmr hand we can split 
the case forms into a pair of smaller, independent 
(;as(; forlns, then we can again try to modularize 
each of those, until all groups are modular. 
'\[b const;ruct a pair of potentially independent 
(:as(; forms, we first need to partition the set of 
alternative vm'iablts from the original ca,qe form 
into two sets. The first, subset contains all of and 
only the, variables corresponding to some subset 
of the original disjunctions and tile second subset 
of variables is the complement of the first, corre- 
sponding to all of and only the other disjunctions. 
lh'om these subsets of variables, we construct two 
new cast forms Dora the original using the opera- 
tion of confinement, defined below. 
Definitjop, A 3 (ConfineInent) 
V /\ a~ 
COII,f (jc N iE M , J~/It) 
451 
V Aa; 
is the confinement of J CN iGM with respect to a 
4 V k a; 
iff co~tf(J CN i<M , M') =- dnf(J CN i~M' ), 
where. M' C M. 
Constructing the eontinement of a (:as(; form is 
essentially just throwing out all of the alternative 
variables that are not in M'. However, only doing 
this might leave us with duplicate disjuncts, so 
converting the result to DNF removes any such 
duplicates. 
To make the definition of confinement clearer, 
consider tile following conjunction of dependent 
disjunctions: 
(d ¢, 0, ¢, (/), ¢', ~//) A (d ~/% ~//, t/,, ,//, ~/o, t//)A 
((~ x, x, x', x', x', x'}. 
This is equivalent to tile compact alternative 
forIn: 9 
(a~ -', ¢') A (a~ --~ x) A (d + x'), 
and tile following case fornl: ease. = 
((el A a~/, ,*9 v (al A ~4 A a'0, V (4 A .,2 A d)v 
(4 A a~ A d) v (4 A (q A ai~) V ((4 A a~ A d))' 
Now we can compute the confinements. For in- 
stance 1 
eonf(case, {1, 2}) = dnf((a I A a~) V (a I A a,~)V 
(al A (q) v (o' A a,9 v ((4 A d) v (4 A d)) ,\] 
After removing duplicates we get: .,,¢((,ase, 
{~, 2}) - 
((4 A ab V (o * A "9 V (4 A a~) V (4 A a,9) '1 
Likewise, for the c()mtflement of M' with respect 
to M, we get: 
conf(case, {3}) : ((a a) V (ai~)). 
Now we just need to test whether two confined 
case ibrms are independent with respect to the 
original. This is done with the free combination 
operation, shown in definition 4. 
Definition 4 (\]~¥ee Combination ®) 
The free combination of two ease forms is the dis- 
junctive 'normal form of their conjunction: 
case' ® case" -- dnf(case' A case") 
The two ease forms, case' and case", are I)NF for- 
mulct. ~ib compute the free combination, we con- 
join them and convert the re.suit back into DNF. 
They are independence if their free combination 
is equal to the original ease tbrm, case. 
For example, the flee combination of the two 
confinements from above, 
((a I A a, 2) V (a*, a a,~) V (a~ A a~) V (a~ A a~)) and 
((d) v 0,9) 
is 
(ra' A a~ A 4) V (el A 4 A 4) V (a I/, a~ A d)V \ \] 
(4 A a.~ A 4*) v (4 A ,q A d) v (4 A a~/, d)V 
(a~ A d A d) v (a~ A a~ A d)) 
9in this examl)le , equivalent alternative variables 
have again been replaced by representat, ives of their 
equivalence class. So tbr instance., a~, c*~ and a~ are 
all represented by al. 
which is not equM t;o the original (:as(.' form: 
((el A a~ A a~) V (a', A ,~,~ A 4') V (4 A d A ,,i\])v 
(al A a~ A all) v (d A a~ A d) v 04 A d A a q)), 
so tim first two disjunctions are not indet)en- 
dent from the third. However, the second dis- 
jmmtion is independe.nt front the first and the 
third since, conf(case, {2}) - ((a~) V (a.~)), anti 
co,¢(ca.~e, {1, 3}) (q,' '~ ' ~ ' " : t ,Aa',)V(%Aai,)V(asAa!i)) , 
and their free combination is equal to the oi'igi- 
nal case form. Therefore, the original formula is 
equivalent to (d' ~/a,*//)A (d,, ¢, ¢, ¢')A(d,, X, X', Z'). 
6 Free combination elimination 
The last section showed all efl'ective algoritlnn for 
modularizing groups of dependent disjunet;iolls. 
However, even dlough this is a compile time al- 
gorithm we should be con(:erned about its eflio 
ciency since it has ext)onential comph;xity. The 
main source of complexity is that we inight have to 
check (;very pair of sul)sets of disjun(:tions fl'oin the 
group. Ill the worst case this is tnmvoidable (el o 
though we do not expect natural language grain- 
mars to exhibit such behavior). Other sources of 
comi)lexity are computing the fl'ee coinbinadon 
and testing the result against the original (:as(; 
form. l,uckily it is possible to avoid both of these 
operations. This Ceil t)e done by noting that both 
the original (:ase form aim each of the (:onfine{t 
(:as(; forms are in DNF. Therefore it; is a nee-. 
essary (:ondition t}tat if l;he fl'ee combination of 
the confinements is the same as the original case 
form then the I)roduet of tile number of disjun('ts 
i,, ea(:h conflneme.t, lease'l x lease"l, re,st eq,lal 
the number of disjun(:ts in the original case form, lease I. 
Moreover, since both confinements at(; de- 
rived fl'om the original ease form, it is also a suf 
ficient, condition. This is shown more forlnally in 
theorem 1. 
Theorem 1 (l~Yee combination elimination) 
~.',~se = ~:as,/Oease" ¢=> \]case\] = ba~e'l × Icase"l 
Proof =:> We assulne that case'®case" =- case. 
Since hoth case'® eas#' and ease are in DNF and 
DNI; is unique, we know that \](:as('.' ® case"\] =: 
lease\]. We also know that case' and case" have 
no disjunets in common because they have no al- 
ternative variables in colnmon, so Icasc'®case"l = 
Icase'l x Icasc."l. Therefore. le~s4 = Icasc'l x 
kase"\]. U 
Proof <-- Again since case' arm case" have 
no disjuncts in cormnon, we know that leas# @ 
case"\] = \]case'\] x Icase"\] and therefore, that 
lease I -- lease'®co, st"\]. Every disjunct in case can 
be represented as A' A A" where A' is a disjnnet 
in case' and A" is a disjun(:t ill case". So the dis- 
.iunets in ease'@ case" must be every conjunction 
of possible A's and A"s. So case' ® case" must 
452 
c<mtain all (>f th<', <li@mcts in ca.sc mM it. could 
contain ev<m m<)re, }),it f,h<m + > 
case ~ ~ case" must (:ontain cxacl;ly the disjuncl;s 
ill cas(: aIld l;hcrcforc (:as( t :: (:o,,~('J (29 (:(ts(:'. E\] 
We can see that this would have hell>ed us in th('. 
p,'cvi<,us <`-x~t~,,p> t;<)k~,<,w m~t. <:<,,,/(,,<,,.~(,, {1,2}) 
(:(}lll(l 110|; |)('~ il,(|(,t)(!II(l(!llJ; \['1'()1\[1 C()ILf(c(t,'~C,{3}) 
wit;h respect to c<,,,sc, t>eca.use ):,,(f(ca,sc, {1,2 })! 
8. ()onvcrscly, sin(:(`- Ico'/~f(ca.s'c, {\[,3}) I 3 and 
\[conf(casc, {2})1 : 2, we, know imm(,Jia.l;ely l;hat 
l;hcs('~ (:as(', forms are in(h`-t)c'nd(mt. 
This the, orem also allows us to trotform other 
comt)inat, orial short cuts, su<'h as noting that if 
t;he nunltmr of disjuncl;s in the origimtl case torm 
is prime \[;hen it; is already modular. 
7 Conclusion 
'\['his paper has \[)r('~s<!nt(xl an (fllici(mt form for 
r(',l)r(;s(ml;ing (lc, p(!ll(h;nl, dis,jun(:t;i(>ns m~(i an algo- 
rithm for d(`-I;(x;l,ing aim (;liminal;ing r(,,dmt(tmit in: 
teractions within a group of <\[(~l)(m(hmt disjmm- 
l;i<ms. This mc, l;h<)<l shoul<l be useful for a.,y sys- 
(;era which (mq)l<)ys <let)endent <lisjun(:tions sin<:e, 
it, can (`-liminai;e exponenl;ial am(mnt;s of i)ro<:(~ssh~g 
during (:onstra.inl; sadsi\]mtion. 
In Conslraint I'ropagatio'n , Linguistic Dcsc~ip- 
tion, a'nd Computation, \[stituto l)alh', Molle II)- 
SIA, Lugano, Switzerlan<t. 
Meurers, i). and G. Minnen. 1995. A @olni)u- 
t;al;ional Trcat;nmnt; of \[ll'S(l I,exi<:al l{ules as 
Covm'ial;ion in Lexi(:al l,;ntries. In l)r'oc, of I,h,<: 
5th, Int. Workshop o'n Nal,'wrrd Lang'uo,9<~ U'ndcr- 
standing a, nd Logic l~r'og'ra'mming. 
M<mr(!rs, 1). ml(I G. Mimmn. 199(i. ()It'-liue Con- 
sl,ra.inl; I)r<)l)agat;ion for l,;\[li('i(`-zzI, III'S(I I)I'O(;(~SS - 
ing. h\[ l'roc, of III'S(I/TAI,N-06. 
I>ollm'd, C. mid i\[. Sag. :1994. Hcad-drivc.n Phra,sc 
Struct'u, rc G'rummar. U. (>t! Chi(:ago Press. 
StrSml)~i(:k, L. 1992. Uni\[~ging Disjun(:l;ive l"eal;ur(; 
Sl;ru<:i;ures. \[n COl,IN(', \[992, 1)a.ges 1:167 11171. 
References 
Eiseh`-, A. and J. D6rre. 1990. Unification of 
Disjunctiv<`- Feature De, s(:ril)tions IBM Wis- 
sens<:haftli<:hcs Zcntrnm, \[nstitul;(', fiir Wiss(`-ns: 
basi(;rt<: ,qysl;t'.In<`- l;(`-(;h, l'Cl)<>r\[; \] 2+l. 
(;(;r<lemann, I). 1991. Parsing and Genc'ration 
of Unification Cramma'rs, PM) thesis, U. (>f 
Illinois. 
(~el'<lemaml, D. and 1). King 1.(t94. The ()or- 
re<:/; an<l Eilh:ient; hnt)lemealt:ation of Apl>rot>ri- 
a.teness Specifications for Typed Feature Struc- 
tures In COLING 1994, pages 956 960. 
Griflith, J. 1995. Optimizing Fcat;nre St;ru<:turc 
Uniticat, ion widt l)ependent l)isjuncl;ions, in 
l'apcrs presented al, th.c W(rrkshop on (h'am- 
ma,'r li'ormaliwm, fl)r NLP at E,qAT, LI:-9/I. U. 
Tiibinge.n, S('minm' fiir Stn'achwisse, nscha.fl; tech. 
rel)ort 04415. 
Gritlith, J. 1996. Disjur~,ction and EJ\]icic'n,t P'lv- 
tossing of Feature Struct'u,'rcs. 1)hi) th(!sis, Uni- 
versitSt T/ibingen. Tentative tide. 
Maxwell, J. and I{.. Kat)lan. 1.(t89. An Overview of 
l)i%iuncl;iw'. C<mstraint Sadsfact;ion. In \]"me. of 
lnl. Workshop on 1)a'rsi'n,g Technologies , pages 
18 27. 
Ma.xw<`-ll, 3. and 1{. Kaplan. 1991. Th(! lnt('xfa(:(! 
1)(!l;w(',(m Phrasal mt<l Funct;ional Consl;ra, ints. 
453 
