Camille Bourgaux
CNRS researcher at École Normale Supérieure (part of PSL University), France
Querying inconsistent prioritized data
Abstract: Real-world datasets are plagued by data quality issues which may render the data inconsistent w.r.t. a set of constraints, be they given by database dependencies or ontologies. A prominent way to handle such inconsistent data is to use inconsistency-tolerant semantics to obtain meaningful answers to queries. Most of these semantics are based on the notion of a (subset) repair, which is an inclusion-maximal subset of the data that is consistent with the constraints. In many scenarios, this basic notion of repair can be refined by exploiting preference information about facts. Preferred repairs can then be used in place of subset repairs in any repair-based semantics.
In this talk, I will present an approach where preferences are given by a binary priority relation between conflicting facts. I will first give some insights on the computational complexity of querying inconsistent prioritized data and on some practical SAT-based approaches to this problem. I will then discuss connections with other settings that use preferences to handle inconsistency.
Gabriele Kern-Isberner
Technical University of Dortmund, Germany
Ranking-based Semantics for Defeasible Subsumptions
Abstract: Defeasible subsumptions are kind of default rules aka conditionals, i.e., rules with exceptions, or rules that plausibly hold. Such rules have been explored in the area of nonmonotonic reasoning since the 80s of the past century, and a crucial insight from these studies is that semantically, it needs qualitative relations between possible worlds which express typicality, plausibility, possibility and the like, to provide solid logical semantics for default rules. However, most approaches here have focused on propositional logic only. In this talk, I present a semantics for first-order conditionals that is based on Spohn’s ranking functions which are particularly popular in the fields of nonmonotonic reasoning and belief revision because they provide representations of epistemic states which are both intuitive and powerful. So-called c-representations construct a ranking model from a first-order conditional belief base that yields high-quality nonmonotonic inferences. As a special feature of this approach, the qualitative relations between possible worlds which are mandatory to implement defeasible inferences are elaborated from the conditionals in the belief base, no external relations, e.g., expressing typicality among individuals need to be specified. This approach can also be applied to defeasible subsumptions in description logics, taking information from both (defeasible) TBox and ABox into account. Also connections to AGM-like revision will be illustrated.
Ondřej Kuželka
Czech Technical University in Prague, Czech Republic
Model Counting and Sampling in First-Order Logic
Abstract: First-order model counting (FOMC) asks to count models of a first-order logic sentence over a given set of domain elements. Its weighted variant, WFOMC, generalizes FOMC by assigning weights to the models and has applications among others in statistical relational learning. Several non-trivial classes of WFOMC problems that can be solved in time polynomial in the number of domain elements were identified in the literature over the past decade, since the two seminal paper by Van den Broeck (2011) and Van den Broeck, Meert and Darwiche (2014) established tractability of FO2 for WFOMC. This talk is about recent developments on WFOMC and the related problem of weighted first-order model sampling (WFOMS). We also discuss applications of WFOMC and WFOMS, such as automated solving of problems from enumerative combinatorics and elementary probability theory. Finally, I will also describe how WFOMS could be used as a basis for a declarative framework for sampling combinatorial structures beyond what is provided in libraries of mainstream programming languages.