Defeasible inheritance systems and reactive diagrams

Inheritance diagrams are directed acyclic graphs with two typesof 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 formalquestion of "is there a valid (winning) path between node xand node y?" Depending on the existence of a valid path we cananswer the question "x is a y" or "x is not a y". The answer to the above question is determined through a complexinductive algorithm on paths between arbitrary pairs of pointsin the graph. This paper aims to simplify and interpret such diagrams andtheir algorithms. We approach the area on two fronts. (1) Suggest reactive arrows to simplify the algorithms for the winningpaths. (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 andtruth values, direct links as information, and valid paths asinformation channels and comparisons of truth values. This resultsin an upward chaining, split validity, off-path preclusion inheritanceformalism of a particularly simple type. We show that the small and big sets of preferential reasoninghave to be relativized if we want them to conform to inheritancetheory, resulting in a more cautious approach, perhaps closerto actual human reasoning. We will also interpret inheritance diagrams as theories of prototypicalreasoning, based on two distances: set difference, and informationdifference. We will see that some of the major distinctions between inheritanceformalisms are consequences of deeper and more general problemsof treating conflicting information. It is easily seen that inheritance diagrams can also be analysedin terms of reactive diagrams - as can all argumentation systems. AMS Classification: 68T27, 68T30 Received for publication 15 March 2007.