Logic Journal of IGPL Advance Access originally published online on November 14, 2008
Logic Journal of IGPL 2009 17(1):1-54; doi:10.1093/jigpal/jzn021
Defeasible inheritance systems and reactive diagrams*
Laboratoire d'Informatique Fondamentale de Marseille ¶
Inheritance diagrams are directed acyclic graphs with two types of connections between nodes: x 
y (read x is a y) and x 
y (read as x is not a y). Given a diagram D, one can ask the formal question of "is there a valid (winning) path between node x and node y?" Depending on the existence of a valid path we can answer the question "x is a y" or "x is not a y".
The answer to the above question is determined through a complex inductive algorithm on paths between arbitrary pairs of points in the graph.
This paper aims to simplify and interpret such diagrams and their algorithms. We approach the area on two fronts.
(1)
Suggest reactive arrows to simplify the algorithms for the winning paths.
(2)
We give a conceptual analysis of (defeasible or nonmonotonic) inheritance diagrams, and compare our analysis to the "small" and "big sets" of preferential and related reasoning.
In our analysis, we consider nodes as information sources and truth values, direct links as information, and valid paths as information channels and comparisons of truth values. This results in an upward chaining, split validity, off-path preclusion inheritance formalism of a particularly simple type.
We show that the small and big sets of preferential reasoning have to be relativized if we want them to conform to inheritance theory, resulting in a more cautious approach, perhaps closer to actual human reasoning.
We will also interpret inheritance diagrams as theories of prototypical reasoning, based on two distances: set difference, and information difference.
We will see that some of the major distinctions between inheritance formalisms are consequences of deeper and more general problems of treating conflicting information.
It is easily seen that inheritance diagrams can also be analysed in terms of reactive diagrams - as can all argumentation systems.
AMS Classification: 68T27, 68T30
Received for publication 15 March 2007.
Dov.Gabbay{at}kcl.ac.uk, www.dcs.kcl.ac.uk/staff/dg
Department of Computer Science, King's College London, Strand, London WC2R 2LS, UK
ks{at}cmi.univ-mrs.fr, karl.schlechta{at}web.de, http://www.cmi.univ-mrs.fr/~ks
¶UMR 6166, CNRS and Université de Provence, Address: CMI, 39, rue Joliot-Curie, F-13453 Marseille Cedex 13, France
References
-
[ABK07] Avron A, Ben-Naim J, Konikowska B. "Cut-free ordinary sequent calculi for logics having generalized finite-valued semantics". In: Journal Logica Universalis, to appear.
[Ant05] Antonelli A. "Grounded consequence for defeasible reasoning". (2005) Cambridge University Press.
[Ant97] Antonelli A. "Defeasible inheritance on cyclic networks". In: Artificial Intelligence. (1997) vol. 92:1–23.[CrossRef][Web of Science]
[Ant99] Antonelli A. "A directly cautious theory of defeasible consequence for default logic via the notion of general extensions". In: Artificial Intelligence. (1999) vol. 109:71–109.[CrossRef][Web of Science]
[BB94] Ben-David Shai, Ben-Eliyahu R. "A modal logic for subjective default reasoning". In: Proceedings LICS-94. (1994).
[BGH95] Barwise J, Gabbay D, Hartonas C. "On the Logic of Information Flow". In: Journal of the IGPL. (1995) Vol. 3.1.
[FH98] Friedman N, Halpern J. "Plausibility measures and default reasoning". In: IBM Almaden Research Center Tech.Rept. (1995) to appear in Journal of the ACM.
[GV89] Geffner H, Verma T. "Inheritance= Chaining+Defeat". (1989) UCLA Technical Report CSD-890039, R–129–L, June 1989, also in: Proceed. Fourth International Symposium on Methodologies for Intelligent Systems: North Holland. 411–418.
[Gab04] Gabbay DM. "Reactive Kripke semantics and arc accessibility". In: Proceedings CombLog04.—Carnielli W, Dionesio FM, Mateus P, eds. (2004) 7–20. Centre of Logic and Computation, University of Lisbon.
[Gab08b] Gabbay DM. "Reactive Kripke semantics and arc accessibility". In: In Pillars of Computer Science: Essays dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday.—Avron A, Dershowitz N, Rabinovich A, eds. (2008) 292–341. LNCS, vol. 4800, Springer, Berlin.
[Gab08c] Gabbay DM. "Logical modes of attack in argumentation networks". in preparation.
[HTT87] Horty JF, Thomason RH, Touretzky DS. "A Sceptical Theory of Inheritance in Nonmonotonic Semantic Networks". Dept. Comp. Sci. Carnegie Mellon Univ. CMU-CS-87-175, October 1987 also in: Proceedings AAAI-87 (1987), p.358–363 or: Artificial Intelligence 42 (1990), p.311–348.
[KK89] Krishnaprasad T, Kifer M. "An Evidence-based Framework for a Theory of Inheritance". In: Proceed. IJCAI 89. 1093–1098.
[KKW89a] Krishnaprasad T, Kifer M, Warren D. "On the Circumscriptive Semantics of Inheritance Networks". In: Proceed. Fourth International Symposium on Methodologies for Intelligent Systems. (1989) North Holland. 448–456.
[KKW89b] Krishnaprasad T, Kifer M, Warren D. "On the Declarative Semantics of Inheritance Networks". In: Proceed. IJCAI 89. 1098–1103.
[KLM90] Kraus S, Lehmann D, Magidor M. "Nonmonotonic reasoning, preferential models and cumulative logics". In: Artificial Intelligence. (1990) July;44((1–2)):167–207.[CrossRef][Web of Science]
[LMS01] Lehmann D, Magidor M, Schlechta K. "Distance Semantics for Belief Revision". In: Journal of Symbolic Logic. (2001) March;Vol.66(No. 1):295–317.[CrossRef][Web of Science]
[MS91] Makinson D, Schlechta K. "Floating Conclusions and Zombie Paths". In: Artificial Intelligence (Research Note) 48. (1991) 199–209.
[Mor98] Morgenstern L. "Inheritance comes of age: applying nonmonotonic techniques to problems in industry". In: Artificial Intelligence. (1998) vol. 103:1–34.[CrossRef][Web of Science]
[SL89] Selman B, Levesque H. "The Tractability of Path-Based Inheritance". In: Proceed. IJCAI. (1989) 1140–1145.
[San86] Sandewall E. "Non-monotonic inference rules for multiple inheritance with exceptions". In: Proceedings IEEE 74. (1986) 1345–1353.
[Sch04] Schlechta K. "Coherent Systems". (2004) Amsterdam: Elsevier.
[Sch90] Schlechta K. "Semantics for Defeasible Inheritance". Aiello LG, ed. (1990) "Proceedings ECAI 90": London. 594–597.
[Sch93] Schlechta K. "Directly Sceptical Inheritance cannot Capture the Intersection of Extensions". In: Journal of Logic and Computation. (1995) Vol.3(No.5). Oxford. 455–467.[CrossRef]
[Sch95-1] Schlechta K. "Defaults as generalized quantifiers". In: Journal of Logic and Computation. (1995) Vol.5(No.4). Oxford. 473–494.
[Sch97-2] Schlechta K. "Nonmonotonic logics - Basic Concepts, Results, and Techniques". In: Springer Lecture Notes series, LNAI 1187. (1997) Jan. 243.
[Sch97-4] Schlechta K. "Filters and partial orders". In: Journal of the Interest Group in Pure and Applied Logics. (1997) Vol. 5(No. 5):753–772.
[THT87] Touretzky DS, Horty JF, Thomason RH. "A Clash of Intuitions: The Current State of Nonmonotonic Multiple Inheritance Systems". In: Proceed. IJCAI. (1987) 476–482.
[Tou84] Touretzky DS. "Implicit Ordering of Defaults in Inheritance Systems". In: Proceed. AAAI 84. 322–325.
[Tou86] Touretzky DS. "The Mathematics of Inheritance Systems". (1986) Los Altos/ London.
CiteULike 
Connotea 
Del.icio.us What's this?
| ||||||||||||||||||||||||||||||||||||||||||||||||||