Ivan José Varzinczak online

Os seguintes artigos foram aceitos para apresentação no 13th International Workshop on Non-Monotonic Reasoning (NMR’10), em Toronto, Canadá:

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.

Texto integral disponível online aqui.

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.

Texto integral disponível online aqui.

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).

Texto integral disponível online aqui.

On Action Theory Change.
Artigo aceito para publicação no Journal of Artificial Intelligence Research (JAIR).

Abstract:
As historically acknowledged in the Reasoning about Actions and Change community, intuitiveness of a logical domain description cannot be fully automated. Moreover, like any other logical theory, action theories may also evolve, and thus knowledge engineers need revision methods to help in accommodating new incoming information about the behavior of actions in an adequate manner. The present work is about changing action domain descriptions in multimodal logic. Its contribution is threefold: first we revisit the semantics of action theory contraction proposed in previous work, giving more robust operators that express minimal change based on a notion of distance between Kripke-models. Second we give algorithms for syntactical action theory contraction and establish their correctness with respect to our semantics for those action theories that satisfy a principle of modularity investigated in previous work. Since modularity can be ensured for every action theory and, as we show here, needs to be computed at most once during the evolution of a domain description, it does not represent a limitation at all to the method here studied. Finally we state AGM-like postulates for action theory contraction and assess the behavior of our operators with respect to them. Moreover, we also address the revision counterpart of action theory change, showing that it benefits from our semantics for contraction.

A sair em 2010. Texto completo disponível aqui.

Ivan is co-chair of the Commonsense and Nonmonotonic Reasoning for Ontologies sub-workshop of NMR’2010. Collocated with KR’2010. May 14-16 2010, Sutton Place, Toronto, Canada.

Submission deadline: Jan 29, 2010
Workshop: May 14-16, 2010

For more details please check the workshop website.

Next Steps in Propositional Horn Contraction.
Artigo aceito para publicação na 21st International Joint Conference on Artificial Intelligence (IJCAI’2009), em Pasadena, EUA, julho de 2009. Trabalho conjunto com Richard Booth e Thomas Meyer.

Resumo:
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.

Texto integral disponível online aqui.