Grounded Fixpoints

Authors

  • Bart Bogaerts KU Leuven
  • Joost Vennekens KU Leuven
  • Marc Denecker KU Leuven

DOI:

https://doi.org/10.1609/aaai.v29i1.9388

Keywords:

Approximation Fixpoint Theory, Lattice operator, Stable semantics, Well-founded semantics, Groundedness

Abstract

Algebraical fixpoint theory is an invaluable instrument for studying semantics of logics. For example, all major semantics of logic programming, autoepistemic logic, default logic and more recently, abstract argumentation have been shown to be induced by the different types of fixpoints defined in approximation fixpoint theory (AFT). In this paper, we add a new type of fixpoint to AFT: a grounded fixpoint of lattice operator O : L → L is defined as a lattice element x ∈ L such that O(x) = x and for all v ∈ L such that O(v ∧ x) ≤ v, it holds that x ≤ v. On the algebraical level, we show that all grounded fixpoints are minimal fixpoints approximated by the well-founded fixpoint and that all stable fixpoints are grounded. On the logical level, grounded fixpoints provide a new mathematically simple and compact type of semantics for any logic with a (possibly non-monotone) semantic operator. We explain the intuition underlying this semantics in the context of logic programming by pointing out that grounded fixpoints of the immediate consequence operator are interpretations that have no non-trivial unfounded sets. We also analyse the complexity of the induced semantics. Summarised, grounded fixpoint semantics is a new, probably the simplest and most compact, element in the family of semantics that capture basic intuitions and principles of various non-monotonic logics.

 

Downloads

Published

2015-02-18

How to Cite

Bogaerts, B., Vennekens, J., & Denecker, M. (2015). Grounded Fixpoints. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9388

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning