Plurals, Cardinal/ties, and Structures of Determination 
Christopher U. Habel 
Universiti~t Hamburg, Fachbereich Informatik 
8chliJterstr. 70, D- 1000 Hamburg 13 
Abstract 
This paper presents an approach for processing incomplete and 
inconsistent knowledge. Beais for atteoking these prob\]ems are 
'structures of determination', which are extensions of Scott's 
approximation \]atticea taking into consideration some reguirements from 
natural language processing and representation of knowledge. The theory 
developed is exemplified with processing plural noun phrases referring 
to objects which have to be understood as classes or cots. Referential 
processes are hand\]ed by processes on 'Referential Nets', which ere a 
specific knowledge structure developed for the representation of 
object-oriented know\]edge. Problems of determination with respect to 
cardinaIity assumptions are emphasized. 
I. Introductory remarks 
Most approaches to 'proceesing reference' are concerned with the case of 
singular NPs and deal with the complications of plurals on\]y 
periphericolly by remarks af the kind "The plural case can be considered 
analogously." But such hopes are only partially justified: the plural case 
is worse and therefore more interesting. 
In the present paper I wlll discuss some spsclflc prob\]ems of 
(in)definiteness with respect to plurals from an AI point of view. The 
heart of any knowledge-based system (KB$) - man or machine - is his/ 
her/Its knowledge base (KB), containing different types af knowledge (cp. 
sect. 2). The KB reflects the KB5' view af the world; in other (e.g. 
dackendoff's, 1983) words: a projected world. (O/ring emphasis to 
projected worlds and thus to mental models leads to a psychological 
foundation of semantics.) 
The case easiest ta manage is that of a complete and consistent KB. But in 
normal life - of man es well as machine - thia almost never occurs; the 
knowledge is incomplete or inconsistent (or both). There are some 
reasons (cp. sect 3, ,t) to see both types of problem as clase\]y connected, 
as twin problems, abbreviated by I&l. It is important to extend the KBS' 
faculties with regard to the maintenance af I&l. This includes: 
- Recognition and detection of I&l 
- Correction of I&l, i.e. forcing completeness and consistency 
- Dealing, i.e. arguing ar 'thinking', with Incomplete or 
inconsistent knowledge. 
These tasks for maintaining I&l is of specific importance in processing 
reference. 
2. \]he frame of representation 
In representing the knowledge about the world (not linguistic knowledge) 
of a KBS I distinguish three types, hnawledge of facts, knowledge ofru/~ 
and knaw/ed\]e af objects, which is represented by 'Referential Nets' 
(ReiN). The formal objects, which can be underatood as internal (ar 
mental) proxies for entities of the real (or other possible) world(s) are 
called 'Referential Objects' (RafO). RefOB can be seen as underdetermlned 
formal objects (UFCO) in case of incompleteness, or as overdetermined 
(OFOs) in case of inconsistency. 
For representing the knowledge of a KB$ and the meaning of utterances I 
use a propositional 'eamanttc representation language' $RL. Far 
processing, e.g. storing and retrieving, referential relations SRL contains 
apectfic 'descriptian operators', which are from a formal point of view 
variable-binding, term-making operators. Here I will neglect the details 
of 5RL and exemplify only those 8RL-concopta which are involved in 
knowledge about objects (cp. Habel, 1986). The tatellty of RafOs and 
their properties (see below) form a net-like knowledge structure: the 
Ref~rentialNet(ReiN). ReINs are based on three types of formal entities: 
62 
referentialebj~ts(RafOs) as system-internal proxies of the abjecte of 
the world, designMionsaf RefOs, i.e. terms \[as opposed to formulas) of 
8RL and attribute~ to RafOs and dssignationa. From a formal point of view 
(Habel, 1985, 1986) these (double-attributed) ReiNs form a relation 
with 
AARefN c (R-ATT x REFO) x D-TER x D-ATT 
Remarks: 
1. REFO is the set af all referential objects at a specific point af time ( I 
neglect tlme-indecos in the present paper); D-TER, R-ATT, D-ATT are 
the set of 8RL-expreseions of the types 'designating term', 'attribute to 
RefOs', 'attributes to pairs of RefOs and D-terms'. 
2. Bracketing RefOs and their attributes reflects that in AARefNs the 1 st 
component is functional dependent of the 2nd. 
A first example will illustrate the concepts of the ReiN: 
( 1 ) John's children will travel abroad during their summer vacation. 
leads to the following entries in a ReIN (only the most relevant parts are 
formulated; attributes are omitted in the present sect.): 
(I') r. I -- 'John' 
r.2 -- ALL x : child_of (r. 1, x) 
""- SOHE x :trave\] (x, r.3, r.4) 
r. 3 -- "abroad" 
r.4 -- "during r.2'a summer vacation" 
Remarks: 
I. There are proxies for objects in a narrow sense as waI\] as for some 
in a wider sense, e.g.w.r.t, locations (r.3) or time (r.4). Their 
SRL-designaticos will nat be formalized here. 
2. "ALL" is the intenstonal class-building operator, which differs from 
the formula-making universal quantifier. "SOME" is the indefinite 
pluro\] term-maklng analogy to the definite "ALL". (On "SOtIE", tlle 
definite descriptor "IOTA" and the indefinite "ETA", which are used in 
(5'), cp. Hahel 1982, 1986). 
3. ItefNs: Under- and overdeterminetion 
In the following I will mainly deal with proxies for concrete objects, 
especially persons. A first analysis of the situation in question shows that 
a hearer of ( I ) possesses a RefO representing "John's children" without 
the abligation to knew more details about them. e.g., though s/he does not 
have to know how many they are it is passible to refer to them definitely. 
With the introduction of the additional concept 'attribute of e RefO' it is 
possible to deal with the I&l problem, 1.e. the problems af under- and 
overdetermination of formal objects. (Furthermore, the use of attributes 
leads to knowledge representations which allow easy and quick access to 
the objects in question, e.g. in anaphora resolution and generation). A 
more adequate analysis of ( I ) should lead to a representation, which 
represents the plural explicitly (and not only implicitly via "ALL"): 
(1") card~2-- r.2-- ALLx:child_of(r.l,x) 
human -J 
using a cardlnality attr/Dute to the RefO r.2 which represents the 
essential property that r.2's real-world counterpart is assumed to 
consist of more than one human being; the sertal attribute "human", 
which will be, used here only, exemplifies another type of attribute, 
namely ~rtalattribut~ 
By this attribute mechanism I represent the meaning of numerals, e.g. 
"dahn's two cars" leads to 
card= 2-r.9 ~ ALL x:cor (x) &ewn(r.l,x) 
In text generation the communicative goals determine which 
designation(s) and R-ATTs are used to form the content of the message. 
What counts as determinate depends an the type of attribute in question. 
Each type of attribute possesses its own cot af completeness and 
consistency conditions. In the case of cardlnallty, the determinacy 
condition is given by 
(2) ~rdinalit¥ Condition: 
Each set has exactly one cerdinolity. 
This eondition defines the idaal-state of the cardinality attribute which a 
system aspires to. The actual knowledge with respect to cardine\]ity 
concerns a 'rarlge of pesslble cordlna\]lttes'. From this follows what 
under- and overdeterminotion (I&l) are: 
- in the case of underdotarmination some cerdinalities are pessible, eg. 
the cardtnallty Is greater or ague1 2, but the exact value is unknown, 
in the determinate ~ only one cardinolity is possible, i.e. the exact 
cardinality is known, 
- In the case of overdetermination more than one cerdinality is 
assumed, which violates the cerdinality condition. 
I wlll go on with dohn's children: 
(3) The boys will visit France. Hory and Sue will go to Italy. 
Analogously to ( 1 ) the ReiN has to be extended to: 
(3') cord;~'t ~ r.2--- ALLx :chllr.L_of (r.l,x) 
cord ~ 2 -- r.5 ~ ALL x : child_of (r. 1, x) & boy(x) 
SOME x :visit (x, 'France') 
cord ~. 2 ~ r.6 -- ALL x : child_of (r. I, x) & girl (x) 
CONTAINS (r.7) 
CLASS ('Mary', 'Sue') card --, 2 ~ r.7 ~ SOME x : visit (x, 'Italy') 
Remarks: 
1. "cord(r.6) ~ 2" because tt ls pesslble that there ere further 
daughters of John. Note, that o\]l bays - "cord(r.5) ~. 2" - visit France 
but only some girls, namely those represented by r.7, visit Italy. 
2. I assume that the competence of calculating attributes is used in the 
maintenance of ReiNs. By this "cord(r.2) ~. 4" is calculated from 
cord(r.5) and cord(r.6). 
3. There exists an operator "IS_CONTAINED" duo\] to "CONTAINS", 
which I neglect in this paper (ep. Habel, 1986). 
r.7 con be seen as determined wlth respect to cordinoilty since an exact 
value is assumed, whereas r.2, r.5 end r.6 are underdetermined. As a \]est 
example for cordinality computations, let us take the input 
(~r) John has four or five children. Three of them are girls. 
That leads to the following changes in the ReiN: 
(4') cord := 5 --- r.2 ALL x : chlld__of (r. 1, x) 
~ CONTAINS (r.5) 
CONTAINS (r.6) 
ALL x : child_of (r.i, x) & hay(x) cord == 2- r.5 ~ SOME x : visit (x, 'France') 
ALL x : child_of (r. l, x) & girl (x) card,= 3 .-- r.6 ~ CONTAINS (r.7) 
Bemark: 
In a first step (corresponding to the first part of the input) cord(r.2) 
is sat to ,1 or ,5, In a ,second (inferential) step card(r.2) is computed to 
`5 based on the cerdinalities of r.5 (>_2) and r.6 (=3). In a third step 
card(r.5) can t)e computed to exactly 2. 
New we turn to overdoterminotton, i.e. inconsistencies. Suppose someone 
tells the KBS (or" you): 
(5) The oldest, Peter, travels to Spain. 
What is there to do now? Where are the problems, hew are they noticed, 
and how can they be solved? Before rejecting (5) wlth "That ls 
impossible!" let us discuss the changes in the REIN: 
(5') cord=5~ r.2~ ALLx:child_of(r.l,x) 
card > 5 --~ ~ CONTAINS (r.5) 
CONTAINS (r.6) 
card := 2 -- r.5 ----- 
card ~ 5 "/ 
card = :5 ~- r.6 
card = 2 -- r.7 ~-- 
card- 1 --- r.8=---~ 
ALL x : child_of (r.1, x) & boy(x) 
SOME x : visit (x, 'France') 
CONTAINS (r.8) 
ALL x : clli\]d_of (r. 1, x) & girl (x) 
CONTAINS (r.7) 
CLASS ( 'Hary', 'Sue') 
'Peter" 
IOTAx : oldest(x, r.2) 
ETA x: visit(x, '3pain') 
Remark: 
The newly created RefO r.8 is integrated in the ReiN by two links: on the 
one hand via CONTAINS from r.5 "the bays"; this link is inferred by use 
of knowledgo about Christian names in English. On the other hand via the 
oldost-eonnectlon to r.2. Thus the cordlnalltles of r.2 and r.5 (In 4') 
have to be changed, which is rcolized by assigning o second cardinolity 
attribute. (This reading of the sentence end interpretation of the net 
assumes a third son, "Peter", which vlslts Spain only. Note, that the 
inheritance about visiting France can be blocked via the 3rd designation 
of r.8. 
The points of inconsistency or everdetermination can be \]coated at the 
cardinality of r.2 ("card=5" vs. "eard>5") and of r.5 ("card=2" vs. 
"card,~ 3"). What is reasonable to do now? There are several poselbiltties: 
- Reject the newest input. But why should "card=5" be preferable to 
"cord>5" (or "card=2" to "cerd~3")? 
- Try to eo\]va the inconsistencies. Ask other people or undo inferences. 
- Try to live with inconsistencies. Be aware that reasoning con be 
dangerous. 
Why is it convenient and pessible to fol\]ow the third strategy? On the one 
hand, though there are inconsistencies with respect to the cerdineHty of 
r.2 and r.5, these inconsistenclaa ore localized and do not infect the whole 
KB. (This strategy of marking inconsistencies and thus avoiding infections 
of the KB, i.e. putting inconsistencies in quarantine, follows 8elnap 
(1976)). Therefore the system is justified In answering questions with 
regard to other ports of the ReiN. 
On the other hand, locating paints/cress of inconsistency and waiting for 
future information con \]Pad - by means of inferences - to the solution of 
the inconsistency in question. One possible correction of the 
inconsistencies in (5') cou\]d be ~chieved by detecting that the informants 
u~d different concepts of 'daughter', e.g. 'daughter', 'sdepted daughter', 
'stepdaughter'. In the pre~.~nt example the "updating of the boys", i.e. the 
new "cord(r.5) ~ 3", was not given explicitly but was inferred from the 
male Christian names 'Peter'. It is possible that the inference in question, 
which uses common knowledge about Christian names, was misleading, 
because John's oldest daughter is nicknamed, she is "a girl named Peter" 
(as Russoll's wife, who was known as Peter Spence). 
B.e~ac_k~ 
1. Another way of analysis, namely concerning designations but not 
cerdinalities, leads to a different solution with respect to r.8. Peter can 
be seen as a person visiting both France and Spain. Note, that this 
reading would also be baaed on a careful analysis of card(r.5). 
2. The parallel example in Carman would lesd either not to an 
inconsistency at all or to another type of inconsistency since 
gender-informatiea of the article would distinguish between two cases: 
"Der ~lteste, Peter..." ('dor' ~ 'masc.') leads also to (5'), but the 
possibilities for the solution of the overdotermination mentioned above 
are not usable in this case. "Die ~lteste, Peter..." ('die' ~ 'fern.') leads to 
linkage of r.8 to r.6, "the girls", and no inconsistency of cardinality 
would appear. But, most hearers would be suprised with the strange 
Christian name of the girl. 
The similarities and differences of under- and overdetermination, i.e. the 
justification of the twin-concept I&l, can be seen best by discussing the 
appropriate response to questions llke "How many children does ,John 
have?". On the one hand with respect to on undardatermined case, e.g. 
(6) card ~ 5 r.2' ALLx:chiId_of(r.l,x) 
induced by "John lies five or more children". 
In the case of underdetermination (6) the KBS knows that it has 
incomplete knowledge and therefore it is justified in answering "Five or 
more, but I don't know ex~ctly". In the case of overdetormination (5)the 
KBS knows that it has inconsistent knowledge. Therefore it should warn 
the questioner, e.g. by responding wlth "Presumably five or more, but I 
have contradictory information". Note, that it would be reasonable far 
you to usa the concept of "John's children" in a similar way if you only 
have the information in question. 
63 
4. Structures of determinntlen 
From a formal point of view the cerdinelity attributes ore examples of 
approximation structures similar to the information lattices introduced 
by Scott ( 1970); cp. Belnep (1976). The lower part of the structure of 
determination (see Fig. 1 ), "UD-CARD", represents the undardatermined 
end the upper one, "OD-CARD", the overdetermined cardinelities. The 
determined cases are represented by the "D-CARD" level, which is the 
symmetry axis of the structure. D-COrd is the set of singletons over the 
set N of natural numbers (including zero); UD-CARD consists of the 
not-singleton elements of the power-sat of N with the partial ordering 
induced by the set inclusion. OD-CARD is built up by introducing a 'dual to 
each UD-CARO' element, which Is symbolized by square brackets "\[_\]". 
NIL I x,,3\] 
/ / oo-o .o 
\[1,2\] \[1,3\] \[2,3\] \[2,4\] 
{0} {1}......_ {2} {3) {,'1.} {5) ... CARD 
\ {1,2} { 1,3} {2,3} {2,4} 
{I ,2,3} {I ,2,4} 
\ oo-CA.o 
{XEI } {x~3} 
Fig. 1 : Approximation structure CARD of cordinelity attributes 
The D-CARD elements stand for "the cerdinality is exactly the n which 
forms the singleton in question". UD-CARD represents e set of possible 
cardinelities. The minimal entity in the approximation structure, namely 
N, holds no relevant information, since "Card=N" stands for "the RefO 
has a cardinolity", and this ia true for ell RefOs. ('Cord' is o set of 
cardinalities 'cord'.) Oetting input from communication or inferential 
processes, leads to climbing up the structure, which reflects the 
enrichment of information with respect to cardinality, or to no change in 
knowledge about the attribute. The ideal-level is reached at the 
D-CARD-level: an exact cardinelity is assigned. Further input causes ( in 
the good case) no change end in the bad case of inconsistency climbing up 
into the OD-CARD-rogIOn. 
The structure of determination does not possess lattice properties; only 
the UD-CARD end the OO-cord parts are lattice-like. The sudden change 
at passing from UD-CARD or D-CARD to inconsistent OD-CARDs destroys 
the lattice properties (see below). 
The approach of structures of determination, which is exemplified here 
with the case of cordinality attributes, can be ussd analogously with 
respect to other types of attributes. The base of ell such structures ere 
lattices, e.g. those of eartal attributes, which con be interpreted as 
approximation lattices. This means that climbing up the lattice can be 
understood as increasing information. (Note.that the ALL-element in this 
Interpretation is the bottom-element). In e (half) formal way, a 
structure of determination is built up from e Scottien approximation 
\]etttco (AL) by the following method: 
1. Delete NIL from the approximation latticeAL. 
2. Devide the rest in the level of determination (LaD) which ia formed 
by the direct neighbors of the (now deleted) NIL end the 
undardatermined part of the lattice (UD-AL) which is given by those 
elements of AL which ere neither NIL nor in LaD. 
3. With respect to UD-AL construct a dual counterpart of 
overdetermined elements. This Is called OD-AL. 
'1. Olue OD-AL with UD-AL via the level of determination LaD. 
5. The ordering relations can be defined in the canonical way. 
As mentioned for the case of cerdlnn\]lty attributes such structur~ of 
determination do not possess lattice properties. This is proven in Hebel 
(1986). The same phenomenon is observed by Belnap (1976) with 
respect to his set of episternic stete~, E. The lattice properties ere 
violated at the passage to inconsistency (everdatorminetion). 
Nevertheless, the most relevant properties of Scott's approximation 
lattices else hold for structures of determination, especially the 
emplietivityby/nput( using Belnap's terminology). One very important 
difference between Scott's approach and determination structures 
concerns the NIL, which is the (!) failure element of ALs. In contrast, 
structures of determination contain many different failure elements, 
namely all beyond the level of determination. Thus a condensed history of 
informing end dtsinforming is abbreviated by the OD-ettribute. (A 
cherercterizetion of Scott's epprasch could be: "All failures ere equal, 
namely disastrous. ") Repair processes, which e.g. can be triggered by 
Input from an especially competent or believable informant, e.g. with 
respect to my example by dohn himself, levi to climbing downward in the 
structure. Note, that repairing is informing of a specific type. In contrast 
to normal informing it leads downwards; this changing of the direction 
demands a specific prior decision based on the experience that something 
was going wrong. 
I conclude this section with e remark on overdetermination: 
Overdstermined objects ere e specific type of /mpossl'ble objects (cp. 
Rapeport 1985), which constitute e test case for every semantic theory. 
'Impossibility' or 'non-existence' (as used in some approaches to this 
topic) refer to the real world and not to projected worlds, which are in 
the mind. 
5. Conclusion 
In this paper I have only dealt with I&l problems concerning the subtype 
of referential knowledge. Obviously, e similar approach is appropriate 
for the other subtypes of knowledge, i.e. for other formal objects. (Notice 
that assentia\] properties of RefOs, such as cerdinalfty, can also be seen as 
port of factual knowledge.) In the case of factual knowledge 
undardeterminetion or overdaterminetion concerns truth values. Belnep's 
(1976) four-valued logic with e lattice-theoretic semantics has 
influenced the concepts of the present paper from e logical point of view. 
Same types of ReiNs end of structures of determination ere implemented 
as parts of prototypicol text-understanding systems by the KIT-projects 
at the Technical University Berlin. 

References 

Belnep, H ( 1976): "How e computer should think", in O. Ryle (ed): 
Contemporary aspects of philosophy. Oriel Press: 8tesksfleld.30-56. 

IlobeI, Ch. ( 1982): "Referential nets with attributes", in. 6. Herecky 
( ed): COLING- 82, North- Holland: Amsterdam. I 01 - 06. 

Umbel, Ch. ( 1985): "Referential nets as knowledge structers", in T. 
Bellmer (ed): Linguistic Dynamics. daOruyter: Berlin. 62-84. 

Flobol, Oh. ( 1986): Prlnzlpien der Reforontie\]lt~t. Springer: Berlin. 

dackendoff, R. ( 1983): Semantics and Cognition. HIT-Press: 
Cambridge, Mass. 

Ropoport, W. ( 1985): "Melnongian semantics for propositional 
semantic networks". Prec. 25rd Meeting of the ACL. 't3-8. 

Scott, D. ( 1970): "Outline of a mathematical theory of computation". 
'1th Ann. Princeton Conf. on Information Sciences & Systems. 169-76. 
