The Logic of Inheritance in Frame Systems
Proceedings of the Tenth International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 483-487.
© 1987 International Joint Conferences on Artificial Intelligence
Abstract
This paper shows how the semantics of frames with exceptions can be described logically. We define a simple (purely declarative) frame language allowing for multiple inheritance and meta classes (i.e. the instances of a class may be classes themselves). Expressions of this language are translated into first order formulas. Circumscription of a certain predicate in the resulting theory yields the desired semantics. Our approach allows the intuition that subclasses should override superclasses to be represented in a very natural way .
- Allard!, G., Simi, M., Consistencv and Completeness of Omega, a Logic ftw Knowledge Representation. Proc. IJCAI 81, 1981,504-510
- Brachman/Schmolze 85
- Brachman, R.J., Schmolze, J.G., An Ouen!Ww of the Klr ONE Knowledge Representation System. Cognitive Sci- ence 9(2) , 1985, 171-216
- Etherington, D.W., Fbrm.ali.zing Nonmonotonic Reason- ing Systems. Artificial Intelligence 31, 1987, 41-85
- Etherington/Reiter 83
- Etherington, D.W., Reiter, R., 01\ /nll.eritance HiArat- chies With. Ezceptions. Proc. AAAI-83, 1983, 104-108
- Hayes, P.J ., The Logic of Fr-ames. in: Brachman, R.J., Levesque, H.J. (Eds.), Readings in Arliticial Intelli- gence, Tioga Publishing, Palo Alto, 1979, 287-295
- Hayes/Hendrix 81
- Hayes, P.J., Hendrix, G.G., A Logical View of 7}nles. SIGART Newsletter 74, 1981, 128-130
- Lifschilz, V., 01\ the Sa.tisftability of lXrcumscription. Artificial Intelligence 28, 1986, 17-27
- McCarthy, J. , Applications of arcumscription to Fbt- matizing Common Sense Knowledge. Proc. Non- Monotonic Reasoning Workshop, 1984, 295-327
- di Primio/Brewka 85
- di Primio , F., Brewka, G., BABYLON-Kernel System of an Jn.tegrated D\vironmmt for &pert System Develop- ment and qperation. Proc. 5th International Workshop Expert Systems and their Applications, Avig- non, 1985, 573-583
- Reiter, R., A Logic ftw Default Reasoning. Artificial Intelligence 25(1) , 1980, 81-132
- Roberts/Goldstein 77
- Roberts, R.B., Goldstein, I.P., 1he FRL Nanuet. MIT AI- Memo 409, 1977
- Sandewall, E., Nonmonotonic /n.ference Ru.les ftw .111/Jti- ple /nll.eritance with. Ezceptions. Proc. IEEE, Vol. 74, No . 10, 1986, 1345-1353
- Symbolics, Lisp Machine Manual. Vol. 3, Usp Language, Cambridge, 1985
- Tourelzky ,64
- Tourelzky, D.S., Implicit Ordering of Defaults in ln.Mt- itance Systems . Proc. AAAI-84, 1984, 322-325
- Tourelzky, D.S., 7he Mathematics of /n.Mritance Sys- tems. Research Noles in Artlftcial Intelligence, Pitman, London , 1986
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
THE LOGIC OF INHERITANCE IN FRAME SYSTEMS
Gerhard Brew/ea. Genna.n Resea.rch. Institute for Ala.th.ema.tics a.nd Da.ta. Processing Postfa.ch. 12 40 D 5205 Sa.nkt Augustin Fed. Rep. of Ge1ma.ny
ABSTRACT
This paper shows how the semantics of frames with exceptions can be described logically. We define a simple (purely declarative) frame language allowing for multiple inheritance and meta classes (i.e. the instances of a class may be classes themselves). Expressions of this language are translated into first order formulas. Circumscription of a certain predicate in the resulting theory yields the desired semantics. Our approach allows the intuition that subclasses should override superclasses to be represented in a very natural way.
I INTRODUCTION
Inheritance systems have a long tradition in AI. They allow the description of hierarchies of objects and classes (we use the term hierarchy in the sense of an acyclic network throughout the paper) and the inheri tance of properties in such hierarchies. There are two main types of inheritance systems: those which admit exceptions to inheritance and those who do not. KL ONE [Brachman/Schmolze 85] and OMEGA [Attardi/Simi 81] are examples of the second type. Systems with exceptions are for instance FRL [Roberts/Goldstein 77], Flavors [Symbolics 85] and the BABYLON-Frame-System [di Primio/Brewka 85].
A common way of defining a semantics for a formalism F1 is to translate it into another formalism F2 for which a well defined semantics exists (this amounts to stating that Fl is a notationa.l variant of (a subset of) F2) . In the knowledge representation field first order logic is a good candidate for F2 since it is well under stood and has an appealing semantics.
It is not too difficult to describe the semantics of inheritance systems without exceptions in first order logic, see for instance [Hayes 79], [Hayes/Hendrix 81], where frames are interpreted as unary and slots as binary predicates.
Inheritance with exceptions is much more difficult since exceptions introduce nonmonotonicity. Ether ington and Reiter use default logic [Reiter 80] to describe the semantics of NETL-like inheritance net works [Etherington/Reiter 83][Etherington 87]. The problem with their approach is that the intuition underlying all inheritance systems, namely that sub classes should override superclasses (we will call this intuition the specia.liza.tion principle), is not present in their formalization . They require exceptions to be explicit (as exception links) in the network.
Touretzky tries to capture the specialization principle in his inferential distance ordering [Touretzky 84] [Touretzky 86]. But I think he is not right in stating that "inferential distance is a partial ordering on defaults that implements this intuition" ([Touretzky 84],p.325) . The reason is very simple. The inheritance system he uses cannot represent the notion of sub class. It only uses defeasible links with the intuitive meaning A's a.re typica.Lly B's. But if we have long chains as
it may even be the case that A 1 and An are disjoint. But how can the intuition that subclasses should over ride superclasses be captured if the notion of subclass cannot even be represented? Touretzky simply redefines the meaning of subcla.ss. He states: " .. . A is a subclass of B iff there is an inheritance path from A to B."([Touretzky 84],p.322). But changing the definition of subclass is certainly not a solution.
As Sandewall [Sandewall 86] has shown, there are cases where Touretzky's approach leads to counterin tuitive results. We will discuss an example in section VI.
Sandewall argues for defining a partial semantics for inheritance systems by a collection of structure types since this "semantics by examples" is the best we have up to now. He, also, does not distinguish between strict and defeasible links . This can lead to situations where we expect different results from the same structure type. Let's discuss a slight generalization of his type 1B structures which can be represented as follows (IS-A links are represented by---+. NOT-IS-A links by~):

With n = 2 and the interpretation A = Clyde, 8 1 = Roy alEiephant, 8 2 = Elephant, C = Gray (this is exactly Sandewall's example) we expect, of course, Clyde not to be Gray. But what if we have n = 4 and A= P_!te~-8.1 = Student. 8 2 = Adult, :0... = llarried, 8 4 = HaaTwoChiF dren, C ·= 01Cier'l'han28. 'f think there fs no reason to prefer Peter being not Older'l'han28.
We try to show in this paper that at leost for special types of inheritance systems the situation is not that bad. We will concentrate on frame systems (class/property inheritance systems in . Touretzky's terminology [Touretzky 86]). They allow to represent hierarchies with strict subclass relations as well as properties (slots with slot va.lues) that members of classes (frames) typically possess. On one hand the expre·ssiveness of these systems is stronger than that of inheritance systems which only admit Is-A and NOT-Is-A links since defeasible and undefeasible links can be represented. On the other hand the expres siveness is much more restricted since chains of defeasible inferences are not allowed. Fortunately, we do not need Touretzky's formal apparatus and his predicate lattices to describe the semantics of such a frame system.
In principle, second order logic would be a good for malism to express the specialization principle In a very intuitive way. If frames are interpreted as predi cates, then the fact that one frame specializes another can easily be represented by a second order predicate. But, of course, second order logic Intro duces many difficulties, especially since we need a nonmonotonlc logical formalism.
Fortunately, there is a well-known technique (some times called "reification") which allows us to remain totally in first order logic. Instead of writing IIAN(Peter) for expressing the fact that Peter Is an instance of the frame llan, we Introduce a predicate IS and a constant llan and express the mentioned fact as IS(Peter,llan). If a slot Age of Peter has the value 28, then we write HOLDS(.Age,Peter,25) Instead of AGE(Peter,28). The use of constants Instead of predi cate symbols allows to reason about properties of frames in first order logic.
We will introduce a three-place predicate EXCEP TIONAL whose extension will be minimized. We use McCarthy's circumscription technique [McCarthy 84] for that purpose. Circumscription is a very general formalization of nonmonotonlc reasoning, many even think the most promising one (e.g. Raymond Reiter stated that in his invited talk during AAAI-86). The advantages of circumscription are
- it Is quite close to standard logic,
- it has a very appealing semantics defined in terms of minimal models.
Various different forms of circumscription have been defined during the last years. We will need a form known as variable circumscription [McCarthy 84]. Variable circumscription allows predicates to vary during the minimization. It will turn out that the logi cal formulas we need to represent frame and Instance definitions belong to the class of universal formulas. This is fine since for universal formulas variable circumscription cannot lead to inconsistencies [Lifschltz The rest of this paper is organized as follows . In sec tion II we define a simple frame language which allows us to define a class/instance hierarchy with multiple inheritance and meta classes (i.e. classes whose instances are classes themselves) . In section III we show how the definitions of this language can be translated into a set of first order formulas in :which the predicate EXCEPTIONAL is circumscribed. Section IV gives a short example, and in section V we discuss ambiguities in frame systems.
Throughout the paper we use a logic with equality and make the unique names assumption, i.e. different sym bols denote different objects.
II THE FRAME LANGUAGE
The frame language we will use In this paper is very similar to the BABYLON frame language [ di Primio/Brewka 85), but extends it somewhat since we want to allow frames to be instances of (meta) frames . Frames are defined as follows:
(detrrame fram.e-nam.e l(.upen superframe 1 ... superframe l)l f(81ou (slot 1 value 1 ) (slotk valuek))l)
!!-brackets indicate an optional part of a definition. Instances of frames can be defined in the following way
(deftnst.ance instance-name of frame-name I with slot 1 = value 1 sloth.= valueh.l)
For the sake of simplicity we do not allow instances to be instances of different frames here. This is not a strong restriction, because we always can define one frame having the different frames as supers and instantiate that frame.
Since we want to allow instances to be classes them selves, we extend the usual frame definitions some what and allow also definitions of the form
(detrrame fram.e-nam.e 1 I (lrwt.ance-of frame-name 2 I with slotm. = valuem. slotn = valuenl)l f(.upen superframe 1 ... superframe )I f(slou q (slotk valuek) (slotl valuel))l)
In this definition slot ... slotn are attributes of the frame itself, slotk ... sllitl attributes of the instances of the frame (in our language the difference betweeen Instances and frames is less important than in other frame systems, so we could have·used a common construct, e.g. defobject for all definitions. We wanted, however, to retain some similarity with other well known languages and chose the more conventional syntax, therefore). ·
Let us assume that frames must be defined before they are mentioned in definitions as supers or as frames to be instantiated. Then our language allows to define directed acyclic graphs in which superclass and instance links may appear anywhere, but - as men· tioned above - at most one instance link may go out from one node.
We allow multiple inheritance in our frame language. This means that a frame is allowed to have more than one {direct) superframe. In this case an inheritance strategy must specify from which frame an object inherits a property. There are different strategies implemented in existing systems. Mostly the {direct or indirect) superframes of a frame are linearized in some way. The Flavors system [Symbolics 85], for instance, uses such a linearization (until recently even superclasses could override their own subclasses in certain cases, this has been remedied in the newest Flavors version). This is not the best idea, however, since sometimes any linearization yields unintuitive results. An old example is: quakers are pacifists, republicans are not pacifists, Nixon is a quaker and a republican. How about his pacifism? The available information is ambiguous. Our intuition in this case is to remain agnostic. We have evidence for and against his pacifism, but nothing allows to prefer one of the contradictory conclusions. So we simply don't know and our system should not infer anything.
In the introduction we mentioned the specialization principle: subclasses should override superclasses. Here we have the other side of the coin: only sub classes should override superclasses. This is also Touretzky's view [Touretzky 86].
In section V we will show that circumscription easily handles ambiguities the way we want them to be han dled.
III THE MEANING OF THE FBAME LANGUAGE
We now describe how definitions of our frame language can be translated into a set of second order formulas. We introduce the predicate EXCEPTIONAL which essen· tially is a three-place variant of McCarthy's ABnormal predicate. The idea is: if Frame 1 has a slot Slot 1 with value Value 1 this will be represented as
Forall x. IS(x,Frame 1 ) 1: ~ EXCEPTIONAL(x,Slot 1 ,Frame 1 ) -> HOLDS{Slotl'x,V alue 1 )
Intuitively EXCEPI'IONAL(x,Slot 1 ,Frame 1 ) can be read as "x does not inherit information about attribute Slot 1 from frame Frame 1 ".
Sometimes slots are interpreted as functions, not as general relations. We prefer the second approach here since it makes multiple values for slots possible. We don't deal with multiple values in this paper, how· ever.
Independently from the definitions to be translated we need the following four formulas:
- [m.e11ning of SPECIALIZES]
Forall p,q. SPECWJZES (p,q) -> (Forall x. IS(x,p) ·> IS(x,q))
If a class specializes another class then all members of the class are also members of the other class.
S) [trt~nsitivity of SPECIALIZES]
SPECIALIZES(x,y) 1: SPECIALIZES(y,z)
Forall x,y,s. -> SPECIALIZES(x,z)
Specialization is transitive.
- [m.111ning of HA8-SLOTj
:rorall frame,slot,value. HAS-SLOT(frame,slot. value) -> (Forall x. IS{x,fnune) 1: ~ EXCEPI'IONAL(x,slot,frame) -> HOLDS(slot,x,value))
We introduce the predicate HAS-SLOT here as a matter of convenience. It makes the rest of the translation more readable.
4) [speciclli%11tion formult~]
Forall x, frame 1 , frames, value 1 , values, slot. IS (x,framel.) a HAS-SLOT ( rame 1 ,slot,value 1 ) 1: SPECIALIZES (fnune..l,fnune 2 J a HAS-SLOT (frame 2 ,siOt,value 2 ) 1: ~ value 1 =values -> EXCEPTIONAL(x,slot,frames)
Intuitively: x is exceptional with respect to a slot of a frame if x is an instance of a more special frame, for which different information regarding the slot is avail able. This is the formula representing the specializa tion principle.
Now we can easily map frame and instance definitions into a set of logical formulas.
The definition of a frame
(defframe my-fra,me (supers superframe 1 ... superfrt~mek) {slots {slot 1 value 1 ) (slotn va.luen)))
is translated into the following formulas SPECIALIZES(m.y-frllme ,superfrt~me 1 ) SPECIALIZES(my-frame,superframek) HAS-SLOT(m.y·frame,slot 1 ,va.lue 1 ) HAS-SLOT(m.y-frame,slotn,va.luen)
The definition of an instance
(detlnBtance my-instance of my-frame with slot 1 = value 1 sloth.= valueh.) yields the following formulas: IS( my-instance ,my-frame) HOLDS(slot 1 ,my-instance,value 1 ) HOLDS(slot h.' my-instance, value h.) Forall frame, value. IS(my-instance,frame) It HAS-SLOT(frame,slot 1 ,value) It ~ value = value 1 -> EXCEPTIONAL(my-instance,slot 1 ,frame) Forall frame, value. IS( my-instance .frame) It HAS-SLOT(frame,sloth.,value) It ~value= value h. -> EXCEPTIONAL(my-instance,sloth.,frame) The last implications guarantee cancellation of inheri tance for slots initialized in the instance definition. Definitions of the form (detrrame frame-name 1 (instance-of frame-name 2 with slotm = valuem slotn = valuen) (supers superframe 1 ... superframeq) (slot. (slotk valuek) (slotl valuel))) have the same translation as the two seperate definitions (detrrame frame-name 1 (supers superframe 1 ... superframe ) (slot. (slotk valuek) q (slot l value l))) and
(deftnstance frame-name 1 of frame-name 2 with slotm = valuem slotn = valuen)
The meaning of a set of frame and instance definitions now is the variable circumscription of EXCEPTIONAL in the set of formulas described above. We allow all predi cates to vary during the minimization, cf. [McCarthy 84].
IV EXAMPLE
We use the following definitions (defframe Car (slot. (Wheela 4) (Seats 5))) (defframe Sport.scar (supers Car) (slot. (Seat. 2) (Cylinders 8))) (detlnBtance Speedy of Sport.car with Cylinders = 8) then, besides formulas 1) ... 4) as defined in section Ill, we get the following formulas: HAS-SLOT (Car,Wheela,4) HAS-SLOT (Car,Seats,5) SPECIALIZES (Sport.scar,Car) HAS-SLOT (Sport.scar,Seats,2) HAS-SLOT (Sport.scar,Cylinders,8) IS(Speedy,Sport.scar) . HOLDS(Cylinders,Speedy ,8) Forall frame, value. IS(Speedy.frame) It HAS-SLOT(frame,Cylinders,value) It ~value= 8 -> EXCEPTIONAL(Speedy,Cylinders,frame) Circumscribing EXCEPTIONAL in this theory (allowing all predicates to vary) yields Forall x,y,z. EXCEPI'IONAL(x,y,z) <-> (x = Speedy 1: y = Seats 1: z = Car) v (x = Speedy 1: y = Cylinders 1: z = Sport.scar)
To derive interesting results we must assume, of course, that different names denote different objects (e.g. that cylinders and seats are not the same). But under the unique names assumption we get exactly the results we expect:
HOLDS(Wheela,Speedy,4) is derivable since Speedy is a Car and not EXCEPTIONAL with respect to Wheela and Car.
HOLDS(Seats,Speedy,2) can be derived since Speedy is not EXCEPTIONAL with respect to Seats and Sport.scar. EXCEPTIONAL(Speedy,Seats,Car) holds, however, so there are no inconsistencies.
HOLDS(Cylinders,Speedy,B) was asserted directly in the translation; there are no inconsistencies since EXCEPTIONAL(Speedy ,Cylinders,Sport.scar) holds.
V AMBIGUITIES
Up to now our formalization still admits different values for a slot inherited from different paths in the frame network. Usually such situations are inter preted as ambiguities and, as discussed in section II, the best thing to do in case of an ambiguity is to remain agnostic. It is very easy to achieve the desired behavior in our formalization, since circumscription does most of the job automatically. We simply have to add Forall slot,x,valuel,value2. HOLDS{slot,x,valuel) k HOLDS(slot,x,value2)
-> valuel = value2
With this additional formula we forbid slots having different values (of course, we could easily extend our frame language and distinguish between different types of slots, e .g. multi-valued and single-valued slots. In that case we should restrict the above impli cation to single-valued slots by introducing an addi tional condition).
Circumscription is a correct realization of minimal entailment. In our formalization ambiguities correspond to different minimal models. Since cir cumscription only allows to derive what is true in all minimal models, we get exactly what we want.
Let us assume we have a frame QUAKER with slot POLITICAlrVIEW and value PACD1SI'IC and a frame REPUBIJCAN with the same slot and value NON PACD1SI'IC. Let us also assume that none of the frames specializes the other. If NIXON is an instance of both frames, we have minimal models where HOLDS{POLITICAL-VIEW, NIXON, PACD1SI'IC) is true and HOLDS{POLITICAL-VIEW, NIXON, NON-PACD1SI'IC) false. But there also exist minimal models which make the first formula false and the second true. Circumscrip tion only allows to derive the disjunction of both for mulas but does not favour one of them.
VI FUTURE WORK AND DISCUSSION
Many frame systems allow additional information to be associated with slots (often called facets) . For the sake of simplicity we did not deal with facets in this paper, but it is straightforward to extend our approach accordingly and to represent them as well. Sometimes the facets are given a special meaning in frame systems. For instance, a facet POSSIBLE VALUES of a slot could restrict the values that this slot may have. If, for Instance, the POSSmLE-VALUES facet of SLOT 1 of FRAIIE 1 has the value POS8-VAlr PRED, we can represent th1s as
Forall x, y.
IS{x,Fnune 1 ) k HOLDS{Slot 1 ,x,y) -> POS8-VAlrPRED(y)
Of course, POSS-VAirPRED has to be defined according to its intended meaning. In a more elaborate formali zation, also values representing unknown. or undeter mined need·special treatment (e.g. if they participate in ambiguities) . But there are no theoretical difficulties.
Inheritance in general is very hard to deal with. We have shown, however, that for simpler classes of inher itance systems quite natural logical representations exist. Of course, it would be tine to see how our for malization deals with Sandewall's structure types
[Sandewall 86) . Obviously, we cannot match the frame hierarchies definable in our frame language directly against Sandewall's examples since he admits only defeasible links (i.e. there is no guarantee that every royal elephant is an elephant) and we cannot represent chains of defeasible inferences. But for most of the examples an analogous representation in terms of frame hierarchies exists and we get the desired results. Let us discuss the example for which Touretzky's approach fails:

To represent this example in our language, we have to define Clyde as an instance of a frame RoyaWri canE!ephant which has RoyaiElephant and Afri canE!ephant as superframes. The last two frames each have the superframe Elephant. For RoyalElephant and Elephant a slot Color must be defined with value Non Gray and Gray respectively. Now our formalization yields exactly what we expect, i.e. HOLDS(Color, Clyde, . Non-Gray).
We have defined the semantics of a frame system with exceptions by means of circumscribing a certain predicate in a first order theory. Our approach for malizes the intuition that subclasses and only sub classes should override superclasses in a very natural way. Expressions of our frame language can be translated independently from the translation of other expressions. Moreover we don't need a compli cated new mathematical apparatus. It should be men tioned, however, that most current implementations of frame systems (in fact all implementations I know of) are not correct with respect to the proposed seman tics since they favour one inheritance path instead of remaining agnostic in case of ambiguities.
ACKNOWLEDGEMENTS
Thanks to all members of our research group, espe cially Thomas Christaller, Tom Gordon, Joachim Hertzberg, Franco di Primio and Karl Wittur. Tom also helped to make this paper as English as possible. Of course, the paper totally depends on the fundamental work of John McCarthy. Without his ideas no part of it could have been written.
@inproceedings{ijcai1987p95,
title = {The Logic of Inheritance in Frame Systems},
author = {Brewka, Gerhard},
booktitle = {Proceedings of the Tenth International Joint Conference on
Artificial Intelligence, {IJCAI-87}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {John McDermott},
pages = {483--487},
year = {1987},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1987/95},
}
TY - CPAPER TI - The Logic of Inheritance in Frame Systems AU - Brewka, Gerhard T2 - Proceedings of the Tenth International Joint Conference on Artificial Intelligence, IJCAI-87 PB - International Joint Conferences on Artificial Intelligence PY - 1987 SP - 483 EP - 487 UR - https://ijcai.org/proceedings/1987/95 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards