Extending The Expressive Power Of Semantic Networks

L. K. Scltub<.>.-t University of Alberta Edconton, Alberta

.U.>:;SI.EEh "Factual knowledge" us"d by natural language precessing syst"as can loe cor,vcn ier.tly repn:sented in tt.e !or111 of se111antic networks. Compared to a "linear" rep.-esentation such as that of the Predicate Calculus however, seman~ic networks present Sfecial problems with res~ect to the use of logical cor.nectives, quan~ifiers, descriptior.s, and certain other constructions. syste111atic solutions to tbese problems will be proposed, in the form of extensions ~o a more or less conventional network ~otation. Predicate Calculus translations of network fropositions w: ll frequently be given for comparison, to illustrate the close kinship of the two forms of representa~ion.

Semantic networks (or nets) mean different things to different people. They a~e variously thought of as diagrams on paper, as abstract s~' ~ of n-tuples of some sort, as data structures in coaputers, or ever. as information structures in brains. ny concern here will be with semantic n~t s as .!l.L~ . .l.'h icel3!!al£>..9.\!.ll_Q.LQ!!.ll.-HL\!ct u r !:2 ~R~£~!!1irg~I££~: in e computer system fo~ understanding natural language. They aid both in the !or·ulation and exposition of the da~e structures they resemble. Exa11ples of such graphical aids are found in the work of Quillian (1968, 1969), Pall!le (1971), Schank (1972, 197:?), Sim~nons & Bruce (1971), ~.nderson & Bower (1973), Hendrix et al. (1973), Ru~nelhart et al. (1973). llylo?culos et al. (1973), and 111any other writers. Se111antic nets are also used to advantage in the ·cchani7ation of other forms of understanding, particularly scene understandir.g, e.g., by ~instcn (1<;70), G·1:r.c:an (1971), and i'irschein & Fischler (1 <;71).

The infcr111al and disparate ways i~ which semantic nets have b'en used p~eclude their precise dcfir.iticn ir. a nonrcst ~ ictive way. ~owcv~r, th£y have gehe.-elly shared the fcllowir.g characteristics:

1. £articular as well as general concepts are rcpr~~~nt~d as labeled or unlabeled r.odcs of a grarh.
2. Propositions consist of subgraphs with linl:5 to a pr~dicative concept ar.d to a suitable number of conceptual argu~ents for the predicate. ~xplicit proposition nodP.s are so~etimes introduced as points of attachment for thes':! liroks, ar,d as units or. which prcpositior.al operators ~.g., "knows that") can oper<:.tc.
3. Cuplicatior. of r.odes denotinq the same concept is avoided. Thus several arcs associat~d wi~h seve~al distinct propositions ·ay share ~he sa~e cor.cept node. Such no~es are usually regarded as corres pondin~ to a unique co111puter stnrage location, i.e., the ~ntry point for accessing knowledge about that concept. Similarly propos~tion nodes are r£garded as ur.igue.

In comfarison with Predicate Calculus encodir.gs of factual kncwl€dge, semantic nets seem more natural and understandable. !his is due to th~ cne-to-one correspor.dence between ncdes and the concepts they denote, to the clustering about a patticular node of proposi~ions atout a particula~ thing, and to the visual :mm~diacy of "ir. terrelationshiFs" among concepts, i.e., their connection~ via sequences of propositional links These properties of semantic nets aid in the design of comparison algorithms, such as that of Quillian (1968,1969) for finding intersecticn nodes for two related concepts, or that of Winston (1970) for comparing ~wo complex scer.e descriptions. certain kinds of deductive inference also appear to be facilitated by the network representation (Sandewall, 1970).

Having acknowledged some advantages of semantic nets over the Predicate Calculus repres~ntation, I should like to e~phasize that I regard the two fcrms of representation as closely akin·. I will often supply Predice~e Calculus equivalents of network propositions in order to illustrate their near-isomorphism. Further·ore, seaantic networks propos"d so far have been expre~sively weaker than Predicate Calculus, particularly in their har.dling of quantification and of higher-order state·ents. In the following ~ections I will develop a network representation which permits the use of n-ary predicates (n=1, :;, 3 ··· ), logical conn(octives, unre s tricte-d guant!fication (incluJiLg quantif i cation ov~r predicat~s), lambda abstractio~, and nor.extensional operators such as belief and counterfactual implication. The representation easily accomcodates profOSitions of the type encoded by Quillian (1968, 1~69), Wir.ston (1970), Schank (1972), and Ru~elhart et al. (1972) in their networks. Ccmfarisor. with r.etwork repre~entations used by ~hese and othe~ authors ar;; ·ad€ as far ae space permits. Sec. II introduces th€ tasic proposit:onal notation, ar.d Sees. III-V progressively extend the power of the notaticn.

II · !!..Qili...hQEQl!iti.Ql!~

!he basic node type in the notation to be developed is the concept n~. Concept ncdes may deno~e individuals such as John, Canada, a particular chair, or a particula~ real number; they may denote sets such as a set of of children, a set of numbers, o.- ~ set of properties: or they may denote predicativ~ conc<:!pts such as (the universal cor:ci!pt) chsir, rEd, hor.est, virtue, larger thar., in front of, betw~en, or qives. Nodes 2ay be labeled with r.amcs to~ the co~cepts they denote, e.g., Jchn, chair, chair1, chair2; ordinary at~ributive terms such as "~heir" are rese~ved fer the correspor:ding universal conc~pts, while nameric~lly suffixed words such as "chair1" are used for pa~ticular instances of th: concepts.

The s·allest unit of ir.for~atior. in a semantic net is the ato~ic proposition. An atomic proposition consists cf e £IQ£2§~!12n_aQ~~. a PRED link to a pr~dicativ~ node, and links to a suitatlc r.umber of concept nodes serving as arguments of ~h~ pr~dicate. The argument links are marked i~ so~e syste111atic way, e.g., A, B, c, etc., to distinguish the first, second, third, etc., arguments. Exa·ples are shown in Fig. 1(a)­ (c), alct:':l with their Predicate Calculus representations. All nones in Fig. 1 (a)- (c) are regarded as 1Y£L!!.Qde~ in Quillian· s (1968) sense and correspond to unique storage locatior.s. Note that the links in a FrOFOSition are directed from the Ftoposition node to the components of the propositior:. The only significanc~ of thiz cor.v~ntion is that it ensures nonamhiguity of th~

a Formal logical representations are often wrongly maligned fer SUfposedly cc~aitting the designer to the afplica~ion of syntactically oriented uniform infer~nce proce~ures. This c~iticis~ confuses the l~!l~~ of logic wi tr. its £~1~1~~· Nothing whet~ver prevents the arrlication o! heu~istic or plausible interence routir.~s to Pr£cicate Calculus assertions. Indeed, FLA»GER-like systems combine heuristic inf~rence ~rocedu~es with a restrict{.: fora cf Predicate Calculus in the data base.

(b) "l.llltrta is part O[ Car.acb" (E) flrt -of(ll~~rta,Canata)

A r

Fig, 1. Ato;nic propositions, in full and abbreviated.

network syntax. !n a computer implementation the links could be reversed or two-way, depending on computaticnal n~eds,

The propositional diagrams aay be simrlified as follows. A~y explicit propo£ition nodE along with its link to the predicative node may be replaced by a JJiili~~ll· Yiz., the (noncncircled) na11e of t~e prgdicate, Sir.ce predicate tokens i·plicitly establish propcsition nodes, separate tokens aust be used i~ separate propositions, even if the predicates involved are the sa11e. Another permissibl9 simplification of the diag=a·s is the omission of link markers when the predicate is ·onadic (i, e., denotes a property) or dyadic (i.e,, denotes a binary relation); in the dyadic case the first and second arguments are then distinguished by omitting the arrowhead on the lir.k to the first argument. The simplified diagra·s for the propositions in Fig. 1(a)-(c) are shown in ~ig, 1 (d)-(f), I will usually opt for the simplified notation in the sequel, except in diagramming certain higher-order constructicns.

The proposed propositional notation is closely related to various extant notations. fig 1 (e) is essentially in the style of Winston (1970), although Winston do~s not ir.troduce proposition nodes as distinct fro· concept nodes. I re9ard Fig, 1(d) as the proper monadic ar.alogue of the dyadic notation, Diagra11s 1 (a)- (c) closely rese·bl~ the prcrositional graphs of Rumelhart et al. (1972), Figs. 2 and 3 ir.dicate how the rres .. nt conv~ntions relate to those ot Quillian (1969) and Schank (1972) respectively, A fuller co11parison with a discussion of "cases" can be four.d in Schubert (19711) ·

Fig. 2. ·Compariscn with TLC notation "John gives the book to Mary"

Fig. 3. Comparison with Schank's notation "John transfers tbe book fro· John to nary"

In ·ost varietieE of semantic nets very little usg is ·ade of logical connectives, There is little need for conjunction, sir.ce usually all frOfositions in the r.et are assumed to be asserte~, and cf course this is equiv~lent to assertion cf their conjunction, That several researchers have chose~ to do without disjunction as well is perhaps traceable to the fact that assertion of "pVq" is in a sens~ o~ly half as infor~ntive as assertior. of any of the binary conjuncts which i11ply it (ptq, ~ptq, or pt~q), yet is just as bulky.

Nevertheless disjunction and other cor.nectiYes are commonplace in ordinary discourse and in a~y case they are needed for truth­ functional co·pleteness, Now everyone who uses semantic nets e·floys so·~ sort of negation device and cf course nega~ion together with ccnjucction is truth-functioc~lly co~pl£te. The probl£~ with ·ost of the ~ega~ion devices, however, is that they are applicable to a~~i£ sentences only (e.g,, putting "not" in front of a predicate, or crossing off a subject-predicate link); and negat i on of atoms together with conjunc~ior. is .!l.Q!. truth-functionally comrlute. It is quite cl~ar what the alternatives are. If ~e want to r~Etrict negation to atoms, ~e · &ced to introduce an additior.al logical connective (e.g,, disjunction or iEplication), If we want to st~y with r.egation and conjunction, we h~v· to exter.d the r.egaticn convention so that it is applicable to conjuncts, I& either case we n~ed to create graphical entities which corresfcnd to ~~~ sentences co~posed o! arbitrarily many ato~ic sentences, The obvious solution lies in the introduction of explicit nodes for logical co~poucds of profositions (or open sen~ences) , with graphical links to the components. Fig. 4 illustrates the formation of disju~ctions by the use of graphical links to tokens of the disjunction operator. The net states "Mary is not at home; she is either at school, or en the playground, or at the zoo; if she is not at schcol, her 11other will be angry". I

will aGsume that the operbtor more operands. Its ~eneral fig. 5. "V" for· takes cne is shewn or in

0

Fig. 5. Generalized disjunction.

Broker. lines are used for the operator-cperand linkR to N~t£ the logical compounds visually distinguishable. Note . that no dis~inguishing aarkers are needed on the li~ks, since disjunction is a syagctrical oreration. Ihe arrowheads can be dropped when there is no ambiguity, i.e., when tt.e operands are not ~~~ms~lves loqical compou~ds.

~he use of "will be" in Fig. q as a ~odifier of ·angry" is an evasive m~noeuvre, serving to avoid discussion cf ti~e. Of course none of the fredicates appearing illustratively in this paper are proposed as frimitives in an understanding systca. The ·~a~" ir. Fig. q is an abbreviation for "~ ---> at", which shews "~" as a monadic Cferator on the place-holder ·at" for the profcsition "at(llary, r.ary·s hoae) "·

If d~sired, ot~er log!cal connectives can be introduced in exactly the same way. For example, it would have been ~o~e natural to render "lf ~ary is not at school her mother will be angry" by fteans of implication instead of disjunct!on, even though this requires the use of an extra negation operatorz. A general!zed implication operator is shown in Fig. 6. This allows for a conjunct of

Fig. 6. GeLeralizcd ~aterial implication.

arbitrarily many antecedents and a conjunct of arbitrarily many consequents. No labels are needed in thP. atbreviate~ notation if consequent and antec~dent links are shown emerging fore and aft of the iaplicaticn symbol respectively. Equivalence is defined analogously (syabol <=>), allowing arbitrary sets of conjuncts to be equivalenced.

For a semantic net containing logical coapounds, we ·u~t revise th~ usual convention of regarding all profositions in the net as as~~rted. The convPntion r will adop~ is that the complete seaantic ~et ~~~~Il~_ixactll-1h2~~§ili2La

~hiSh-A~~-D21-S£D~£11]iL!~i-£~~

~~~~Q~i1i2D§ (i.P., Of~rands of connectives or modal operators). Graphically this mean~ that exactly those profositicr.s are asserted which are oot pcinted to. Tlus in Fig. q, for example, "llary is not at ho11e" and "~ary is at school or her ·other will be angry" an· asserted who:rcas "Mary is at th& ~oo" bnd "~art is at school" are not, This raisfs t~e qu·~ticn of how to asEert a proposition ~hich is also a constitu~nt of a compour.d profosition. first, for logical coe1pour.ds this n~~d never occur. For exa11ple, if a constitu~nt p of a disjunction pVqVr is kncwn to be assertable, then that ~ntire disjunctior. can be

2 I aa taking a rather literal interpretation of the sentence, ignoring the implicit causal pro rosi t ion.

replaced by the propositio~ p and the alternatives <;Vr d£leted. The reason is that p& (pVqVr) <=> p. Similar simplifications rfsult if a cor.stituent o~ ~nl logical ccmfound is asserted. For propositional attitudes, causes, intentions and the li~e, hooever, we may indeed want to assert a constituent independez;tly of the coopound. ln this case we car. use disjunction with a si!£gle operand, v --> p ,

as a way of saying "P Lol~s". Since the ·co·pound" proposition est~blished by the token v is not pointed to, it is automatically a~~erted. Alternatively we could use conjunction of a single proposition (with an explicit "&") or even double negation to the sa~e effect. Examples are shown in Fig. 7. The "beliefs" diagrammed in this figure

(a) ''Jci1D belivv~s thAt nary is happy"

(c) "John b~licves that narJ is happy but she isn't"

(d) ''John bcli4nes that nary iso ·t h·I'I'J l·ut st.e is"

fig. 7. Asserting propositions by aeaos of acnadic disjunction

are exa·ples cf "propositional attitudes·; they are governed by modal operators about ~hich I will havE< a little ·ore to say in Sec. v.

! will conclude this section with some reaarks on existing notations. Quillian (1968) used e "horping a:rov" to conjoin o: disjoin sets of propositions. However, any such arrow was associated witb a particular ~~~. and as onP. of the disjunctions in Fig. q illustrates, disjoi~cd propositions ne~d not have ~ny !ubject (or objact) in co·noon. Winston (1?70) r£stricted himself tc implicit conjuncticn plus negation of atonos, although h~ obtainPd some of th~ effect of disjuncticn by means ot a "may-be" operator. Ruaelhart et al. (1972) state that they allow arbitrary ccmfound fropcsiticns in the internal representation, but in their graphical r.ctation they all~w cnly chaining together of propositions aaking up an "efisode". Schank (1972, 1973) 11akes little attempt to deal graphically vith logically c.onnected propositions, as he is usually not conc€rned with displaying aore than 2 or 3 related frOfOSitior.s. He uses n~gation of a~oaic propositions and places connectives in the spaces , betwe€n propositional sutgraphs ("conceptualizatior.s") to indicate thPir logical relations. Andersen & Bower (1973) could easily have introduced unrestrict~d binary connectives since they use explicit proposition nod~s, but it is net clear to m~ whetber or not they d:d. They discuss disjunction only in connectior. with checking the sc~antic net for the presence of either of two propositions, ra~her than inserting explicit dis junctions. As for i mplica ti on, it appears that they regard their particular manner of using subset relations as giving the full power of iaplicaticn. All of their exa11ples, hcwever, involve atcmic antecedents, and it is no~ cbvious hov a sentence like "The customs official detained all tearded men who were wearing beads" would be r~pr~sentad, in which "ma~"· "bearded", and "weari~g teads" are implicative antecedents. Note that the given sentence ·ust be distinguished from both "A numb~r ot bearded men wearing beads were detained by th~ customs official" and "All of those detained by the customs official were bearded men wearing beads".

IV. i!.!!SJl ti .!J.fi.§

It is important to have logical quantifiers within s~mantic net notation for several reasons: many statements of ordinary discourse involve quantifiers ("He calle,d every day but the phone was always busy"); the representation of ~nenl knowledge in declarative form requires quantifiers ("All children like sweets"); the definition of complex concepts ' requires quantifiers ("At all times when an individual is ~!ling some foot of that individual is touching the ground ··· "); and definite descriptions of sets require qua~tifiers ("the r-eople of Canada").

Yet the treatment of quantifiers in se·antic nets has generally been rather curso~y. Of~en quantifiers are regarded as monadic mod!fiers of concept nodes, indicative of "how many there are" of that item (i.e., set cardinality). ur.iversal quantifiers are then attached in the same way, even thou<Jh the logic~l orerator A ("for ell") is not at all indicative of ca!'dinality. Tt.e only systematic attempts to include qu~r.tifiers !n semantic r.ets of which ! am awa!'e are those of Palme (1971) and ;.nder!'on & !lover (1973). Palme·s symbolism is based on Sandevall's (1970) analysis of pro~erty-structures. !n that r.rp~oach quantifiers are attached siLgly or in pairs to predicates, e.g., to symbolize a transfcrmation fro· a binary relaticn R on individuals to a binary relation on sets ARA <=> lambda XY[ (Ax) (J. y) merober (x,X) c. member (y, Y) => !I (x,y) ]. However, this doo:sr.·t allow for 3 or more quantifi~rs in a proposition ("Any politician can fool some of the people all of the time~. Anderson & Bover·s treatment is not Entirely satisfactory either. First, there is a difficulty about quantified implicative propositio~s with complex a~tecedents, which stems frcm the deficient implicative nctation. One way of characterizing the difficulty is that there is no apparent method for dis~i~guishing definite and indefinite set d~scriptions, such as "i.h! set of all dcgs that chase cats" versus "J set of dogs that chase cats", and hence no way of distinguis~ing statemer.ts involving such descriptions antecedently. Second, th~ rule that quantifiers in the subject position of the ftopositional tree have the largest scope leads to difficulties. In particular, it is awkward to raise a propositional object to the lev~l of maximum scope, as Anderso~ & Bover are well aware. For examplE, they are forced to render "There is a cat ~hat all do~s chase" as "There is a cat distinguished by the fact that all dogs chafe it", where "distinguished by" is a pseudo-predicate introduc~d to allow objects to be =aised to subject position. Additional problems are encountered in quantification over ti·e, since in Anderson & Bow~r·s notation the "time ccntext" includes an entire proposition in its scope. For exa·ple, there is no direct way to handle the distinction between "There is always someone there" and "~here is scmeone who is always there". Finally And~r son & Dower neglect to supply quantifier precedence rules vhen the scofe of a quantifi~r extands over logical combinations of propositions, as it certainly may.

The notation ! will propose is a~alogous to quantifie~-free normal form in Predicat~ Calc~lus. Propofitior.s are expr~~sed in £I~.!l!:.l!.J:2..:.!!! (~.e. · quantifi-?rs have max1111um scope), ex1.stent1.ally quantified variables are Skole~ized, and universal quantification is implic:t · This first cf all requir~s a distinction bet~een existentially and univer~ally quanti~ied nodes. A simple method is the us~ of solid lines !or existentially quantified concept . nodes (as in all previous figure~, and broken lines for universally quantifi~d nodes. Graphical Skolemization then consists of li~king each existentially quantif!~d node to all universally quantified nodes or. which it depends (i.e., whose universal quantifiers prec~de the existential quantifi~r in pre~ex form). I shall use dotted lines for these dependency li~ks for eafy distinguishability from fropositior.al and logical lin"s· ?or example, "All dogs chase some cat" is represented as s~own .in Fig. e (a). In Predicate calculus notation this is

.. · ·· 0 ··

(J.x) (dog (x) => (Ey) {cat(y) &chase(x,-y)]}, or dog(x) :) [cat(f(x))C.chase(x,f(x)) ], Skolemizad. Nov if we can assume (Ey)cat(y), i.e., there is at least one cat (or alternatively, that there is at least one dog), then this becomes

cat(f(x)) & (dog(x) => chase(x,f(x))] which corresponds to the slightly simpler diagram shown in Fig. 8(b). Here the "ca~" proposition is no longer regarded as a consequent of the "dog" proposition. This type of simplification is often appropriate for encoding nat ural language statements, since ve do not usually com~unicate in terms of propositions which are trivially true by virtue of the nonexistence of their referents~. A further simplification is indicated in Fig. 8(c), which is based or. the implicit notation for implication explained in Schubert (1 974). The diagram for the propositicn "There is a cat which all dogs chase" differs from Fig. 8 only in the absence of the dependency link between the "cat" and "dogu nodes. As another example consider the rroposition "There is always soaeone there". This ·ight be diagram·ed as in Fig. 9(a), after adding the assu·ption that there is at least one mo·ent of time. Note that a time argument has been added . . cr· .!t~l~c:_~)

to the pr~dicate "at". The representation ~eems a littlE u~natural bec·us~ of the r.eed to re~trict the universally quantit!~d ncde to "moments" and th~ implicative dep~ndence of the main relaticnship en that rest:iction. This :!tuggests that it would be more r.atural to use a many-so!'t£d logic, with each argument of each predicate restricted to a particular subdomain of the domain of di:!tcourse, and with time forming a distinct sort. Then quantificaticn over a time argument would automatically be r~strict~d to momer.ts of time. This is the course I will take, at least nominally. sortal distinctions could be made explicit by us:ng distinct node shapes for distinct Eorts, or by usiQg a distinct kind of argument ~arker on argument point~rs to entities of each distinct sort, e.g., always using OBJi (i = 1,2, ··· ) to point to argum~nts of the sort "physical object". !n fact the latter tEch~igue is used by llumelhart et al. (1972). llatt.er than

~ Which is not to say that ve do not coa~unicate about n>DeKistent entities.

commiting myself to a particuar ~e~hod here , I shall leave sortal distinctions implicit, EXCi!F': in the case of ti.re. Tiae calls for special treatment because of its central importance in structuring ev~nts. : will use pairs of parentheses instead of circles for ~aments of time and mark pointl>rs to mol'ents of time "T". A name for a mcmer. t of ti11e can be placed between the parentheses. Broken parentheses indica~e unive~sally quantified time variables. With these conventions Fig. 9(a) can be redrawn as shewn in Fig. 9 (b). "There is so~eone who is always there" would aerely lack the defendency link of fig. 9. The representation of time dependence can be simplified further with the aid of two additional conventions. The first is to place the time at which a p=opositicn hclds directly alongside the predicate token of that proposition, as in fig. 9(c). The second is to use time inter~ls as time argu~~nts (in so11e suitable sense of interval - e.g., see l!ruce, 1972). If T is a time interval, then a frorcsit i on of the form P(x,y, ··· ,T) is taken as an abbreviation of (At)[ 11ember (t ,T) c) P(x,y , ... ,t) ]. In the graphical notation ! will use square ~rackets instead of parentheses for nodes denoting time ir.tervals, and mark pcinters (if any) to such nodes "T!" instead of "T". Two equivalent ways of refreser.ting "The sun rose" are shown in Fig. 10. In both versions quantification

,.,

Fig. 10. "The sun rose",

over IACments of tin:e has been entirely surrres&d by 11eans of the interval notation. "Then· is taken as a relation between adjacent time intervals, and "before" as a relation bi!tween aoments or intervals of time. For complete sets of tia~e relations st>e Findler & Chen (1911), Bruce (1972), or Schank et al. (1"73).

r.ar.y hiqher-o:der constructions are easily expressed with th~ notation already intrcduced. For example, "John has Q.J.l of his father's faults, and carelessness is one of thea" is represented as Ehown in Fig. 11. Note that both the abbreviated and unabbreviated notation for propositions have been used here, Three of the proposition nodes are explicit, whilE "father-of" and thE tvo occurrences of "fault" establish thr~e i&~licit fropositicr. nodes, 1he higher-order predicate is of cours e "fault", ar.d the univers3lly quantified node should l;e read "fer all freciicates". Here H.e i·plicit restriction of quantificaticn to appropriate sorts has been extended to arrly to !~ as well, i.e., since "fault" is a predicate on pr~dicatcs, its argu111t:·nt in any propos i tion is implicitly restricted to th~ type "predicate·.

Fig. 11. "John has all of his father's faults, and carelessness is one of them"

Here l shculd ree~ark that past clai~. E about the equival·nce of ce~tair. vari~ties of_ ~~man~~c net nota!ion to second (or higher) order log1c have not been ~ackeci by adequate quantificational apparatus. Statements about predicates alone do not demonstrate a seccnd-order capability, as they can be ·ade in a many-sorted first-o=der logic.

finally r should point out that the . logical quantifiers are unsuited for express1ng many natural language quantifiers. ! believe that natural languag~ quantifiers not readily expressible in terms of the logical quantifiers, such as "several", "aany", "aost of", "a few acre than·, etc,, can te handled systematically by the use of (fuzzy) rroperties of set cardinalitJ and relations betveen set cardinalities, plus standard set relations such as set inclusion. for examples see Schubert (19711) and Cercone & Schubert (19711).

v. I9I~I-:!1~iQn§

In this section I will briefly illustrate the representaticn of definite and indefinite descriptions, lambda expressions, and aodal constructions. A fuller exposition is given elsavhere (Schube·rt, 1971i).

Russellian descriptions of individualE and sets are illustrated in Figs. 12 and 13 respectively (e.g., Quine, 1960). The descriptions

fig. 12. Indefinite and definite descriptions (a) "Jchn owns .! ill ~ll" (Ex) [ cwns (John, x) & car (X) & red (x) ] (b) "~2l!D!§ £!I is red" (Ex) (Ay) [owns (Jchn, y) &car (YI <=> x= y) & red (x)

are underlined in the figure legends, and fredicate Calculus translations are given £or co11parison. A r.ong~neral but frequently useful aethod cf abbreviating such descripticns is proposed in Schubert (19711).

In diagram·ing Russellian descriptions, I am not doing so as an uncritical advocate of Russell's theory. certainly it is incorrect to regara referential descriptions as nothing but disguised assertions (see Strawson, 1950) · '!"·he role I envisage for Russellian descri~tions in a se·antic net-based language understand1ng syste11 is best seen by exa11ple. Sufpose that the language understanding system is told "John's ~ar . is red". The syste· would first look for an ex1st1ng node to use as referent of ·John's car". We need not be concerned with the details of this search here, noting only that if it succeeds, D2 new Fig. 13. Indefinite and dtfinite descripticns of sets.

• (a) "'!here are h2I?.!?l £hiBr~n on the playground" (ES) (tS2:2 & (~X) ( l:leatber (X, S) =>
• ha('py(x) & child(x) & on(x,playground1))) (b) "1h~ sh.i.HH.r .Qll 1h~ J?!.H!H.Q~llS ar~ h a FPY" (.ES) { 'S2:2 & (l.x) ( m~nb£'r (x, S) <=> child (X) & on(x,flayground1)) & ( mEJDber (x, S) => happy (x) ))

description is rlaced in memory. Only "red" is predicated about the node found (provided this predication is consistent with prior knowledge). If the search fails, however, the system creates a new existentially quantified node with the attached propositicn ~hat this is the one and only car John has, possibly in a sense of "has" deterained by context. This Russellian existence assertion is placed in memory, provided it is consistent with prior knowledge. If all goes well, the net of Fig. 12(b) is the final result. But suppose that the existence assertion contradicts prior in!oraaticn to ~he 6ffect that John has no car. Tt,en the attempt to insert a new node in memory is abcrt6d, and thus no referent fer the predication "is :ed" is made available. Seeking a resolution of the difficulty encounter~d, the syste~ might well respond "Cut I thought John do~sn·t have a car". 1hus I see ·presufpcsition failure" as an .Q£~.£1.1l2ill pheno!'lcnon, ratl.u than as a logical phenc~:~enon calling for complex model­ theoretic 111anoeuvering (e.g., ~isk, 1969).

1he problem raised by lambda abstraction and mcdc\l opetators suct1 az ··nccassarily'', ''knows··, "want~'', and ''causes'' is that state~~e~ts i~volving them cannot in general b~ convert~d to prenex form. ~hus the scope conventions introduced for quantifiers are inadequate. The conventions can be generalized by allowing (dotted) scope dependency links be~ween proposition nodes and quantified nodes, to indicate that the quantifiers lie within the scopes of the Q£~rat~ which form those propositions. The n~v links supplement the dotted links already introd~ced to indicate the relative scopes of quantifiers. Two examples are given in Fig. 111. The lamtda point~r in Fig. 11i(a) fro· the

Fig. 14. Lambda atstraction and modal operators. (a) "Lovir.g solll,, cn~ is a virtue"

• virtue (lambda x( (Ey) per::on (y) &loves (x,y) )l
• (b) "Everyone ought to love someone" ought ((Ax) (ry) person (y) &( perscn (x) => loves (x, y) ])

conjunctive proposit i on node to the first argumen~ of "loves" abstracts the predic~te "loving someone" from the open sentence "x loves someone".

7he operands of the modal op~rator "ought" !n Fig. 11i(b) are regarded as implicitly conjoined. Deletion of some of the scope depend~ncy lir.ks in the two diagrams yields other (less plausible) readings of the sentences.

I have put forward scme vi~vs on the proper construction and interpretation of semantic networks, and suggested systematic method~ for expressing operations such as logical comtinaticn and quantification in these networks. The propozed representation is a fairly direct extension of several quite successful, superficially disparate representations, such as Schank's conceytualiza·ions, Winston's descriptive nets, and Sandewall·s property-structures. Consequently the computational proce~se:: that create end utilize t~eir rlata structures can readily be adapted to structures bas~d on the present repre::entation. This indicates that t~e increased expressive power the suggested r~pres€ntation proviaes should be of real value in the design of under~tandi~q systems.

A vari~ty c! problems in the representation of knc~ledge could raise additio~al questicns of notational adequacy. ~xamples are the ~andling of vagueness, events, ~be lexical meanings of complex concepts, and overall knowledg~ orgar.izaticr.. We are currer.,ly studying so~e of ttes~ protlems in the ccntext of a practical attempt to design a language understanding system.

}£AD2~1!~E!~~n!§

This work vas intended to establish a notational basis for research on a "state-based" conceptual representation by Nick Cercone and myself. A great deal of credit goes to Nick for contrituting to the ideas herein. I a· indetted to G. Prideaux, c. G. !!organ and F. J. Pelletier for pointing me to some relevant literature, and to t~e l~tter two fer several very helpful d~scuss~ons. I am also grateful for J. R. Saapson·s and K. v. Wilson's comments on the original Jnanuscript, which hofefully have led to a more readable versicn. The research vas supported by the National Research Council of Canada under Operating Grant no. Aee1e.

And .. rson, J. a~:d cover, G. (1973). .l&~Q£.t~1l.Y!Lll~I. v. 11. Winston and Washi~gto~, D.c. ~.!"All Sons,

Bruca, I!. c. (1972). "A IIedel for 'reatporal References and its Application in a Question Answering Proyraa," Artificial :ntelligence 1. fP 1-26.

Cercone, N. and Schubert, L. K. (19711). "A Sketch of state-Based Conceptual Representation," Department of Computing Science, TF711-19 Univers~ty of Alberta, Edmonton, Alberta. se~ also thls volume.

Findler, "· and Chen, D. (1971). "On the rroblems of Tillle, Retrieval of Te111poral Relations Causality, and Co-existence," Advance fapers 0 ~ Second International Jcir.t cor.ference on Art~ficial Intelligence, ;he British ccmputer Soc1ety, Lcndon, ~ngland, pp 531-5115.

Hr~chein, 0: a~d Fischler, 11. A. (1971). "A study ~n D3scr~pt~ve ~eprescntation of Pictorial Da~a," Advance Papers of Second International Jo~nt C~n~erence c~ Artificial Intelligence, The Brlt~sh Computer Society, London, England pp 258-269. ,

• Fisk, 11. (1969). "A llodal Analogue of l'ree logic," in !b~_lQ9i~~l-~a~_Q1_Doing_~nings, Lambert, K. (ed.), Yale Univ~rsity Press, N~w Haven, Connecticut, pp147-184.

Guz·an, A. (1971). "Analysis of curved Line Drawings Using Context and Global Icfor~ation," in ~S~iD£_ln~~lll~~~-~. lleltzer, B. and llichie, D. (£ds.), l.merican Elsl'vier Publishing Co11pany, New York, New York, pp 325-375,

Hendrix, G. G., l'hompson, c. 11., and Slocua, J. (1973). "Language Processing vie Canonical verbs and S£·a~tic llodels," Ad~ance Papers of Third International Joint Confere~ce on Artificial Intelligence, Sta~ford Fesearch Institute, llenlo Park, Californi~, pp 262-269.

llylopculos, J,, Badler, N., llelli, L. , and ROUSSOfCUlos, N, (1973), "1,PlP:: A iSNOBOL­ Based Prograa~ing Languag~ !o~ Artificial Intelligence Applications," Advance Pafers of Third International Joint Conference on Artificial In~~lligenc~, Star.!ord Fesearch Institute, r.enlo Park, California, pp 691-696,

Pal··· J. (1971). "llaking Co·puto;rs UndErstand Mat ural Language," in !.I~ill....ln!li.l.i..9!:.D~ll !D~-llfYii~~i£_fr29r~~ing, l'indler, N, v. & lleltz~::, c. (£ds. 1, A11ericar. Elsevier Publishin; co~rany, r:ev York, New York, FP 199244,

Ouill ian, 11. ( 1 ~68) · "Seuntic ~s~~D!l£_l~12I~~~l£~_Pr££~ing, llinsky, 11. (<?d.), :111 Press, Cadridge, llassachusetts, pp 227-270.

Quillian, 11, (1969). "The ~eachable language Co·preh<?nder," Co~·· Assoc. Co·p. llacb, 11. pp 459-475.

• Ouine, il, v. A. (196{)). .!!2~ .. L~n.LQ!!.ll£.!,, lilT Press, Cambridge, llassachusetts,

J;umelhart, D., Lindsay, P., and Norman, D. (191 2). "A Process Model for Long Term /Iemery," in Q~9~l~~iQn_QJ~e~ory, Tulving, E., and Donaldson, w. (eds.), Acade:11ic P::-ess, New York, N~w York, pp 1~8-221.

Sandevall, E. J. (1970). "A S'O!t-Orieo.ted Prcperty­ Structure ~epresentatico for Binary Relations," in ~~~iE~_lE~~lllyence_2, Meltzer, B. and Michie, D. (eds.), Am~rican Els-oviE'r Publishing COIIFany, N'O!W York, New York, pp 237-252.

Schack, R. (1972). "Conceptual Theory of Natural Language Cogn. Psych. ], pp 552-631, Dependency: !\ Understanding,"

Schank, !l. (1973). "The Fourteen Primitive Actior:s and Their Inferences," Stanford AI Pxoject, 1\e~o AIII-183, Stanford University, . Stanford, California.

Schank, R,, Goldman, N., Rieg~r, c., and Riesbeck, c, (1973). "Margie: l!egory, Analysis, Fesponse Generation, and Inference on English," Advance Papers of Third International Joint conference on Artificial :ntelligence, Stanford REsearch Institute, M~nlo Park, California, pp 25~-261,

Si··ons, R. F., and Bruce, B. c. (1971). "SoDte Relaticns Between Predicate Calculus and Semantic N~t ~epresentation of Disccurse," Advanc~ Papers of second International Joint Conference on ArtifJcial Intelli~ence, The British computer Society, London, England, pp ~211-5 30.

Strawson, P. 1'. (1950). "On Referring," !lind ~. pp ;20-3114,

Winston, P. (1970). "Learning Structural Descriptions frca Exaafles," PhD Thesis, HIT, IIAC-TR-76, Ca·tridge, r.assachusetts.