papiers NMR’10
Les papiers suivants ont été acceptés au 13th International Workshop on Non-Monotonic Reasoning (NMR’10), à Toronto, Canada:
Semantic Diff as the Basis for Knowledge Base Versioning
Enrico Franconi, Thomas Meyer and Ivan Varzinczak
Abstract:
In this paper we investigate the problem of maintaining and reasoning with different versions of a knowledge base. We are interested in the scenario where a knowledge base (expressed in some logical formalism) might evolve over the time and, as a consequence, different versions thereof have to be maintained simultaneously in a parsimonious way. Moreover, users of the knowledge base should be able to access, not only any specific version, but also the differences between two given versions of the knowledge base. We address this problem by proposing a general semantic framework for the maintenance of different versions of a knowledge base. It turns out that the notion of semantic difference between knowledge bases plays a central role in the framework. We show that an appropriate characterization produces a unique definition of semantic difference which is applicable to a large class of logic-based knowledge representation languages. We then proceed to restrict our attention to finitely generated propositional logics, and show that our semantic framework can be represented syntactically in a particular kind of normal form, referred to as ordered complete conjunctive normal form or oc-CNF. This is followed by a generalization in which we show that similar results can be obtained for any syntactic representation (in a finitely generated propositional logic) of the semantic framework. Of particular interest are representations of appropriately chosen normal forms. We expect that our constructions for the propositional case can be extended to more expressive languages, such as description logics (DLs). In that respect, our results add to the investigation of the versioning problem for DL-based ontologies.
Disponible en ligne ici.
Pertinent Reasoning
Katarina Britz, Johannes Heidema and Ivan Varzinczak
Abstract:
In this paper we venture beyond one of the fundamental assumptions in the non-monotonic reasoning community, namely that non-monotonic entailment is supra-classical. We investigate reasoning which uses an infra-classical entailment relation that we call pertinent entailment. The notion of pertinence proposed here is induced by a binary accessibility relation on worlds establishing a link (representing some form of pertinence) between premiss and consequence. We show that this notion can be captured elegantly using a simple modal logic without nested modalities. One road to infra-classicality has been studied extensively, that of substructural logics, which weaken the generating engine of axioms and inference rules for producing entailment pairs (X,Y). Here we follow an alternative strategy: we first demand that X entails Y classically, and then, with supplementary information provided by an accessibility relation, more, trimming down the set of entailment pairs to infra-classicality. It turns out that pertinent entailment restricts well-known ‘paradoxes’ avoided by relevance/relevant logic in an interesting way. We present its properties, showing that it possesses other non-classical properties, like strong non-explosiveness and non-monotonicity, and we discuss which inference rules traditionally considered in the literature it satisfies.
Disponible en ligne ici.
A Contraction Core for Horn Belief Change: Preliminary Report
Richard Booth, Thomas Meyer, Ivan Varzinczak and Renata Wassermann
Abstract:
In this paper we continue recent investigations into belief change for Horn logic. The main contribution is a result which shows that the construction method for Horn contraction for belief sets based on infra-remainder sets, as recently proposed by Booth et al, corresponds exactly to Hansson’s classical kernel contraction for belief sets, when restricted to Horn logic. This result is obtained via a detour through Horn contraction for belief bases during which we prove that kernel contraction for Horn belief bases produces precisely the same results as the belief base version of the Booth et al construction method. The use of belief bases to obtain the result provides evidence for the conjecture that Horn belief change is best viewed as a “hybrid” version of belief set change and belief base change. One of the consequences of the link with base contraction is the provision of a more elegant representation result for Horn contraction for belief sets in which a version of the Core-retainment postulate features. The paper focuses on Delgrande’s entailment-based contraction (e-contraction), but we also mention similar results for inconsistency-based contraction (i-contraction) and package contraction (p-contraction).
Disponible en ligne ici.