Disjunctions and Inheritance 
in the Context Feature Structure System 
Martin BSttcher 
GMD-IPSI 
Dolivostra~e 15 
D 6100 Darmstadt 
Germany 
boettche~darmstadt.gmd.de 
Abstract 
Substantial efforts have been made in or- 
der to cope with disjunctions in constraint 
based grammar formalisms (e.g. \[Kasper, 
1987; Maxwell and Kaplan, 1991; DSrre and 
Eisele, 1990\].). This paper describes the 
roles of disjunctions and inheritance in the 
use of feature structures and their formal 
semantics. With the notion of contexts we 
abstract from the graph structure of feature 
structures and properly define the search 
space of alternatives. The graph unifica- 
tion algorithm precomputes nogood combi- 
nations, and a specialized search procedure 
which we propose here uses them as a con- 
trolling factor in order to delay decisions as 
long as there is no logical necessity for de- 
ciding. 
1 Introduction 
The Context Feature Structure System (CFS) 
\[BSttcher and KSnyves-Tdth, 1992\] is a unification 
based system which evaluates feature structures with 
distributed disjunctions and dynamically definable 
types for structure inheritance. CFS is currently 
used to develop and to test a dependency grammar 
for German in the text analysis project KONTEXT. 
In this paper disjunctions and inheritance will be in- 
vestigated with regard to both, their application di- 
mension and their efficient computational treatment. 
The unification algorithm of CFS and the con- 
cept of virtual agreements for structure sharing has 
been introduced in \[BSttcher and KSnyves-TSth, 
1992\]. The algorithm handles structure inheritance 
by structure sharing and constraint sharing which 
avoids copying of path structures and constraints 
completely. Disjunctions are evaluated concurrently 
without backtracking and without combinatoric mul- 
tiplication of the path structure. For that purpose 
the path structure is separated from the structure of 
disjunctions by the introduction of contexts. 
Contexts are one of the key concepts for main- 
taining disjunctions in feature terms. They describe 
readings of disjunctive feature structures. We define 
them slightly different from the definitions in \[DSrre 
and Eisele, 1990\] and \[Backofen et ai., 1991\], with a 
technical granularity which is more appropriate for 
their efficient treatment. The CFS unification algo- 
rithm computes a set of nogood contexts for all con- 
flicts which occur during unification of structures. 
An algorithm for contexts which computes from a 
set of nogoods whether a structure is valid, will be 
described in this paper. It is a specialized search 
procedure which avoids the investigation of the full 
search space of contexts by clustering disjunctions. 
We start with some examples how disjunctions and 
inheritance are used in the CFS environment. Then 
contexts are formally defined on the basis of the se- 
mantics of CFS feature structures. Finally the algo- 
rithm computing validity of contexts is outlined. 
2 The Use of Disjunctions and 
Inheritance 
Disjunctions 
Disjunctions are used to express ambiguity and ca- 
pability. A first example is provided by the lexicon 
entry for German die (the, that, ...) in Figure 1. It 
may be nominative or accusative, and if it is singular 
the gender has to be feminine. 
Those parts of the term which are not inside a dis- 
junction are required in any case. Such parts shall be 
shared by all "readings" of the term. The internal 
54 
die := L_definit-or-relativ@ <> 
graph : die (nom} 
Cas " acc 
syil : categ : ( Ilum : pl t 
num : sg 
gen : fern \]} 
Figure 1: Lexicon Entry for die 
representation shall provide for mechanisms which 
prevent from multiplication of independent disjunc- 
tions (into dnf). 
tr&ns :.~-~ trails : • dom : syn : categ : gvb : aktiv 
{ I \[categ \[class :nomn\]ssentj 
syn : categ : \[cas : acc j 
\[lexem : hypo' \] syil : : class : 
\[prn none 
<tree-filler> = <role-filler trails> 
" . \[ gvb : passiv \] dom:syn: ca~eg: Lrel #1 J 
. \[ class : prpo \] categ : rel • #1 
syn: \[ " \] 
lexem : {~::ch } 
<tree-filler> = <role-filler agens> 
• v-verb-trails-slote<> 
Figure 2: The Type trans 
As a second example Figure 2 shows a type de- 
scribing possible realizations of a transitive object. 
The outermost disjunction distinguishes whether the 
dominating predicate is in active or in passive voice. 
For active predicates either a noun (syn : categ : 
class : nomn)or a subsentence (syn : categ : class : 
ssent) is allowed• This way disjunctions describe 
and restrict the possibility of combinations of con- 
stituents• 
External Treatment of Disjunctions 
The KONTEXT grammar is a lexicalized gram- 
mar. This means that the possibility of combinations 
of constituents is described with the entries in the 
lexicon rather than in a separated, general grammar. 
A chart parser is used in order to decide which con- 
stituents to combine and maintain the combinations• 
This means that some of the disjunctions concerning 
concrete combinations are handled not by the unifi- 
cation formalism, but by the chart• Therefore struc- 
ture sharing for inheritance which is extensively used 
by the parser is even more important. 
Inheritance 
Inheritance is used for two purposes: abstraction in 
the lexicon and non-destructive combination of chart 
entries• Figure 3 together with the type trans of Fig- 
ure 2 shows an example of abstraction: The feature 
structure of trans is inherited (marked by $<>) to 
the structure for the lexeme spielen (to play) at the 
destination of the path syn : slots :. A virtual copy 
of the type structure is inserted• The type trans will 
be inherited to all the verbs which allow (or require) 
a transitive object. It is obvious that it makes sense 
not only to inherit the structure to all the verbs on 
the level of grammar description but also to share 
the structure in the internal representation, without 
copying it. 
L_spielen := 
lexem : spielen 
. \[ fie_verb : schwach syn : ca~eg : \[ pfk : habeil 
slots : trans@<> 
v-verbt~<> 
Figure 3: Lexicon Entry for spielen 
Inheritance is also extensively used by the parser. 
It works bottom-up and has to try different combi- 
nations of constituents. For single words it just looks 
up the structures in the lexicon. Then it combines a 
slot of a functor with a filler. An example is given in 
Figure 4 which shows a trace of the chart for the sen- 
tence Kinder spielen eine Rolle im Theater. (Chil- 
dren play a part in the theatre.) In the 6'th block, in 
the line starting with ... 4 the parser combines type 
_16 (for the lexicon entry of im) with the type _17 
(for Theater) and defines this combination dynami- 
cally as type _18. _16 is the functor, _17 the filler, 
and caspn the name of the slot. The combination is 
done by unification of feature structures by the CFS 
system. 
The point here is that the parser tries to combine 
the result _18 of this step more than once with differ- 
ent other structures, but unification is a destructive 
operation! So, instead of directly unifying the struc- 
tures of say _7 and _18 (_11 and _18, .•.), _7 and 
_18 are inherited into the new structure of _20. This 
way virtual copies of the structures are produced, 
and these are unified• It is essential for efficiency 
that a virtual copy does not mean that the structure 
of the type has to be copied. The lazy copying ap- 
proach (\[Kogure, 1990\], and \[Emele, 1991\] for lazy 
copying in TFS with historical backtracking) copies 
only overlapping parts of the structure. CFS avoids 
even this by structure- and constraint-sharing. 
For common sentences in German, which tend to 
be rather long, a lot of types will be generated• They 
supply only a small part of structure themselves (just 
the path from the functor to the filler and a simple 
slot-filler combination structure). The bulk of the 
55 
i: Kinder 
_I : Kinder open/sat 
2: spielen 
...I _2 : spielen 
_3 : spielen _2 
_4 : spielen _2 
open 
subje Kinder _I open/sat 
trans Kinder _I open 
3: eine 
...2 _S : eine open/sat 
4: Rolle 
...3 _6 : Rolle 
...2 _7 : Rolle _6 
_II: spielen _3 
...1 _14: spielen _2 
open/sat 
refer eine _5 open/sat 
trans Rolle _7 open/sat 
trans Rolle _7 open 
5: im 
...4 _16: im open 
6: Theater 
• ..5 _17: Theater 
...4 _18: im _16 caspnTheater _17 
...3 _19: Rolle _6 caspp im _18 
• ..2 _20: Rolle _7 ¢aspp im _18 
_21: spielen _11 caspp im _18 
...I _22:spielen_14 caspp im_18 
_26: spielen _3 trans Rolle _20 
...I _29: spielen _2 trans Rolle _20 
open/sat 
open/sat 
open/sat 
open/sat 
open/sat 
open 
open/sat 
open 
7: • 
°°.6 _30: open 
_31: • _30 praed spielen _26 sat 
_32: . _30 praed spielen _21 sat 
Figure 4: Chart for Kinder spielen ... 
structure is shared among the lexicon and all the 
different combinations produced by the parser. 
Avoiding Recursive Inheritance 
Recursive inheritance would be a means to com- 
bine phrases in order to analyze (and generate) with- 
out a parser (as in TFS). On the other hand a parser 
is a controlled device which e.g. knows about im- 
portant paths in feature structures describing con- 
stituents, and which can do steps in a certain se- 
quence, while unification in principle is sequence- 
invariant. We think that recursion is not in princi- 
ple impossible in spite of CFS' concurrent treatment 
of disjunctions, but we draw the borderline between 
the parser and the unification formalism such that 
the cases for recursion and iteration are handled by 
the parser. This seems to be more efficient. 
The Connection between Disjunctions and 
Types 
The similarity of the relation between disjunctive 
structure and disjunct and the relation between type 
and instance is, that in a set theoretic semantics (see 
below) the denotation of the former is a superset 
of the denotation of the latter. The difference is 
that a disjunctive structure is invalid, i.e. has the 
empty set as denotation, if each disjunct is invalid. 
A type, however, stays valid even when all its cur- 
rently known instances are invalid. This distinction 
mirrors the uses of the two: inheritance for abstrac- 
tion, disjunctions for complete enumeration of alter- 
natives. When an external system, like the chart of 
the parser, keeps track of the relation between types 
and instances disjunctions might be replaced by in- 
heritance. 
3 Contexts and Inheritance 
This chapter introduces the syntax and semantics of 
CFS feature terms, defines contexts, and investigates 
the relation between type and instance concerning 
the validity of contexts. We want to define contexts 
such that they describe a certain reading of a (dis- 
junctive) term, i.e. chooses a disjunct for some or all 
of the disjunctions. We will define validity of a con- 
text such that the intended reading has a non-empty 
denotation. 
The CFS unification algorithm as described in 
\[BSttcher, KSnyves-TSth 92\] computes a set of in- 
vMid contexts for all unification conflicts, which are 
Mways conflicts between constraints expressed in the 
feature term (or in types). The purpose of the defini- 
tion of contexts is to cover all possible conflicts, and 
to define an appropriate search space for the search 
procedure described in the last part of this paper. 
Therefore our definition of contexts differ from those 
in \[DSrre and Eisele, 1990\] or \[Backofen et al., 1991\]. 
Syntax and Semantics of Feature Terms 
Let A = {a,...} be a set of atoms, F = {f, fi, gi,...} 
a set of feature names, D -- {d,...} a set of disjunc- 
tion names, X = {x, y, z,...} a set of type names, 
I = {i,...} a set of instantiation names. The set 
of terms T - {t, tl,...} is defined by the recursive 
scheme in Figure 5. A sequence of type definitions is 
X := ~1 y := t2 Z := t3 .... 
a atom 
f : t feature value pair 
It1... t,\] unification 
{tl...tn}d disjunction 
<fl.--fn > = <gl..-gm> path equation 
zQ<>i type inheritance 
Figure 5: The Set of Feature Terms T 
The concrete syntax of CFS is richer than this def- 
inition. Variables are allowed to express path equa- 
tions, and types can be unified destructively. Cyclic 
path equations (e.g. <> = <gl. • •gm >) are supported, 
but recursive type definition and negation are not 
supported, yet. 
56 
In order to define contexts we define the set of dis- 
junctions of a term, the disjuncts of a disjunction, 
and deciders as (complete) functions from disjunc- 
tions to disjuncts. Mi is a mapping substituting all 
disjunction names d by i(d), where i is unique for 
each instantiation. 
dis : T ~ 2 D, sub : D ~ 2 N, 
dis(a) := {} 
dis(<p> -- <q>) :- {} 
dis(f : t) :- dis(t) 
dis(x~<>i) := dis(Mi(t))lz := t 
dis(\[tl, ..,tn\]) := U.i dis(tj) 
dis({tl,..,tn}a) := {d} U Uj dis(tj), 
sub(d) := {1, ..., n} 
deciders(t) := 
{choice: dis(t) -o Nlchoice(d) E sub(d)} 
Figure 6 defines the interpretation \[tiC of deciders i 
c w.r.t, terms t as subsets of some universe U (similar 
to \[Smolka, 1988\], without sorts, but with named 
disjunctions and instantiations). 
a I E U, 
yz : g±, yZ(a = ±, = ±, 
\[a\]\]c :={a I } 
If: tic :--{s e Ulfl(s) E It\],} 
\[ It1.. t,\] :=N, \[t \]o 
\[{q..t.}d\]o :=l\[t<d)L 
i<fl..fn > = <gl-..qm>\]e:----{S e Ulf (..ft (s)) = 
gi(..gl(s)) # ±} :={s e := t 
s e 
Figure 6: Decider Interpretation 
Similar to deciders we define specializers as partial 
functions from disjunctions to disjuncts. We also 
define a partial order _t on specializers of a term: 
c1 ~ c~ iff 
Vdedis(t) (c~ is defined on dA c2(d) = j) 
==~ cz(d) = j 
The interpretation function can be extended to 
specializers now: If c is a specializer of t, then 
¢~6deeiders(t)Ae'-g~¢ 
A specializer is valid iff it's denotation is not empty. 
For the most general specializer, the function ca- 
which is undefined on each disjunction, we get the 
interpretation of the term: 
It\] := \[fLy 
Contexts 
Contexts will be objects of computation and repre- 
sentation. They are used in order to record validity 
for distributed disjunctions. We give our definition 
first, and a short discussion afterwards. 
For the purpose of explanation we restrict the syn- 
tax concerning the composition of disjunctions. We 
say that a disjunctive subterm {..-}d oft is outwards 
in t if there is no subterm {.., tj, ..}a, of t with {...}n 
subterm of tj. We require for each disjunctive sub- 
term {...}a oft and each subterm {..,tj, ..}d' oft: if 
{...}d is outwards in t i then each subterm {...}a of t 
is outwards in tj. This relation between d ~ and d we 
define as subdis(d~,j, d). Figure 7 shows the defini- 
tion of contexts. 
A specializer c of t is a context of t, iff 
Vd, d / E dis(t) : 
(e is defined on d ^ snbdis( d', j, d) ) 
=~(e is defined on d ~ ^ e(d ~) = j) 
Figure 7: Definition of Contexts 
The set of contexts and a bottom element ± form 
a lattice (__t, Ct±). The infimum operator of this 
lattice we write as At. We drop the index ~ from 
operators whenever it is clear which term is meant. 
Discussion: E.g. for the term 
f : t" 
t lIt d2 dl 
(dl --~ 2, d2 ~ 1) is a specializer but not a con- 
text. We exclude such specializers which have more 
general specializers (dl --~ 2) with the same deno- 
tation. For the same term (d2 ~ 1) is not a con- 
text. This makes sense due to the fact that there 
is no constraint expressed in the term required in 
(d2 ~ 1), but e.g. a at the destination of f is re- 
quired in (dl --* 1, d2 ~ 1). We will utilize this 
information about the dependency of disjunctions as 
it is expressed in our definition of contexts. 
In order to show what contexts are used for we 
define the relation is required in (requi) of subterms 
and contexts of t by the recursive scheme: 
t requi cT 
f : t ~ requie =~ t' requic 
z~<>i requi e A z := t' :¢, Mi(t/) requi c 
\[..,t I, ..\] requi e ~ t' requi c 
{..,tj,..}d requi c :~ tj requi (d-+ j 
/ 
c(a/)\] 
The contexts in which some subterms of t are re- 
quired, we call input contexts of t. Each value con- 
straint at the destination of a certain path and each 
path equation is required in a certain input context. 
Example: In 
e 
57 
a is required in (dl --+ 1) at the destination of f, 
and e is required in (d2 --+ 2) at the destination of f, 
and the conflict is in the infimum context (dl --* 1) n 
(d~ --, 2) = (dl ---, 1, d2 ---, 2). This way each conflict 
is always in one context, and any context might be a 
context of a conflict. So the contexts are defined with 
the necessary differentiation and without superfluous 
elements. 
We call the contexts of conflicts nogoods. It is not 
a trivial problem to compute the validity of a term 
or a context from the set of nogoods in the general 
case. This will be the topic of the last part (4). 
Instantiation 
If z := t is a type, and x is inherited to some term 
x©<>i then for each context c of z there is a corre- 
sponding context d of z©<>i with the same denota- 
tion. 
\[z©<>i\]c, = \[Mi(t)\]c, = \[tic 
c' : dis(M~(t) ~ N, c'(i(d)) = c(d) 
Therefore each nogood of t also implies that the cor- 
responding context of the instance term z©<>i has 
the empty denotation. It is not necessary to detect 
the conflicts again. The nogoods can be inherited. 
(In fact they have to because CFS will never com- 
pute a conflict twice.) 
If the instance is a larger term, the instance usually 
will be more specific than the type, and there might 
be conflicts between constraints in the type and con- 
straints in the instance. In this case there are valid 
contexts of the type with invalid corresponding con- 
texts of the instance. Furthermore the inheritance 
can occur in the scope of disjunctions of the instance. 
We summarize this by the definition of contezt map- 
ping mi in Figure 8. 
z := t, c E contexts(t) 
t I -- ..x@<>i.., 
zQ<>i is required in d E contezts(t') 
mi : contezts( t ) ~ eontezts( t'), 
( i(d)---* c(d) ) mi(c) := d' --.* c'(d') 
Figure 8: Context Mappings 
4 Computing Validity 
Given a set of nogood contexts, the disjunctions and 
the subdis-relation of a term, the question is whether 
the term is valid, i.e. whether it has a non-empty 
denotation. A nogood context n means that \[t\]n = 
{}. The answer to this question in this section will be 
an algorithm, which in CFS is run after all conflicts 
are computed, because an incremental version of the 
algorithm seems to be more expensive. We start with 
an example in order to show that simple approaches 
are not effective. 
{fi it }, { \[i it }. { \[i 
(dl --, 1, --, 1), (dl 2, 2), 
(d2 --+ 1, d3 --* 1), (d2 --* 2, d3 --* 2), 
(d3 --* 1, dl ---* 1), (d3 "-~ 2, dl --~ 2) 
Figure 9: Term and Nogood Contexts 
For the term in Figure 9 the unification algorithm 
of CFS computes the shown nogoods. The term is 
invalid because each decider's denotation is empty. 
A strategy which looks for similar nogoods and tries 
to replace them by a more general one will fail. This 
example shows that it is necessary at least in some 
cases to look at (a covering of) more specific contexts. 
But before we start to describe an algorithm for 
this purpose we want to explain why the algorithm 
we describe does a little bit more. It computes all 
most general invalid contexts from the set of given 
nogoods. This border of invalid contexts, the com- 
puted nogoods, allows us afterwards to test at a low 
rate whether a context is invalid or not. It is just the 
test Bn G Computed-Nogoods : c ~_t n. This test is 
frequently required during inspection of a result and 
during output. Moreover nogoods are inherited, and 
if these nogoods are the most general invalid con- 
texts, computations for instances will be reduced. 
The search procedure for the most general invalid 
contexts starts from the most general context cv. 
It descends through the context lattice and modifies 
the set of nogoods. We give a rough description first 
and a refinement afterwards: 
Recursive procedure n-1 
1. if 3n E Nogoods : c -4 n then return 'bad'. 
2. select a disjunction d with c undefined on d and 
such that the specializer (d -* j, d ~ --~ c(d~)) is 
a context, if no such disjunction exists, return 
'good'. 
3. for each j E sub(d) recursively call n-1 with (d --+ 
j, d ~ -.+ c( d~) ). 
4. if each call returns 'bad', then replace all n E 
Nogoods : n ~_ c by c and return 'bad'. 
5. continue with step 2 selecting a different disjunc- 
tion. 
If we replace the fifth step by 
5. return 'good' 
n-1 will be a test procedure for validity. 
n-1 is not be very efficient since it visits contexts 
more than once and since it descends down to most 
specific contexts even in cases without nogoods. In 
order to describe the enhancements we write: Cl is 
relevant for c2, iff cl I-1 c2 ~ .1.. 
58 
The algorithm implemented for CFS is based on 
the following ideas: 
(a) select nogoods relevant for c, return 'good' if 
there are none 
(b) specialize c only by disjunctions for which at 
least some of the relevant nogoods is defined. 
(c) order the disjunctions, select in this order in the 
step 2.-4. cycle. 
(d) prevent multiple visits of contexts by different 
specialization sequences: if the selected disjunc- 
tion is lower than some disjunction c is defined 
on, do not select any disjunction in the recursive 
calls (do step 1 only). 
The procedure will be favorably parametrized not 
only by the context c, but also by the selection of 
relevant nogoods, which is reduced in each recursive 
call (because only 'relevant' disjunctions are selected 
due to enhencement (b)). This makes the procedure 
stop at depth linear to the number of disjunctions 
a nogood is defined on. Together with the ordering 
(c,d) every context which is more general than any 
nogood is visited once (step 1 visits due to enhence- 
ment (d) not counted), because they are candidates 
for most general nogood contexts. For very few no- 
goods it might be better to use a different proce- 
dure searching 'bottom-up' from the nogoods (as \[de 
Kleer, 1986, second part\] proposed for ATMS). 
(a) reduces spreading by recognizing contexts 
without more specific invalid contexts. (b) might be 
further restricted in some cases: select only such d 
with Vj G sub(d) : 3n E relevant-nogoods : n(d) = j. 
(b) in fact clusters disjunctions into mutually inde- 
pendent sets of disjunctions. This also ignores dis- 
junctions for which there are currently no nogoods 
thereby reducing the search space exponentially. 
Eliminating Irrelevant Disjunctions 
The algorithm implemented in CFS is also capable 
of a second task: It computes whether disjunctions 
are no longer relevant. This is the case if either the 
context in which the disjunctive term is required is 
invalid, or the contexts of all but one disjunct is in- 
valid. 
Why is this an interesting property? There are two 
reasons: This knowledge reduces the search space of 
the algorithm computing the border of most general 
nogoods. And during inheritance neither the dis- 
junction nor the nogoods for such disjunctions need 
to be inherited. It is most often during inheritance 
that a disjunction of a type becomes irrelevant in the 
instance. (Nobody would write down a disjunction 
which becomes irrelevant in the instance itself.) 
Structure- and constraint sharing in CFS makes it 
necessary to keep this information because contexts 
of shared constraints in the type are still defined on 
this disjunction, i.e. the disjunction stays relevant 
in the type. Let the only valid disjunct of d be k. 
The information that either the constraint can be 
ignored (c(d) ~ k) or the disjunction can be ignored 
(c(d) = k) is stored with the instantiation. The con- 
text mapping for the instantiation filters out either 
the whole context or the disjunction. 
The algorithm is extended in the following way: 
4a. if e is an input context of t and d is a disjunc- 
tion specializing e and the subcontexts are also 
input contexts, and if all but one specialization 
delivers 'bad' the disjunction is irrelevant for t. 
All subdisjunctions of subterms other than the 
one which is not 'bad' are irrelevant, too. 
Consequences 
One consequence of the elimination of irrelevant dis- 
junctions during inheritance is, that an efficient im- 
plementation of contexts by bitvectors (as proposed 
in e.g. \[de Kleer, 1986\]) with a simple shift operation 
for context mappings will waste a lot of space. Either 
sparse coding of these bit vectors or a difficult com- 
pactifying context mapping is required. The sparse 
coding are just vectors of pairs of disjunction names 
and choices. Maybe someone finds a good solution 
to this problem. Nevertheless the context mapping is 
not consuming much of the resources, and the elim- 
ination of irrelevant disjunctions is worth it. 
5 Conclusion 
For the tasks outlined in the first part, the efficient 
treatment of disjunctions and inheritance, we intro- 
duced contexts. Contexts have been defined on the 
basis of a set theoretic semantics for CFS feature 
structures, such that they describe the space of pos- 
sible unification conflicts adequately. The unification 
formalism of CFS computes a set of nogood contexts, 
from which the algorithm outlined in the third part 
computes the border of most general nogood con- 
texts, which is also important for inspection and out- 
put. Clearly we cannot find a polynomial algorithm 
for an exponential problem (number of possible no- 
goods), but by elaborated techniques we can reduce 
the effort exponentially in order to get usable sys- 
tems in the practical case. 
References 
\[Backofen et al., 1991\] R. Backofen, L. Euler, and 
G. Ghrz. Distributed disjunctions for life. In 
H. Boley and M. M. Richter, editors, Processing 
Declarative Knowledge. Springer, Berlin, 1991. 
\[Bhttcher and Khnyves-T6th, 1992\] M. Bhttcher 
and M. Khnyves-Thth. Non-destructive unifica- 
tion of disjunctive feature structures by constraint 
sharing. In H. Trost and R. Backofen, editors, 
Coping with Linguistic Ambiguity in Typed Fea- 
ture Formalisms, Workshop Notes, Vienna, 1992. 
ECAI '92. 
\[de Kleer, 1986\] J. de Kleer. ATMS. Artificial In- 
telligence, 28(2), 1986. 
59 
\[DSrre and Eisele, 1990\] J. DSrre and A. Eisele. Fea- 
ture logic with disjunctive unification. In Proceed- 
ings of COLING '90, Helsinki, 1990. 
\[Emele, 1991\] M. C. Emele. Unification with lazy 
non-redundant copying. In Proceedings of the gg'th 
ACL, Berkeley, 1991. 
\[Kasper, 1987\] R. Kasper. A unification method for 
disjunctive feature descriptions. In Proceedings of 
the 25'th ACL, Stanford, 1987. 
\[Kogure, 1990\] K. Kogure. Strategic lazy incremen- 
tal copy graph unification. In Proceedings of COL- 
ING '90, Helsinki, 1990. 
\[Maxwell andKaplan, 1991\] J. T. Maxwell and 
R. M. Kaplan. A method for disjunctive constraint 
satisfaction. In M. Tomita, editor, Current Issues 
in Parsing Technology. Kluver Academic Publish- 
ers, 1991. 
\[Smolka, 1988\] G. Smolka. A feature logic with 
subsorts. Lilog Report 33, IBM Deutschland, 
Stuttgart, 1988. 
60 
