KR2021Proceedings of the 18th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning

Online event. November 3-12, 2021.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-99-7

Sponsored by
Published by

Copyright © 2021 International Joint Conferences on Artificial Intelligence Organization

Unfounded Sets for Disjunctive Hybrid MKNF Knowledge Bases

  1. Spencer Killen(University of Alberta)
  2. Jia-Huai You(University of Alberta)


  1. Computational aspects of knowledge representation
  2. Logic programming, answer set programming


Combining the closed-world reasoning of answer set programming (ASP) with the open-world reasoning of ontologies broadens the space of applications of reasoners.

Disjunctive hybrid MKNF knowledge bases succinctly extend ASP and in some cases without increasing the complexity of reasoning tasks. However, in many cases, solver development is lagging behind.

As the result, the only known method of solving disjunctive hybrid MKNF knowledge bases is based on guess-and-verify, as formulated by Motik and Rosati in their original work.

A main obstacle is understanding how constraint propagation may be performed by a solver, which, in the context of ASP, centers around the computation of \textit{unfounded atoms}, the atoms that are false given a partial interpretation.

In this work, we build towards improving solvers for hybrid MKNF knowledge bases with disjunctive rules:

We formalize a notion of unfounded sets for these knowledge bases, identify lower complexity bounds, and demonstrate how we might integrate these developments into a DPLL-based solver.

We discuss challenges introduced by ontologies that are not present in the development of solvers for disjunctive logic programs, which warrant some deviations from traditional definitions of unfounded sets.

We compare our work with prior definitions of unfounded sets.