Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-25T18:11:55.888Z Has data issue: false hasContentIssue false
  • English
  • Français

Research developments in multiple inheritance with exceptions

Published online by Cambridge University Press:  07 July 2009

Peter W. Eklund
Peter W. Eklund
Affiliation:
Department of Computer Science, The University of Adelaide, Adelaide 5005, Australia
Get access Rights & Permissions [Opens in a new window]

Abstract

The inheritance problem can be simply stated: for any instantiation of an inheritance network, say a specific hierarchy Γ, find a conclusion set for Γ. In other words, find out what is logically entailed by Γ. This can be done in two ways: either by defining a deductive or proof theoretic definition to determine what paths are entailed by a network; or by translating the individual links in the network to a more general nonmonotonic logic and using its model and proof theory to generate entailments that correspond to what one would expect from “viewing” the inheritance hierarchy. Two approaches to a solution to the inheritance problem structure this paper. The first is widely known as the “path-based” or “proof theoretic”, and the second, the “Model-based” or “model theoretic”. The two approaches result in both a different interpretation of default links as well as a variation in the entailment strategy for a solution to teh inheritance problem. In either case, the entailments produced need some intuitive interpretation, which can be either credulous or skeptical. The semantics of both skeptical and credulous inheritance reasoners are examined.

Type
Research Article
Information
The Knowledge Engineering Review , Volume 9 , Issue 1 , March 1994 , pp. 21 - 55
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bacchus, F, 1988. Representing and reasoning with probabilistic knowledge. PhD theseis, Department of Computer Science, University of Waterloo, Ontario, Canada.Google Scholar
Bacchus, F, 1989. “A modest, but semantically well founded, inheritance reasoner”. In: International Joint Conf. on Artificial Intelligence, pp 1104–1109.Google Scholar
Belnap, N, 1976. “How a computer should think”. In: Ryle, G (ed.), Contemporary Aspects of Philosophy, pp 30–55. Oriel Press.Google Scholar
Belnap, N, 1977. “A useful four valued logic”. In: Dunn, J and Epstein, G (eds.), Modern Uses of Multiple Valued Logic, pp 8–37. Reidel.Google Scholar
Bläsius, K, Hedück, U and Rollinger, C (eds.), 1990. Sorts and Types in Artificial Intelligence: Lectures Notes on AI Vol 418. Springer-Verlag.CrossRefGoogle Scholar
Boutilier, C, 1989. “A semantical approach to stable inheritance reasoning”. In: International Joint Conf. on Artificial Intelligence, 1134–1139.Google Scholar
Brachman, R, 1985. “I lied about the trees or defaults and definitions in knowledge representation”. AI Magazine, Fall 80–93.Google Scholar
Buchanan, B and Shortliffe, E, 1984. Rule-bases Expert Systems: The MYCIN Experiments. Reading, MA: Addison-Wesley.Google Scholar
Borgida, A and Williamson, K, 1985. “Accommodating exceptions in databases and refining the schema by learning from them”. In: Proceedings of VLDB. Stockholm.Google Scholar
Cross, C and Thomason, R, 1987. “Update and conditionals”. In: International Symposium on Methodologies for Intelligence Systems.Google Scholar
Doherty, P, 1989. “A correspondence between inheritance hierarchies and a logics of preferential entailment”. In: International Symposium on Methodologies for Intelligent Systems.Google Scholar
Doherty, P, 1991. NML: A nonmonotonic formalism with explicit defaults. Phd, Institutionen för Datavetenskap, University of Linköping.Google Scholar
Eklund, P, 1991. “Negotiating inheritance taxonomies in conceptual structures”. In: 3rd Scandinavian Conference on AI, pp 211–221. Roskilde, Denmark.Google Scholar
Etherington, D and Reiter, R, 1983. “On inheritance hierarchies with exceptions”. In: National Conference on Artificial Intelligence, pp 104–108.Google Scholar
Etherington, D, 1987a. “Formalizing nonmonotonic reasoning systems”. Artificial Intelligence 31 41–85.CrossRefGoogle Scholar
Etherington, D, 1987b. “More on inheritance hierarchies with exceptions”. In: National Conference on Artificial Intelligence, pp 352–357.Google Scholar
Etherington, D, 1988. Reasoning with Incomplete Information: Research Notes in AI. See Mateo, CA: Morgan-Kaufmann.Google Scholar
Fahlman, S, 1979. NETL: A System for Representing and Using Real-World Knowledge. Cambridge, MA: MIT Press.CrossRefGoogle Scholar
Lenzerini, M, Donini, F and Nardi, D, 1991. “Tractable concept languages”. In: International Joint Conf. on Artificial Intelligence, pp 458–463.Google Scholar
Froidevaux, C and Kayser, D, 1988. “Inheritance in semantic networks and default logicz”. In: Smets, P, Mamdani, E, Dubious, D and Prade, H (eds.), Non-Standard Logics for Automated Reasoning, pp 179–212. New York, NY: Academic Press.Google Scholar
Gabbay, D, 1985. “Theoretical foundations for non-monotonic reasoning in expert systems”. In: Krzysztof, R (ed), Logics and Models of Concurrent Systems, pp 439–457. Berlin: Springer-Verlag.CrossRefGoogle Scholar
Geffner, H, 1989. Default reasoning: Causal and conditional theories. PhD thesis, Cognitive Systems Laboratory, Department of Computer Science, UCLA, CA.Google Scholar
Ginsberg, M, 1990. “A local formalization of inheritance: Preliminary report”. In: 3rd International Workshop on Nonmonotonic Reasoning, pp 119–1292. Lake Tahoe, CA.Google Scholar
Gelfond, M and Przymusinska, H, 1990. “Formalization of inheritance reasoning in autoepistemic logic”. In: 3rd International Workshop on Nonmonotonic Reasoning, 73–107. Lake Tahoe, CA.Google Scholar
Gelfond, M and Przymusinska, H, 1990. “Formalization of inheritance reasoning in autoepistemic logic”. Fundamenta Informaticae 13 (4) 403–444.CrossRefGoogle Scholar
Geffner, H and Verma, T, 1989. “Inheritance = chaining + defeat”. In: International Symposium on Methodologies for Intelligent Systems.Google Scholar
Hägglund, S, 1989. “Iterative design and adaptive maintenance of knowledge-based office systems”. Office information Systems: The Design Process. Amsterdam: North-Holland.Google Scholar
Haugh, B, 1988. “Tractable theories of multiple defeasible inheritance in ordinary nonmonotonic logics”. In: National Conference on Artificial Intelligence, pp 421–426.Google Scholar
Hayes, P, 1977. “In defence of logic”. In: International Joint Conf. on Artificial Intelligence, pp 559–564.Google Scholar
Horty, J, 1990a. “A credulous theory of mixed inheritance”. In: Lenzerini, M (ed), Inheritance Hierarchies in Knowledge Representation. Chichester: Wiley.Google Scholar
Horty, J, 1990b. “A skeptical theory of mixed inheritance”. In: Dunn, J and Cupta, A (eds.), Truth or Consequences, pp 267–281. Amsterdam: Kluwer.CrossRefGoogle Scholar
Horty, J and Thomasen, R, 1988. “Mixing strict and defeasible inheritance”. In: National Conference on Artificial Intelligence, pp 427–432.Google Scholar
Horty, J, Thomason, R and Touretzky, D, 1990. “A skeptical theory of inheritance in nonmonotonic semantic networks”. Artificial Intelligence 42 311–348.CrossRefGoogle Scholar
Krishnaprasad, T and Kifer, M, 1989. “An evidence-based framework for a theory of inheritance”. In: International Joint Conf. on Artificial Intelligence, pp 1093–1098.Google Scholar
Krishnaprasad, T, Kifer, M and Warren, D, 1989. “On the declarative semantics of inheritance network”. In: International Joint Conf. on Artificial Intelligence, pp 1099–1103.Google Scholar
Krishnaprasad, T, 1989. The semantics of inheritance networks. Phd thesis, Department of Computer Science, State University of New York, Stony Brook, NY.Google Scholar
Loui, R, 1986. “Defeat among arguments: A system of defeasible inference”. Technical Report TR190, Department of Computer Science, University of Rochester.Google Scholar
McCarthy, J and Hayes, P, 1981. “Some philosophical problems from the standpoint of AI”. In: Webber, B L and Nilsson, N (eds.), Readings in AI, pp 431–451. Los Angeles, CA: Morgan Kaufmann.Google Scholar
Moore, R, 1988. “Autoepistemic logic”. In: Smets, P, Mamdani, E, Dubious, D and Prade, H (eds.), Non-Standard Logics for Automated Reasoning, pp 105–127. New York, NY: Academic Press.Google Scholar
Makinson, D and Schlechta, K, 1989. “Floating conclusions and zombie paths”. In: 2nd International Workshop on Nonmonotonic Reasoning, Sankt Augustin, FRG.Google Scholar
Makinson, D and Schlechta, K. 1991. “Floating conclusions and zombie paths: Two deep difficulties in the directly skeptical approach to defeasible inheritance nets”. 48 199–209.Google Scholar
Nebel, B, 1990. “Terminological reasoning is inherently intractable”. Artificial Intelligence 43 (2) 235–249.CrossRefGoogle Scholar
Padgham, I, 1988. “A model and representation for type information and its use in reasoning with defaults”. In: National Conference on Artificial Intelligence, pp 409–414.Google Scholar
Padgham, L, 1989a. “Negative reasoning using inheritance”. In: International Joint Conf. on Artificial Intelligence, pp 1086–1092.Google Scholar
Padgham, L, 1989b. Non-monotonic inheritance for an object-orientated knowledge-base. Phd thesis. Institutionen för datavetenskap, University of Linköping.Google Scholar
Pearl, J, 1987. “Deciding consistency in inheritance networks”. Technical Report CSD 870053: R96, UCLA.Google Scholar
Pearl, J, 1988. Probabilistic Reasoning in Intelligent Systems. San Mateo, CA: Morgan-Kaufman.Google Scholar
Poole, D, 1985. “On the comparison of theories: Preferring the most specific explanation”. In: International Joint Conf. on Artificial Intelligence, pp 144–150.Google Scholar
Patel-Scheider, P, 1989. “Undecidability of subsumption in nikl*”. Artificial Intelligence 39 263–271.CrossRefGoogle Scholar
Reiter, R and Crisuolo, G, 1981. “On interacting defaults”. In: International Joint Conf. on Artificial Intelligence, pp 270–276.Google Scholar
Reiter, R, 1980. “A logic for default reasoning”. AI Journal 13 81–132.Google Scholar
Sandewall, E, 1986. “Nonmonotonic inference rules for multiple inheritance with exception”. In: IEEE, pp 1345–1353.CrossRefGoogle Scholar
Schubert, L, 1976. “Extending the expressive power of semantic networks”. Artificial Intelligence 7 163–198.CrossRefGoogle Scholar
Schlechta, K, 1989. “Directly sceptical inheritance cannot capture the intersection of extension”. In: Workshop on Nonmonotonic Reasoning, Sankt Augustin, FRG.Google Scholar
Shoham, Y, 1988. Reasoning about Change. Cambridge, MA: MIT Press.Google Scholar
Selman, B and Kautz, H, 1988. “The complexity of model-preference default theories”. In: Reinfrank, M, de Kleer, J, Ginsberg, M and Sandewall, E (eds.), 2nd International Workshop on Nonmonotonic Reasoning, pp 115–130. Springer-Verlag. Grassau, FRG.Google Scholar
Lehmann, D, Kraus, S and Magidor, M. 1990. “Nonmonotonic reasoning, preferential models and cumulative logics”. 44 167–207.Google Scholar
Selman, B and Levesque, H, 1989. “The tractibility of path-based inheritance”. In: International Joint Conf on Artificial Intelligence, pp 1140–1145.Google Scholar
Stein, LA, 1989. “Skeptical inheritance: Computing the intersection of credulous extensions”. In: International Joint Conf. on Artificial Intelligence, pp 1153–1158.Google Scholar
Stein, I, 1990. “A preference-based approach to inheritance”. In: 3rd International Workshop on Nonmonotonic Reasoning, pp 233–245. Lake Tahoe, CA.Google Scholar
Thomason, R, Horty, J and Touretzky, D, 1987. “A calculus for inheritance in monotonic semantic nets”. In: International Symposium on Methodologies for Intelligent Systems, pp 282–287. Elsevier.Google Scholar
Touretzky, D, Horty, J and Thomason, R, 1987. “A clash of intuitions: The current state of nonmonotonic multiple inheritance systems”. In: International Joint Conf. on Artificial Intelligence, pp 476–482.Google Scholar
Touretzky, D, Horty, J and Thomason, R, 1987. “A skeptical theory of inheritance in nonmonotonic semantic networks”. In: National Conference on Artificial Intelligence, pp 358–363.Google Scholar
Touretzky, D, 1984a. “Implicit ordering of defaults in inheritance systems”. In: International Joint Conf. on Artificial Intelligence, pp 322–325.Google Scholar
Touretzky, D, 1984b. “The mathematics of inheritance systems”. Technical Report CMU-CS-84–136, CMU.Google Scholar
Touretzky, D, 1986. The Mathematics of Inheritance Systems: Research Notes in Al. San Mateo, CA: Morgan-Kaufmann.Google Scholar
Touretzky, D and Thomason, R, 1988. “Nonmonotonic inheritance and generic reflexives”. In: National Conference on Artificial Intelligence, pp 433–438.Google Scholar
Thomason, R and Touretzky, D, 1990. “Inheritance theory and networks with roles”. Technical Report CMU-CS-90–139, CMU.Google Scholar