Semantic Networks as Abstract Data Types

SEMANTIC NETWORKS AS ABSTRACT DATA TYPES

Werner Dilger and Wolfgang Womann Universitat Kaiserslautern Fachbereich Informatik Postfach 3049 D-6750 Kaiserslautern

FR Germany

system which is shown to be noetherian and confluent. The metanet is correct, in the sense that terms built of operations and individuals from the domain of semantic networks,i.e. describing networks can be reduced into an equivalent minimal genera­ ting expression which is not further reduc­ ible and which contains only constructors.

II SPECIFICATION OF A METANET

Because of the abstraction from con­ crete types for nodes and edges, we can define operations on nodes and edges inde­ pendently from their types. So we are able to examine general characteristics of se­ mantic networks. This leads to production schemata instead of productions of the re­ write system, i.e. the axiomatic definition can be conceived as a meta-description of a semantic net, from which the axiomatiza­ tion of concrete nets can be derived by in­ stantiation of concrete types for all oc­ currences of type variables. For example, node types could be "concept" and "instance", edge types could be "isa", "subset-of", "object-of", "agent".By means of this ab­ straction we get an axiomatic definition of the abstract data type "metanet" by 35 axioms which are easy to surrey. Some of the axioms are provided with conditions, enclosed in{ ... }, wich restrict the ap­ plicability of the productions.

We now present the specification of the abstract data type "metanet". This specification is based on the abstract data types "boolean" and "set". "set" con­ sists of the operations: EMPTYSET, ISEMPTY­ SET, INSERT, DELETE, ISIN.

Abbreviations:

NT {NT1,NT2, ... ,NTn} set of node types. ET (ET1, ... ,ETm) set of edge types~ nl i represents a node named nl with

type Ni.

[nl i,n2 j] represents nodes n.l-and n2. an edge between the

ADDNODE.i represents the operation of ad­ ding a node with type NTi to the metanet. DELETEDGE.e represents the operation of delation of an edge of type ETe·

ABSTRACT

A meta-description of semantic networks as abstract data types is given by a set of 35 production schempta.

With this schemata it is possible to specify all types of semantic networks as abstract data types. By instantiation of concrete types for nodes and edges as semantic primitives we get from the meta­ descrip~ion axiomatic definitions of arbi­ trary types of semantic networks as ab­ stract data types.

The production schemata of the meta­ description can be shown to be noetherian and confluent. Each term describing a semantic network can be reduced to an equivalent minimal generating expression.

I INTRODUCTION

Semantic networks are frequently used in NL-systems as a means . for knowledge re­ presentation. There is a great number of different types of semantic networks which demonstrates their qualification for the purpose of knowledge representation. In (Barr and Feigenbaum, 1981), knowledge re­ presentation is conceived as data struc­ tures together with interpretative opera­ tions. We adopt this interpretation for se­ mantic networks and describe them by means of the theory of abstract data types (Goguen, Thatcher and Wagner, 1976).

We start from a very general and multi­ purpose type of semantic net: the metanet. In the description of the metanet we ab­ stract · ·from the sarirantic primitives re­ P·~senting them by variables.

~he metanet consists of a set N of nodes and a set E of edges. Every node (edge) belongs to a subset of N (E), which is a representation of a node (edge) type NTi (ETel. The number of node and edge types is finite.

We give an axiomatic definition of the metanet using general operations on net­ works. The set of 35 axioms is a rewrite METANET = SET +

sorts: NT 1 , ... ,NTn' ET 1 , ... ,ETm

operationsymbols: V i E NT, V e E ET

... metanet

EMPTYNET:

ADDNODE.i:

metanet

INSERTEDGE.e: metanet

DELETENODE.i: metanet

DELETEEDGE.e: meta net

ISEMPTY:

metanet

ISNODE:

metanet

ISEDGE. e :

meta net

NODES:

metanet

EDGES . e:

metanet

NEIGHBOURNODES: metanet NT.

ET~ e

NT .

ET~ e

NT

ET e

... metanet

... metanet

... metanet

... metanet

... boolean

... boolean

boolean

+ SET(NT)

... SET(ET )

SET(NTf

axioms: v m E metanet v v

v n i,n1 i,n2 i

v n1 j,n2 j E N.

v n2 =k,n3 k E NJ k

-

v n4 l E Nl

(*axioms concerning the boolean operation "ISEMPTY"*)

1. ISEMPTY(EMPTYNET) ... TRUE
2. ISEMPTY(ADDNODE.i(m,n i)) ... FALSE
3. ISEMPTY(INSERTEDGE.e(;,[n1 i,n2 j])) & {ISNODE(m,n1 i)AISNODE(m,n2 j)}~ FALSE (*if an edge-will be insert;d and one or both nodes are not in the net, this is an error*)
4. INSERTEDGE.e(m,[n1 i,n2 j])&{NOT ISNODE (m,n1 i)VNOT ISNODE(m,n2 j)+ Error - metanet
5. (*axioms concerning the operation "NODES" which provides the set of all nodes in the net*)
6. NODES(EMPTYNET) + EMPTYSET
7. NODES(ADDNODE.i(m,n i)) + INSERT(NODES(m),n il
8. NODES(INSERTEDGE.;(m,[n1 i,n2 j])) & {ISNODE(m,n1 i)AISNODE(m~n2 j)}+NODES(m) (*axioms concerning the del;tion of nodes*)
9. DELETENODE.i(EMPTYNET,n i) + EMPTYNET
10. DELETENODE.i(ADDNODE.i(;,n i) ,n i) & {ISEMPTYSET(NEIGHBOURNODES(m,n l))} + DELETENODE.i(m,n i) -
11. DELETENODE.i(m,n-i)&{NOT ISEMPTYSET NEIGHBOURNODE(m,; i))} ... Error t t - me ane
12. DELETENODE.i(ADDNODE.j(m,n2 j) ,n1 i) & {n2 j~n1 i}+ADDNODE.j(DELETENODE.l (m,;1 i)~n2 j)
13. DELETENODE.l(INSERTED�E.e(m,[n1_j,n2_k]~ n i)&{n i~n1 jAn i~n2 kAISNODE(m,n1 j)A ISNODE(m,n2 k)}+INSERTED�E.e(DELETE~ NODE.i(m,n l),[n1 j,n2 k])
14. DELETENODE~i(INSERTED�E.e(m,[n1_i,n2_j]} n1_i)&{ISNODE(m,n1_i)AISNODE(m,n2_j)} ... Errormetanet
15. 14)DELETF.NODE.i(INSERTEDGE.e(m,[n2_j,n1 i]~ n1_i)&{ISNODE(m,n2_j)AISNQDE(m , n1_i)J
16. Error metanet

e ,f

i, j

E Ni E ET

E NT

• (*axioms -concerning the existence of a node in the net*)
• ISNODE(EMPTYNET,n_i) +FALSE
• ISNODE(ADDNODE.i(m,n_i) , n_i) +TRUE
• ISNODE (ADDNODE. i (m, n 1 i) , n2 j) & {n1_i~n2 j} ... ISNODE(;,n2_j) (*axioms concerning the operation "EDGES.e" which provides the set of all edges of type e*l
• EDGES.e(EMPTYNET) + EMPTYSET
• EDGES.f(INSERTEDGE.e(m,[n1 i,n2 j])) & {ISNODE(m,n1_i)AISNODE(m,n2 j)} ... EDGES.f(m)
• EDGES.e(INSERTEDGE . e(m,[n1 i,n2 j] ) )& {ISNODE(m,n1 i)AISNODE(m,n2 j)} + INSERT(EDGES.e(m) , [n1 i,n2 j])
• EDGES.e(ADDNODE.i(m,n_il)+EDGES.e(m) (*axioms concerning the deletion of edges*)
• DELETEEDGE.e(EMPTYNET,[ n1_i,n2 j]) ... EMPTYNET
• DELETEEDGE.e(INSERTEDGE.e(m,[ n1 i, n2 j]),[n1 i,n2 j])&{ISNODE(m,nl i) A ISNODE(m,n2 j)}-+ ·m
• DELETEEDGE.;(INSERTEDGE.f(m,[ n1 i, n2 j]) ,[ n3 k,n4 l]) & - {(;1 i~n3 kVn2 j~n4 lve~f)AISNODE (m,nl i)AISNODE(m,n2 j)}+INSERTEDGE.f (DELETEEDGE.e(m,[ n3 k,n4 l]), [n1 i,n2 j]) -
• DELETEEDGE.e(ADDNODE.i(m,n1 i), [n2 j,n3 k])+ADDNODE.i(DELETEEDGE.e (m,[n2 j~n3 k]) ,n1 i) (*axioms co;cerning the existence of an edge of type e in the net*)
• ISEDGE.e(EMPTYNET,[n1 i,n2 j])+FALSE
• ISEDGE.e(INSERTEDGE.e(m,[nl i,n2 j]) , [n1 i,n2 j )&{ISNODE(m,n1 ilA ISNODE(m~n2 j)} ... TRUE -
• ISEDGE.e(INSERTEDGE.f(m,[n1 i,n2 j]), [n3 k,n4 l])&{(n1 i~n3 kvn2-j~n4-lve~f) AISNODE(;,n1 i)AISNODE(m,n2-j)} + ISED�E.e(m~[n3_k,n4_l]) -
• (*axioms concerning the operation "NEIGHBOURNODES" which provides the set of all adjacent nodes of a node*)
• NEIGHBOURNODES(EMPTYNET,n_i)+EMPTYSET
• NEIGHBOURNODES(ADDNODE.i(m,n i) ,n i)& {ISNODE(m,n_i)}+NEIGHBOURNODES(m,;_i)
• NEIGHBOURNODES(ADDNODE.i(m,n i) ,n i)& {NOT ISNODE(m,n i)} ... EMPTYSET . -
• NEIGHBOURNODES(ADDNODE.i(m,n1 i) ,n2 j) &{n1 i~n2 j} ... NEIGHBOURNODES(m,n2 j)
• NEIGHBOURNODES(INSERTEDGE.e(m,[n1 i, n2 j]) ,n1 i) &{ISNODE (m,n1 i) A - ISNODE(m,;2 j)}+INSERT(NEIGHBOURNODES (m,n1 i) ,n2-j)
• NEIGHBOURNODES(INSERTEDGE.e(m,[n1 i, n2 j]) ,n2 j)&{ISNODE(m,nl i)AISNODE (m~n2 j)}~INSERT(NEI�HBOURNODES(m,n2 j) n 1 i)
• NEIGHBOURNODES(INSERTEDGE.e(m,[nl i, n2 j]) ,n3 k)& - {n3 k~n1 lAn3 k~n2 jAISNODE(m,n1 i)A ISNODE(m~n2 j)}+NEI�HBOURNODES(m~n3_k)

III PROPERTIES OF THE METANET

The following ideas are incorporated in the METANET:

• The operations have no side effects. Example: Before a node can be deleted, all its incident edges have to be de~ted . Else, if we would try to delete a node prior to the deletion of its incident edges , we had to delete its edges together

with itself to avoid mistakes.

• For each sorts there is an error element Error 5 for the handll .ng of exceptions (Goguen, Thatcher and Wagner, 1976).

Example: Axiom 4: If an attempt is made to insert an edge between nodes n1 and n2 and one of them does not exist in the network, then the insert operation is eva luated to Errornetwork·

• The operations are assumed to be strict, i.e. if an error e l ement occurs some­ where the whole expression is evaluated to Errors (Goguen, Thatcher and Wagner, 19 7 6) ·

The production schemata of the meta­ descriptionren be proven as noetherian by one of the techniques given in (Dershowitz and Manna, 1973), (Manna, Ness and Vuillemin, 197 3) . It is easy to find weights for the individual and operation symbols in the production schemata , such that the technique of (Manna, Ness and Vuillemin, 1973) can be applied. Con­ fluence can be shown by means of the super­ position algorithm of (Knuth and Bendix, 1969). Both properties make it possible that every term describing a metanet is reducible to an equivalent minimal genera­ ting expression (Womann, 1983), i.e. a term consisting only of operations which

are constructors.

Metanets can be extended by nodes of higher type representing semantic networks. This extended metanet is specified in the same way as the basic metanet. (Womann, 1983) gives a specification of an extended metanet which corresponds to the parti­ tioned networks (Hendrix, 1979). The axioms are similar to those given here, except that all operations have an addi­ tional argument concerning spaces and there are some further axioms for the vistas.

IV A SIMPLE EXAMPLE

We give an example of a concrete net­ work.

node types = 2 (Concept, Instance). edge types = 2 (subset_of, element_of) Con~Concept,Ins~Instance,sub~subset_of , el~element_of .

The full specification of this semantic network a~ instantiation of the metanet consists of 78 axioms. We omit the fully instantiated specification, but cf. (Womann, 1983). Rather we present a subset of the axioms, which is used for the re­ duction of a sample term.

Instantiated axioms for the example:

• i 1) DELETEEL(INSERTSUB(m,[n1 con ,n 2 con)), [n3 ins,n4 con))& - - {(nl con~n3 insvn2 con~n4 conVEL~SUB) AISNODE(m,nl con) AISNODE(rn ,n 2 con)}~ INSERTSUB(DELETEEL(m, [ n3 ins,~4 con)), [nl con,n2 con)) - -

(*i~stance-of axiom 24*)

• i2) DELETEEL(ADDCON(m,n1 con) ,[n2 ins, n3 con))~ADDCON(DELETEEL(m,[n2 ins, n3-con)) ,n1 con) -

(*instance of axiom 25*)

• i3) DELETEEL(INSERTEL(m,[n1 ins,n2 con)), [n1 ins,n2 con))&{ISNODE(m,nl ins)A ISNODE(m,n2 con)}~m - (*instance of axiom 23*)

The concrete network is:

The term T 0 describes this semantic net T := INSERTSUB(ADDCON(INSERTEL(ADDCON 0 (ADDINS(ADDCON(EMPTYNET,science), mathematics),

sports) ,

[mathematics sports)) ,

fencing), [fencing,sports))

Because we made a mistake classifying mathematics as an instance of sports, we want to adjust this. We extend term T0 ad­ ding two new operations. Then we delete the element of-edge betweeen the nodes for mathematics-and sports and we add an ele­ ment_of-edge between mathematics and science. The extended term is named T 1 .

:= INSERTEL(DELETEEL(T ,(mathematics, sports]), [mathematigs, science])

Now we reduce T 1 by means of the in­ stantiated axioms to an equivalent term which is a minimal generating expression (the reader is invited to check what lm" means whereever it occurs).

• with G·{fencingln1 con,sportsln2 con, mathematicsln3 ins~sportsln4 con~ .·· lm} - -
• := INSERTELEMENT(INSERTSUB(DELETEEL (ADDCON(INSERTEL(ADDCON(ADDINS (ADDCON(EMPTYNET,science) ,mathe­ matics) , sports) , [rna thematics, sports]) fencing) ,[mathematics,sports]), [fencing,sports]) ,[mathematics, science])
• i 2 with G·{fencingln1 con,mathematicsl n2_ins,sportsln3_c;n, ... lm}
• := INSERTEL(INSERTSUB(ADDCON(DELETEEL (INSERTEL(ADDCON(ADDINS(ADDCON (EMPTYNET,science) ,mathematics), sports) ,[mathematics,sports]), [mathematics,sports]) ,fencing), [fencing,sports]), [mathematics, science])
• i3 with os{mathematicsln1 ins,sportsl n2_con, ... lm} - ·
• := INSERTEL(INSERTSUB(ADDCON(ADDCON (ADDINS(ADDCON(EMPTYNET,science), mathematics) ,sports) ,fencing), [fencing, sports]) , -[mathematics, science])

T 4 is a minimal generating expression. No further axioms are applicable. T 4 is equivalent to T 1 .

V CONCLUSION

It is difficult to define concrete se­ mantic networks as abstract data types because the specification of such a data type would become too complex and hard to survey. On the other side it is desirable to have semantic networks defined as ab­ stract data types, because the structure of an AI-system depends heavily on the realization of its knowledge representa­ tion technique. If this technique is de­ fined by means of abstract data type theory, the whole system can be structured as a hierarchy of abstract data types. The metanet is a means to overcome this prob­ lem. The metanet is defined as a speci­ fication of an abstract data type and each semantic network can be described as an instance of the metanet.

At present, we are implementing a pro­ gram which yields instantiations of the metanet from concrete semantic primitives. Together with an interpreter for the axioms which reduces terms to minimal generating expressions we would have a tool for development and testing applica­ bility of semantic networks and for the comparison of different semantic networks on the same level.