PARTS INFERENCE: Closed and Semi-Closed Partitioning Graphs

PARTS INFERENCE: CLOSED AND SEMI-CLOSED PARTITIONING GRAPHS

Mary Angela Papalaskar ts Lenhart Schubert

Department of Computing Science Universit y of Alberta Edmonton, Alberta T6G 2Ht

strategies such as recursive problem reduction . We see thts as an Important challenge tn A. I . . gtven the ubiquit y of parts hierarchies and concept hierarchies in virtuall y al 1 fields o f knowledge

Of course, a great m~ny past and present A. I . systems have made allowance for hierarchies o f various kinds . For e xamp le, Raphael ' s SIR[ 1) effectively exploited the tr·anslvtt y of part - of relationships and Quill ian ' s Semantic Memor y[2 } organized concepts as ''subset- superset" taxonomies ; (neither. tnctdentall y, paid much attention to possible exclusion relationships among subparts or subconcepts) . More recently Phi I ip Hayes[3] has devel ope d network structures and techniques for using knowledge about part - of relationships, and Fahlman[4] has made proposals for reasoning about · " tangled" overlapping concept hiera rch ies tn his NETL system .

A shortcoming of much of this work has been the lack of any attempt t o anal yse the adequacy of the proposed methods . What types of questions can they answer? Are the answers they derive rei iabl y correct? To what classes of hierarchies or "tangled" hierarchies do they apply? Will an answer be derived wtthtn a reasonable length of time?

In an attempt to remedy thts shortcoming , Schubert[5,6] studied sets of partitioning assertions o f the form (a Par .. . an) . meaning that object a Is partitioned tnto disjoint parts af. . an . wtth P defined In terms of a part -of relation " c ". Such sets of assertions correspond to arbitraril y "tangled" hierarchies One of the first findings was that in this general case even the simplest questions. such as ? [a part-of b) can be forbiddingl y difficult to answer (co-NP complete) . This Is surprising if one Is Inc! !ned to bel teve In the general tty and efftctency of ·tabel-propagat1on" methods . The next step was to define a class of P-graphs (where a P -graph is essentiall y a set of partition ing assertions) which avoids the Intractabilit y of unrestricted P - graphs , yet permits ~tangled hterarchtesh of sufficiently genera l kinds to be useful tn p r a ct ical inference prob lems . To this end a closed P - graph was defined , roughl y as a set of P-asserttons whi ch (directl y or i ndirectl y) decompose alI parts mentioned Into a subset of a fixed set o f ultimate parts Graphically, closed P - graphs have the appearance of o ver lApping parttttontng hterarchtes tn whi c h al 1 downward paths terminate at the leaves of some c ommon "ma tn" hierarchy whose root represents the merge o f all parts mentioned Examples given In [5] Illust r ate how closed P-graphs can r epresent overlap parts and "mu lt i ple views" of the same object . They can. of course. also represent partttlonlngs based on relations other than the part-of relation . as long as these relations satisfy the assumed properties of "part -of" (as mentioned later. they must induc e boolean lattices). This Inc ludes the subset - o f relation and the subconcept -of (IS-A) r elati on commonl y used in ta xonomies of t ype s .

While allowing some tangling of h ierarchies. closed P-graphs st11 I admit very effi ci ent ( I tnear or subl tnear) inference met hods fo r questions of t ype ? [a part-of b) or ?[a disjoint - from b) . as out11ned In [5] . Moreover, these methods are provably complete . Thts partially solves the problem originally addressed .

The purpose of the present paper Is twofold The first objective Is to shore up the theoretical foundat ions

ABSTRACT

We consider the problem of answering part -of questions and questions about overlap tn partitioning structures, which ts of Importance tn A. l systems knowledgeable about parts relationships, set tncluston relationships or taxonomies of types . In an earl ter paper tt was noted that the problem o f extracting tnformatton from arbitrary sets of parttttontng assertions ( "P-graphs") Is Intractable (at least 1f P f NP) and the more restrtcttve class of quasi - hierarchical closed P-graphs was introduced as a fairl y fle)(tble representation of partitioning structures permitting efftctent Information extraction . The present paper Introduces the larger class of semi-closed P - graphs . and provides efftctent and complete methods for answering part-of and dlsjolntness questions based on such P-graphs

I INTRODUCTION

Consider the relative ease with which people can solve ~problems" such as

1. Does a dog have a spine?
2. Is sulphur a precious metal?
3. In comparison with a problem such as the following :
4. The members of a certain group of people have the following properties If any one member of the group envies another member, and that other member envies a third. then the first also envies the third ; and tf any two members of the group envy the same person then they love each other . AI . B t l I, Cecil and Otdl are members of the group , and Al env1es 8111, Cectt envies Bill. and Otdt envies Cec 11 . Does D 1 d 1 1 ove A 1 ?

(1) and (2) can be solved "without thinking" , but (3) requires some deliberate thought . (Of course some mental effort Is required merel y to understand the problem , but some additional effort Is required to solve tt) . Yet from a logi c al point of view ( 1)-(3) are very much the same kinds of problems. namely problems of Inferring Inclusion or dtsjotntness relationships In taxonomic struc tures . and (2) probably requires as many Inference steps as (3) . Note that tt would be Implausible to suppose that people r ecal l that sulphur Is not a precious metal as an expl lcltly known fa c t . rather than an Inference

This suggests that ( 1 ) and (2) are solved by very efficient special-pur pose methods that exploit the structure of taxonomies, while (3) Is solved by more labori ous general methods Whtch type of method ts used ts a matter of famll tar tty : tf we have reflected on the relat ionships between AI, Btl 1 . Cecil and Oldl -or a much larger group - at length, and the relationships can be vtewed taxonomically, we will eventually asstmtlate the taxonomy In the same wa y we ha ve assimilated the taxonomies of anima l parts. or the taxonomies of substances .

Even if these comments are psychologicall y incorr ect , · they serve to make a practical point concerning A I systems : tf such systems are to use taxonomi c knowledge wtth the same ease as humans , they wtll have to be equipped wtth special - purpose inference mechanisms for dotng so tnstead of r el ying on general problem-solving

• This work was supported by NSERC operating grant A8818

o f t he earlier work by supplying axioms for the part-of r elation , · stating some Immediate consequences and c arefull y defining various kinds of P-graphs and relevant no t ions Thts ts the subject of sections 2 ~nd 3 . Later ( tn sec ti on 6l we also illlJStrate the model - theoretic t echn iques which provide a basts for proving inference a l gor i thms for P - graphs correct and complete .

The second objective ts to liberalize the notion of a closed P-graph so as to provide a more flexible r epresentation for parts structures without sacrtflctng inferenc e efficiency It was noted in [5] (and proved in [6 ]) that an arbitrary P-graph can tn principle be conve r ted to a logically equivalent closed P-graph . Howeve r, the equ ivalent closed graph may be much larger tha n the original open graph

Consider the following situation . Suppose that a per s on ( or c omputer) knows who the faculty members a 1 , . , a15 of certain computer science department Care, and also knows that the department divides orga ni zationally Into a chairman c1 , an advisory committee c2, a 1 i brary committee c3. a cot loquium committee c·' · and graduate and undergraduate committees . cS and c6 . He/she/I t doesn ' t know the current chairman or const i tution of the committees (perhaps after being out of touch f o r a y ear) . This Information, tn the form of a P- g r aph , Is shown In Fig . i . ·· Note that not all paths tn tht s g r aph term i nate at the leaves of a ~ matn h ie r arc hy (though all terminate at the leaves of one of the t wo main hterarchtes). so that the graph ts open Conve r sion of the graph to a closed graph would Introduce 90 ne~ parts tn addttton to the 22 already present! (We a re Ignoring constraints such as that ct. the chairman, must equal one of a1, ... , at5 and that each cl must consist o f a subset of the af, for stmpltctty) . Thts ts because

conver si o n to a c losed graph produces an "arttftctal" tn t e g r atton of the alternative viewpoints In the ortgtnal g r aph , Introducing nodes for all the ways In whtch parts tn o ne v tew may overlap with parts In the other The ques ti o n - answering algorithms rely on the presence of thes e o verlap nodes . Yet It ts obv ious that part-of quest ions and dtsjotntness questions can be answered very eas tly for the original graph : everything ts part of c . and ~~ eac h of the two partltlontngs all dtsttnct par ts are disjoint while for parts ai. cj , taken from both parttttontngs , the correct answer to ?[a/ part - of cj) or ?[af dtsjotnt-from cj] ts "unknown" A reduction to closed gr a phs would only obscure the logic of the requtstte r e ason ing process .

A simila r example would be provided by a partly functional and partl y anatomic representation of bratn structure tn wh i ch the postulated functional subsystems ( s ay, perceptual subsystems , motor control subsystems. shor t term and long term memory, language understanding subsy s t ems. etc . ) cannot be reliably tdenttfted wtth par t lcular anatomic structures . A computer encoding of s uch Incomplete knowledge should not require Introduction of t de nt t fters and parttttontng assertions for all possible overlap parts corresponding to the two v i ews . Examples of this type, tnvolvtng poorly Integrated a lter native vtews of some physical , pol lttcal , or abstract entit y are east ly constructed, and could easily arise In a n AI s y stem. particularly one which Is fed Its knowledge p iec emeal .

This motivates the Introduction of recursively defined semt-closed P-graphs in sectton 4 . A semi-closed P-graph ts e ither a c losed P-graph, or a semt - closed P-graph wtth another semi-closed P - graph attached to tt by one o f Its matn roots . Clearly the P-graph of Ftg . i ts a

· We take thts opportunity to correct an error tn [5) : tn the first sentence of Sec . 2. the assumption that part-of ha s the e x tension property should be replaced by the a s sumption that the merge and overlap functions "U" and "" "are mutu81ly dtstrtbuttve (see below) . · · For the purposes of this illustration, we Intend C to be Interpreted as the (disconnected) physical whole composed of the· department members, not as a set . Thus the

af and c t are parts of C , not elemenrs-or subsets .

semi - closed P-graph , since it c onsists of the c l o sed committee-structure subgraph attached 2Y ~mai n roo t c to the closed faculty - roster· subgraph

In Sec . 5 efficient c omplet e al gor ithms f or answering part - of and dtsjotntnes s que s ti ons on the ba s 1s of semi-closed P - gr8phs are developed . We feel that the class of semi-closed P - graphs Is probably as large a class of P - graphs as Is needed for most practical appl teat tons to taxonomic structures , and as can be easil y mechanized , as far as answering part - of and disjotntness questions is concerned .

JJ THE PART-OF RELATION. PARTJTJONJNGS AND P-GRAPHS

The part-of relation, c , that the gi ven methods rely upon ts assumed to have the following propert i es [6} :

• (I) ' C ' Is a partial ordering ;

( 1/x) [ xcx J (1/xy)[[[xcy]&[ycx]]· >[ x =y ]]

(1/xyz)[ [ [xcy]&[yC:Z] ] ·> [xc:z] J

• (tt I Existence of a unique empty object e such that (1/x)[eo:::x]
• (t t l) Existence of an 'overlap' function n such that (1/xyz)[ [zc(nxy) ] <=>[ [zcx]&[zcy]]]
• (tv) Existence of a 'merge ' function U such that (1/xyz)[[(Uxy)C:Z]<·>[[xcz]&[yc:z]]J
• (v) Existence of a ' remainder ' function \ such that ( 1/xyz )[ [z·( \xy)] <·> [ [ x= ( Uz( nxy)) ]&[ ( nyz )=6]]]
• (vt) Mutual dtstrtbuttvtty of nand U:

(llxyz)[(nx(Uyz)) · ((U(nxy)(nxz))] (1/xyz)((Ux(nyz))·((n(Uxy)(Uxz)))

It ts shown tn [6] that the assumed properties of the part - of relation induce a boolean lattlce . on the set {xl xcw} for any w. The following are some consequences of this that are used throughout the proofs . From now on brackets are omttted where no ambiguity arises .

• (a) (1/xy)[[Uxy·Uyx] & [nxy=nyx]]
• ( b) (1/xy)[xcy<· >[nxy·x & Uxy ·y]]
• (c) (1/xyz)[y·nxz <·>[(Uy( \ xz))·x & (ny(\xz)) =e])
• (d) (llx)[nxe·e & uxe= x ]
• ( e) (1/xy)[(Ux(nxy)) =x & (nx(Uxy))=x)
• (f) The functions nand U are associative .

For brevity, nand U will be I nformally used as many-place functions since, from (vt) , this results tn no ambiguit y.

Partltlontngs a r e defined tn terms of the part-of relation ; tntuttlvely , a partitioning assertion enumerates a set of disjoint parts of the object that tt per tains to

Oeftnttton : A parttttontng assertton is of the form r;- Pm y 1-- ym) , m~ 2 . where ~.v r ... ,ym c an be constants or variables of the object language and Pm ts the m+l place p r edi c ate symbo l defined b y ·

(1/xyz)[[ x P2 y z) <=>[ x= Uy z & e =ny z]J

and for all m~2 :

Thus. by deftnttton. and (1) above, the order of the y ' s ts tmmatertal . ·p~ will be used for "P2"

Parttttontng assertions are the building units of P-graphs

Oeftnttton · A P-graph ts a ftntte non-empty set of partttlontng assertions of the form [x P y z . ) together with non-empttness assertions of the form [xfe) over constants of the object language The dtsttnct constants~ ~ z of a P-graph will be referred to as the "nodes" of the P-graph .

The reader ' s attentton ts drawn to the fact that distinct object language constants correspond to distinct nodes by deftnttton . Consequently a statement such as a·b can only express that a and b denote the same obtect, not that a and bare the same node . However. a metal tngu·sttc statement such as ·x·y", where x andy stand for metalanguage vartables ranging over the nodes of a P-graph ts taken to mean that x and y denote the same node . Generally statements of the object language assert facts such as ·a ts part of b" and so on , whtle those of the metalanguage are about relations between nodes of P-graphs such as the descendant retatton deftned below . Boldface symbols will be used tn the metalanguage In order to stress thts distinction

It ts assumed throughout thts paper that the assertions whtch make up a P-graph along wtth the part-of axioms are consistent . It should be noted, however, that a P-graph G along with the part -of axtoms and the usual rules of inference of first order logic tn general amounts to an Incomplete theory of the objects of the graph; t.e . not every well formed formula w butlt up froM constants that are nodes of G. e. predicate sy~ols c , Pm, · , functton symbols n . U, \ and the logical connectives ts et ther provable (G f- w) or d t sprovabl e ( G f- ~w) (8]

As an example consider the case where all that ts known ts that "b ts part of a· and ·c ts part of a"; from this tt ts clearly undecidable whether or not band care dtsjolnt . Although this Is tntulttvely obvtous tn such stmple cases . tn general. showing that some question cannot be answered from the tnformatton avat1ab1e requtres a formal argument . Typtcally, showing that a parttcular statement cannot be proved. g1ven the tnformatton available from the P-graph . will constst of ·~htbtttng a model of the graph tn which the statement ts tn fact false . stnce , by soundness of the rules of inference . a statema'nt c an be dertved frol'f' a consistent sat of sentences (t a ,a theory) only If It ts true tn all models of the theory

Ill HIERARCHIES AND ~ P-GRAPH$

Stmp1y stated . a descendant of a node "a" of a P - graph ts any node from whtch there is an upward path In the graph that leads to "a" . Stmllarly . a hterarchy ts a P-graph that takes the form of a tree with no more than one P-assertion about each node; a clos'ed graph ts one tn which all nodes are ulttmately partlttoned tnto a set of disjoint " leaves "

These nottons are made formal tn the followtng deftntttons :

Oeftnttton : The descendant relatton <between the nodes x . y and z of a P- graph G ts deftned by~ (I) ~x for all nodes x of G (t I) tf ~y and z ts a dtrect descendant of x then z~y .

We say that x ts a dtrect descendant of y tf there ts an assertion tn G of the form : [ y P k x z f ··· Zk - f ] for some k . (Of course , X need not be the first argument followtng Pk) .

The ancestor relation is the inverse of the desc endant relation

Oeflnttion : A leaf ts a node that has no descendants other than itself

Oeftnttion : A root ts a node that has no ancestors other than ttself .

Oeftnttton : A P- graph G Is acycltc tf and only if for any two nodes x and y of G, tf ~y and ~x . then x·y .

The graphs that will be considered here are acycl tc . Note that all the nodes that make up a cycle tn a P-graph are forced to be tdenttcal tn denotation . I.e .. the object language formula x=y can be derived for any two nodes x , y from the assertions of the P-graph and the part-of axioms . · Thus cycles are eastly el tmtnated by col lapsing the cycltc nodes .

Graphs tn which some node ts provably empty are of relatively 1 lttle practtcal A. l interest, stnce they do not reflect the kinds of knowledge typically employed tn "common sense· Inferences For example , people presumabl y do not usually hold bel tefs about human anatomy (or about the anatomy of a bicycle, organization, or computer program) which logically requtre some of the parts about whtch the bel tefs are held to be empty .

Oeftn~ : A P - graph ts fully -consistent iff none of its nodes can be proven to be empty .

Oeftnttton : A~~ ts an acyclic P-graph .wtth a unique root and at most one partittontng assertion about each non-leaf node .

Oeftnltton : A path ts a set of nodes of a P-graph ordered by the dtrect descendant relation .

Oeftnttton : A hterarchy ts a stmple P-graph tn whtch there Is at most one path between any two nodes .

Examples of stmple graphs and hierarchies are shown tn Ftg . 2 . Hterarchtes are the most destrable form of P-graph , because parts-reasoning for hierarchies ts trtvtal : tn a hterarchy xcy ts provable for any two nodes x , y tf and only tf ~y . Further , nxy·e ts provable tf and only if there is no path connecting x andy, and x·y ts provable tf and only tf x·y t .. e ., all the nodes represent posstbly dtsttnct objects . It can also be shown that hterarchtes are fully consistent and that any full y consistent simple graph ts a hierarchy {7) .

Fig . 2 General P- graphs and hterarchtes (a) , (b) are stmple ; (b) ts a hierarchy but (a) ts not stnce there are two paths between "a· and "b" . (c) ts not s imple . stnce there are two assertions about "n "

Unfortunatel y. h ierarchies can onl y represent some very restricted kinds of tnformatton about parts Usuall y , parts knowledge about the world takes the form of ' tangled hierarchies ' . Reasoning about arbitrary P-graphs is known to be co -NP -complete . This problem is dealt wi th tn [5] by reductng arbitrary P- graphs to closed P-graphs · G is closed tff any two of tts nodes are projec ttble into a common subhlerarchy A node n is proJectible tnto a subhterarchy H tf G contains a subhterarchy r oot ed at n whose leaves 1 te tn H. In theory, a singl e parts node wil I be regarded as a s ubhterarchy. although , stri c tl y speaking , It cannot stand on tts own asaP- graph , according to t he deftnttton . Thus any node ts trtvially projecttble 1nto any subhterarchy to which tt belongs . Hence any two nodes of a subhterarchy Hare projectible into a common subhterarchy, vtz ., H.

· Formulas involving object language and metalanguage s ymbols are interpreted as object language formulas (symbol sequenc es), 1 . e . , the object language symbols are mentioned rather than used . Thus x·y (unltke xay) denotes an object language for~ula . rather than a proposttton The protectton of a node n tnto the leaves of a closed P - graph G 1s the largest subset L of the leaves of G that are also leaves of a subhterarchy rooted at n .

It 1s shown 1n [6) that for every P-graph there 1s an equivalent closed P-graph . Inference methods are gtven t o answer the quest1ons ?(b part-of a) and ?[a d1sjo1nt-from b) for fully cons1stent closed P-graphs, tn ltnear space-ttme relative to the number of edges of the closed graph .

It ts proved tn [6] that all the leaves of a fully cons1stent, closed P-graph belong to a s1ngle (not necessarily uniQue) matn hierarchy whose root represents the whole entity Such a root wtll be called a matn ~ o f the closed p-graph .

IV SEMI-CLOSED P-GRAPHS

Semi-closed P - graphs relax so~e of the restrtcttons of closed P-graphs . thus formtng a larger class . The tactt restriction to fully consistent graphs should be kept fn mtnd .

a sem1-closed P-graph that has a sem1-closed P- graph attached by a matn root to one of tts nodes . (It t s easy to see that a semi-closed P-graph, 1 ike a closed P-graph , must have at least

Deftnttton : A semt - closed P-graph ts : (1) a closed P - graph. or ( 11) one matn root) .

As semt-closed P-graphs are deftned tn terms of closed P-graphs , the Inference methods presented here rely on those developed for closed P-graphs [5] .

The design of the following algorithms is based on the observation that semi -c losed P-graphs can be vtewed as trees of ~lased P- graphs; each vertex represents a closed subgraPh and each edge a common node of the two P-graphs (parent and child subgraphs) that it connects . Since the closed subgraphs can have at most one node tn common , thts wt l 1 be a tree . Examples of corresponding trees for P-graphs are given 1n f1gure 3(c) , (d) and (e) .

Note that edges out of dtsttnct vertices correspond to distinc t node~ tn the P- graph whtle edges out of the same vertex may represent the same node .

For any gtven semt - closed P-graph, tt ts possible to attach labels to the nodes wh1ch 1nd1cate the pos1t1on tn the corresponding tree of closed P-graphs . Implementation details are of no concern at the moment ; we assume semi-closed P- graphs to be searched by the algo rithms of Sec . 5 have been preprocessed, wtth labels being attached to all nodes whtch tndtcate thetr posttton tn the corresponding tree of closed P - graphs . Thus. for any pair of nodes of a semi-closed P- graph, tt wt11 be possible to arrtve at a patr of Rancestor" nodes which both belong to the same closed subgraph tree vertex . Note that one (or even both) of the "ancestors" sought may be the same as the corresponding tntttal node .

In f1gure 3(b), for e · ample, for rand q the corresponding patr ts r' and q ', whtle for rands the corresponding patr Is r ' and s

We have put "ancestors" In quotes above , since we are deal tng wtth an ancestor (descendarlt) relation whtch t s somewhat more general than that for mally defined earl ter : r' ts an "ancestor" of r tf and only if ~r~' orr ts project lble tnto a set of nodes nr . ... , nJ< such that for' all t, tSt ~ k either n i~r · orr ' Is an "ancestor .. of n' (see F 1 g 4) .

V ALGORITHMS fQB EXTRACTING JNFQRMATIQN f!Q! SEMI-CLOSED P-GRAPHS

Algor ithms for answering the Questions ? [>< part-of y] and ?[>< d1sjo1nt-from y] 1n fully cons1stent closed P-graphs have been developed 1n [5] and are Incorporated tn the methods given below . So , for any two nodes x , y of a fully consistent closed P-graph G. assume there are algortthms P(x,y) and O(x,y) that wttl return ~yes ". "noR or "unknown" to the respective questions. on the basts of what can be logtcally deduced from the closed P-graph G The algorithms are complete tn the sense that ·they return "unknown" only if neither a postttve nor a ·negattve answer logically follows from the P- graph and the part-of axioms . The same property ts destred for the new algorithms .

Algor1thms P(><,y) and D(><,y) make use of a predicate N(xJ, .. ,Xn) which ts true tf the merge of xt, ... ,xn is provably non- empty and false otherwise . It was noted 1n (5] that th1s pred1cate 1s eff1c1ently dec1dable for closed P- graphs . In appl y 1ng P(>< , y) and D(><.y) to closed P- graphs embedded w1th1n sem1-closed P-graphs, we need to assume that N is still efficiently decidable, with the provabll tty requirement now referring to the entire semi-closed graph. The assumption Is justified stnce the only changes In the truth values of N( x 1 , ..· xn) over nodes of a c I osed graph C. resu 1 t i ng from attachment of semi-closed P-graphs to C. are those due to the non-emptiness of nodes to which a semi-closed graph containing a provably non-empty node was attached (this Information propagates "upward" in the tree of closed graphs): and the only change potentially resulting from the attachment of C to a semi-closed P-graph Is that due to provable non - empt tMss of the node to which C was attached (this Information propagates "downward" via matn nodes which are points of attachment in the tree of closed P-graphs) The emptiness assertions thus necessitated at points of attachment by the upward and downward flow of Information can be computed In one "pass" each over al 1 the no~es of the semi-closed P-graph, In the worst case .

In the following algorithms the test "a:b" ts an abbreviation which stands for :

"((C(a,b) and P(a,b)) or ?[a part-of b])"

where C(a,b) Is a predicate which ts true If the nodes a and b belong to a common closed subgraph, and false otherwise .

"a;b" incorporates a recursive call to the algorithm ?[a part-of b) to determine whether the answer to the question "azb?" (I . e . , do the nodes a and b denote the same object?) ts "yes". tn cases where it Is already known that b ts part of a; (this test t s only used where a ts an ancestor of b, as for x' and x) Let X', y' denote the nearest patr of "ancestors" whtch belong to a common closed subgraph for x andy respectively, as described tn the above dtscusston .

To answer ?[x part-of y!:

If (x·=x and y ·=y) then return P(x' ,y') else If y ·=y then

If P( x'. y') · "yes · then return ·yes ·

else If (D(x' ,y' )·"yes" and N(x)) then return "no" else return "unknown"

else If x · =x then

If P(x' ,y· )·"no· then return ·no· else return "unknown·

else If (D(y ' .x')·"yes· and N(x)) then return "no" else return "unknown"

To answer ?[x disjoint-from y] :

If (x ·=x and y ·=yl then return D(x' ,y·)

else If D( x '. y') · "yes" then return "yes"

else If x ·=x then

If (P(y' .x· )·"yes" and N(y)) then return ·no" else return "unknown"

else If y · :y then

If (P(x',y')·"yes· and N(x)) then return "no" else return "unknown"

else return "unknown"

VI CORRECTNESS OF THE PROPOSED METHODS

This section Is devoted to showing how much can be Inferred from P-graphs and , In particular, proving the question answering methods gtven tn the previous section correct and complete .

The logical foundations of these proofs have been brtef1y discussed In section 2 In deciding whether a statement regarding objects represented tn a P - graph is a valtd Inference from the P-graph, the part-of axioms and the assertions that make up the P-graph are vtewed as a theor y ( tn the logical sense) . Thus. the question reduces to what is a theorem for that theory.

Because of the soundness and the completeness of ftrst - order logic, we can write

for any fully consistent P-~raph G, meaning that+ ts derivable as a theorem Iff. ts true tn a11 models of G

A model of a P-graph Is an Interpretation of the parts nodes of G. the function symbols u, n. \. the relation c and constant e. such that the part-of axtoms and the asserttons of G are sattsfted.

When deal tng wtth knowledge representation we are interested tn interpretations whose domatn conststs of Ftg. 5 G ts A fully consistent semi-closed P-graph Subgr~phs St. S2, SJ are semt-closed, and C closed ~· ~nd b' belong to the same closed subgraph C. so P(a' . b') and O(a' ,b ' ) are used . b and b' belong to a smaller semt -closed subgraph. thus the algorithms CC'In be appl ted recursively to determine whether G r- b=b' Thus if G f- b=b ' . then If P(a ' ,b ' )="yes" the algorithm yields "yes" for ?[a part-of b]

real world objects (concrete or abstract) . Thus we have ·real world " models for P-graphs

The completeness and correctness of the given algorithms relates to the dertvab11 tty of statements of the form a c b, a t b, nabc9 o·r nabJl-6 . To show that the methods are complete and correct It is necessary to prove that for an assertion+. the algorithm will return "yes" If G f- +. "no" If G f- ~+. and "unknown" otherwise . The following lemma illustrates the sorts of techn1ques used and facti ttates the proofs of correctness and completeness

Lemma1 : Let G be a fully consistent closed P-graph Let I be an Interpretation that assigns functions U, nand\ to the symbols U, n, and \, and the relat1on ~to the symbol c of the object language and ass1gns objects from a set A to the constants (nodes) of the P-graph so as to satisfy

the part-of axioms and :

(I) tf nand k are the interpretations for two leaves nand k of G, respectively, then: nn~<=e

( t t) t f n and nt. . ,nk are the interpretat tons of a node nand tts projection nt, .nk onto the leaves of G. respectively, then : n·(Unr . . . . nk)

Then I constitutes a model of G ( t . e . . all the assertions of G are true under such an interpretation)

Proof : Let [n P nf, ... ,nk] be an assertion of G, and let ~ .Nk be the (sets) projections of nl, .. , nk Into the leaves of G , respectively .

where ~i and ~j are sets of interpretations of the nodes tn the sets Nf and NJ respectively (U is informally used here as an operator on sets) .

Since G ts a closed P-Qraph therefore NiflNj=f> (for If x(NfnNJ then x=e. since G ~ 0nfnj=9) Thus from ( i) nnfnj·e.

Now Unr nk = U(UNI l. (UNk)

Furthermore ~ru .. UNk Is the projection of n into the leaves of G, since:

1) any leaf tn the projection of nf ts also tn the projection of n stnce tt ts a descendant of n . 2) let "a" be a leaf tn the projection of n

nan-=a .

Thus G f- na(Unl . . . nk )=a, G f- Oa(U(UNI) . . . (UNk) )=a

hence G f- U(Oa(UNI) . . . Oa(UNk))=a But if a1JC for all leaves X In the union of the projections of the n f' s , then G r- nax=e so a~e and G wou ld not be fully consistent Thus a must be tn the projection of one of the ni ' s .

t heref ore. unr .. nk=n

Hence, I I= [ n P n I ... nk I

The following lemmas sketch the proof of correc tness and completeness of the algorithms ; these are proved tn (7] , by methods very similar to those employed tn the proof of lemma 1

Lemma2 : A semi - c l osed graph G consisting of full y consis tent sem t-closed graphs T and 5. suc h that 5 ts attached toT by its matn r oo t onl y, ts full y consistent

Proof The proof of this lemma makes use of theorem 2 of [5} whic h states that for every P-graph there Is a logi ca lly equi valent closed P - graph . Once deal tng wtth closed P-graphs we c an construct a model In which a11 the nodes have non-empty Interpretations .

For the followtng three lemmas let G be a semi - closed full y consistent P-graph LetS and T be closed subgraphs o f G, both rooted at some node "a· with no ot her common nodes , and suppose G without T is 8 closed subgraph

Lemma3 : Let s r , . , sn and t r . .. , tn be nodes of S and T respectivel y . For any s i. tj , G I-f Os i tj·6

Proof : The same model theoretic methods are used In thts proof The tdea ts to suppose there is a model of G that satisfi es nsrtnse and from that construct another model that sat tsftes nsrtnfe .

~4 : Let x andy be nodes of SandT respectively . (a) G 1- yc:x ·> G 1- a= x

(b l G 1- xr::y

Proof : Straightforward .

Lemma5 : If y is a node of T and x t s a node of G not and G 1-far::y then : tnT ,

Proof 5 t rat gt"1t forward

Theorem: This theorem relaxes the r~s trtctt on that the subgrap hs T,S and G without T be c losed , tn lemma 5 .

~ This makes reference to the theorem 2 from (5) .

For the f o llowing corollaries to the theorem let G be a ful l y consi stent semi -c losed P-graph with subgraphs Ta , S. Tb such that Ta and Tb are roo ted at nodes a '. b ' o f 5, respectively and have no other common nodes with S or each other . Let a , b be nodes of Ta, Tb respectively , such that G 1-f ·a · c:: a and G 1-f b ' C:: b .

The correctness and completeness of the proposed algorithms follows from the above theorem and its coro118r1es .

VII CONCLUDING REMARKS

In (6] tt ts shown that the problem of answer ing questions about part-of and dtsjotntness relations between nodes of a general P-graph is co-NP-complete . This motivates the search for algorithms whtch answer these questions for as large a class of P-graphs as possible . and hence the development of semi - closed P- graphs . Note , however . that tn proving the co-NP-completeness o f these problems , the restriction to fully con~tstent P ~ graphs had not been made: thus It is conceivable that methods can be devised to answer these questions efficientl y for general full y consistent P-graphs . Thts would clearl y make the foregoing obsolete; thus the co-NP-completeness o f the corresponding problem needs to be Investigated .

Semt-closed P-graphs are tn most cases sufficientl y general to accommodate all incoming parts information without an intervening conversion Nevertheless. algorithms to convert general to semi-closed P-graphs need to be developed ; the conversion can be accomplished tn a bottom up fashion wtth relati ve ease . It should be noted that we are mostl y interested tn a knowledge assimtlattng, system , so the order of entry of the assertions will be stgntftcant .

The restrtctton that a semt - c1osed P-graph constst of a semt - closed P-graph wtth another semt - closed P-graph attached by the main root to one of tts nodes could yet be relaxed , leadlng~a larger class of graphs .

Another area of further Investigation Is the applications of P-graphs to propostttonal logic and theorem provtng . Clause sets can be translated to P-graphs. exp1otttng the analogy between tmpltcatton and part-of. and vice-versa . Thus P-graphs may offer a new approach to theorem proving for certain classes of clauses .

ACKNQWLEDGEMENTS

We wish to thank Leo Hartman for the help he has offered through dlsscusstons of this work and for his assistance tn preparing the ftnal draft of this paper .