Approximation Fixpoint Theory with Refined Approximation Spaces

Linde Vanbesien, Bart Bogaerts, Marc Denecker · 2025

Read Approximation Fixpoint Theory with Refined Approximation Spaces by Linde Vanbesien, Bart Bogaerts, Marc Denecker (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16294.txt.

Introduction

Logicians who study how computers reason with changing facts rely on a framework called Approximation Fixpoint Theory. Linde Vanbesien, Bart Bogaerts, and Marc Denecker wrote this 2025 paper to fix a known weak point in that framework. In the standard version, rough estimates of truth are handled as simple ranges between a low and a high value.

Ranges work for many systems, such as logic programs and answer set programs, but they fail on some simple cases. The authors widen the method so estimates can take richer shapes than plain ranges. They call these wider settings refined approximation spaces. The paper shows what the wider settings can express, and it maps how the different settings relate to each other.

Catalog record

CREATORLinde Vanbesien, Bart Bogaerts, Marc Denecker
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-16294

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Approximation Fixpoint Theory with Refined Approximation Spaces Linde Vanbesien, Bart Bogaerts, Marc Denecker Abstract Approximation Fixpoint Theory (AFT) is a powerful theory covering various semantics of non-monotonic reasoning formalisms in knowledge representation such as Logic Programming and Answer Set Programming. Many semantics of such non-monotonic formalisms can be characterized as suitable fixpoints of a non-monotonic operator on a suitable lattice. Instead of working on the original lattice, AFT operates on intervals in such lattice to approximate or construct the fixpoints of interest. While AFT has been applied successfully across a broad range of non-monotonic reasoning formalisms, it is confronted by its limitations in other, relatively simple, examples. In this paper, we overcome those limitations by extending consistent AFT to deal with approximations that are more refined than intervals. Therefore, we introduce a more general notion of approximation spaces, showcase the improved expressiveness and investigate relations between different approximation spaces. 1 Introduction Approximation Fixpoint Theory (AFT), introduced by ? ( ? ), is a comprehensive constructive framework covering various semantics for non-monotonic reasoning formalisms in knowledge representation. In such reasoning formalisms, it is common practice and often very natural to associate a semantic operator on a lattice ( the exact lattice ) with a theory (or program). In case this operator is monotonic, the semantics will typically coincide with the least fixpoint of the operator. However, in general, the semantic operator is not monotonic. This obfuscates the link between the intended semantics of the theory and the semantic operator. In fact, for many non-monotonic reasoning formalisms, different (disagreeing) semantics exist. This is where AFT comes in. Instead of the semantic operator, it uses an approximating operator and reduces different proposed semantics to different types of fixpoints of this approximating operator. As the name suggests, the approximating operator operates on an approximation space , i.e., it maps approximations of exact elements to other approximations. Essentially, an approximating operator uses approximations to approximate the behavior of the semantic operator. Following its original introduction, AFT uses pairs of elements in the exact space as approximations. Such pairs can be thought of as intervals, therefore we will refer to this version of AFT as interval-AFT. The semantics captured by AFT include the supported, Kripke-Kleene, stable and the well-founded semantics. It has been shown that AFT is able to grasp multiple non-monotonic reasoning formalisms, including (higher order) Logic Programming [ 2001 , 2018 ] , auto-epistemic and default logic [ 2003 ] , and argumentation frameworks and abstract dialectal frameworks [ 2013 , 2019 ] . Extending Consistent AFT In this paper, we develop a generalization of consistent AFT in which the elements of the approximation space need not necessarily be pairs/intervals, but more general approximations are allowed. Our new theory is a true generalization of consistent AFT: when instantiated with pairs as approximations, it reduces to the standard definitions of ? ( ? ). Our generalization is motivated by examples from auto-epistemic reasoning and abstract argumentation (more specifically weighted abstract dialectic frameworks [ 2018 ] , which we discuss next. Motivating Example from AEL It has been argued that logic programming under well-founded model semantics can be understood as a logic of inductive definitions [ 2014 ] . In this, AFT’s well-founded fixpoint construction constructs the relations inductively defined by the program. ? ( ? ) claim that for such definitional programs, the well-founded model will always identify the defined set. In the application of AFT for auto-epistemic logic (AEL), the well-founded fixpoint construction does not construct sets, but a belief state. Example 1 (First published by ? ( ? )) . Consider the following auto-epistemic theory: \mathcal{T}=\left\{\begin{array}[]{c}\mathit{q}\Leftrightarrow\neg K\mathit{p}.\\ \mathit{r}\Leftrightarrow\neg K\mathit{q}.\end{array}\right\}. This theory is seen as the theory of a rational, epistemic agent with introspection, whose knowledge base does not only contain objective facts of the world, but also propositions about what it knows or does not know. E.g., suppose the above theory would contain the objective fact ‘ p. ’ then the agent would know p , Kp would be true, and according to the agents theory, q would be false, which in turn would lead to r being true according to the theory. But as it happens, the theory does not contain objective information about p , hence the agent does not know p , meaning that Kp is false, and hence q is true, and further down the road, r is false. This is the belief state of the agent: nothing is known about p , but q and \neg r are known to be true. This at least is the intended belief state of this theory. ? ( ? ) explain how the well-founded semantics fails for this example. In fact, it is not able to derive any information. The well-founded model is the least precise approximation, i.e., the approximation that approximates all considered interpretations. Therefore, the authors stated that AFT is not strong enough for some auto-epistemic theories and they proposed an alternative method to determine the semantics of those theories using the concept of well-founded sets. This is a powerful ad-hoc algebraic method that is able to find the expected model of theories of this kind. Intuitively, in that paper, arbitrary sets of elements are used as approximations and a powerful algebraic method is defined that can identify the intuitive model in (a class of theories generalizing) the above example. In this paper, on the other hand, we show that the standard methods of AFT suffice, provided we generalize them to a richer approximation space. Motivating Example from wADFs Likewise, ? ( ? ) discusses how AFT can be used to successfully capture a broad range of weighted abstract dialectical frameworks (wADFs), which were introduced by ? ( ? ). In essence, wADFs are systems that represent knowledge on how different arguments influence each other, i.e., arguments can attack and support one another, possibly by joint attacks or support. An interpretation of a wADF then assigns an acceptance value to every argument which represents the degree to which an argument is accepted. Naturally, this requires an acceptance order \leq_{a} on the set of possible acceptance values. Due to the fact that AFT uses intervals as approximations, ? ( ? ) had to pose restrictions on the acceptance order. In particular, in order to have a least precise approximation, there needs to be a ‘least precise’ upper bound, i.e., a greatest element with respect to the acceptance order. On the other hand, ? ( ? ) allows multiple \leq_{a} -maximal acceptance values. In other words, interval-AFT requires the exact space to be a complete lattice, whereas not every problem naturally satisfies this constraint. Example 2 (Corresponding to Example 3.2 as introduced by ? ( ? )) . Consider the following wADF: paper’s status paper’s significance scientific methodology (a) A simple wADF illustrating how the status of a paper depends on its significance and the used methodology. accept borderline reject tendency accept tendency reject indifferent (b) The acceptance values under \leq_{a} . The wADF states that the status of a paper is jointly supported by its significance and the used scientific methodology. Therefore, the value for the status of the paper will be the greatest value that is compatible with the

Read the complete text