Daniil Kozhemiachenko

Meghyn Bienvenu, Katsumi Inoue, Daniil Kozhemiachenko

We explore the problem of explaining observations starting from a classically inconsistent theory by adopting a paraconsistent framework. We consider two expansions of the well-known Belnap--Dunn paraconsistent four-valued logic $\mathsf{BD}$: $\mathsf{BD}_\circ$ introduces formulas of the form $\circφ$ (the information on $φ$ is reliable), while $\mathsf{BD}_\triangle$ augments the language with $\triangleφ$'s (there is information that $φ$ is true). We define and motivate the notions of abduction problems and explanations in $\mathsf{BD}_\circ$ and $\mathsf{BD}_\triangle$ and show that they are not reducible to one another. We analyse the complexity of standard abductive reasoning tasks (solution recognition, solution existence, and relevance / necessity of hypotheses) in both logics. Finally, we show how to reduce abduction in $\mathsf{BD}_\circ$ and $\mathsf{BD}_\triangle$ to abduction in classical propositional logic, thereby enabling the reuse of existing abductive reasoning procedures.

Meghyn Bienvenu, Camille Bourgaux, Daniil Kozhemiachenko

We present a novel approach to querying classical inconsistent description logic (DL) knowledge bases by adopting a~paraconsistent semantics with the four Belnapian values: exactly true ($\mathbf{T}$), exactly false ($\mathbf{F}$), both ($\mathbf{B}$), and neither ($\mathbf{N}$). In contrast to prior studies on paraconsistent DLs, we allow truth value operators in the query language, which can be used to differentiate between answers having contradictory evidence and those having only positive evidence. We present a reduction to classical DL query answering that allows us to pinpoint the precise combined and data complexity of answering queries with values in paraconsistent $\mathcal{ALCHI}$ and its sublogics. Notably, we show that tractable data complexity is retained for Horn DLs. We present a comparison with repair-based inconsistency-tolerant semantics, showing that the two approaches are incomparable.

Daniil Kozhemiachenko, Igor Sedlár

We explore a fuzzy modal logic that can formalise probabilistic reasoning about actions and knowledge. In particular, we deal with contexts involving statements about events expressed via modal formulas, e.g., "after doing $a$, the probability of $A$ knowing that $p$ holds increases / decreases / is equal to $0.25$", "according to $A$, $p$ is equally likely to happen after doing $a$ or $b$", etc. We define the semantics of the logic on Kripke frames equipped with probability measures. We analyse the complexity of deciding the satisfiability of formulas of our logic over finitely branching models, for the full language and its fragments of varying expressivity. In particular, we identify several fragments of our logic where satisfiability is decidable in polynomial time.

Tommaso Flaminio, Katsumi Inoue, Daniil Kozhemiachenko

We study the problem of explaining observations about the probabilities of events, such as "it rains $20\%$ of the time", "rain and snow are equally likely", etc. We explain these statements with a probability distribution or a statement about probabilities of (other) events that are consistent with our knowledge and entail the observation. We formalise this problem in a fuzzy probabilistic logic $\mathsf{FP}$. We define and motivate the notions of abduction problems and their solutions. Our main technical contribution is a comprehensive study of the complexity of solution recognition and existence for a given abduction problem in $\mathsf{FP}$ for the case of full language and its disjunctive-clause fragments. We also obtain a translation of classical probabilistic abduction (finding the most likely explanation of a given event) to $\mathsf{FP}$.