Ivan José Varzinczak online

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.

Next Steps in Propositional Horn Contraction.
Papier accepté à la 21st International Joint Conference on Artificial Intelligence (IJCAI’2009), à Pasadena, EUA, juillet 2009. Travail en collaboration avec Richard Booth et Thomas Meyer.

Résumé:
Standard belief contraction assumes an underlying logic containing full classical propositional logic, but there are good reasons for considering contraction in less expressive logics. In this paper we focus on Horn logic. In addition to being of interest in its own right, our choice is motivated by the use of Horn logic in several areas, including ontology reasoning in description logics. We consider three versions of contraction: entailment-based and inconsistency-based contraction (e-contraction and i-contraction, resp.), introduced by Delgrande for Horn logic, and package contraction (p-contraction), studied by Fuhrmann and Hansson for the classical case. We show that the standard basic form of contraction, partial meet, is too strong in the Horn case. We define more appropriate notions of basic contraction for all three types above, and provide associated representation results in terms of postulates. Our results stand in contrast to Delgrande’s conjectures that orderly maxichoice is the appropriate contraction for both e- and i-contraction. Our interest in p-contraction stems from its relationship with an important reasoning task in ontological reasoning: repairing the subsumption hierarchy in EL. This is closely related to p-contraction with sets of basic Horn clauses (Horn clauses of the form p implies q). We show that this restricted version of p-contraction can also be represented as i-contraction.

Disponible en ligne ici.