A Finite Abstraction of Real-Valued Functions for Complete Reasoning About Influence

Sören Möller, Florian Bruse, Martin LangeFroCoS 2025 · DOI

Introduction

In natural science education, students frequently reason about chains of influence. For instance, a student might hypothesize that "as altitude increases, air pressure decreases, which in turn decreases oxygen saturation." To develop digital tools capable of automatically grading such hypotheses or simulating experiments, a formal logic is required to handle these qualitative yet mathematically grounded statements.

This paper addresses the challenge of reasoning about continuous real-valued functions ($f: \mathbb{R} \to \mathbb{R}$) that model these influences. Because there are uncountably many such functions, determining if a hypothesis follows from a set of observations (a "scheme") is traditionally difficult. Previous proof systems, such as the Calculus of Influence, were incomplete—they could not prove every true statement within the logic.

Figure 1: An influence chain showing how altitude (Alt) affects air pressure (AP), which then affects oxygen saturation (Ox). The third graph shows the resulting direct influence of Alt on Ox.

The Algebraic Abstraction Approach

The authors propose a shift from proof rules to an algebraic abstraction. The core insight is that the exact values of a continuous function are less important than its behavior relative to specific "boundary points" defined by the experimental setup.

To achieve a complete decision procedure, the authors introduce a method to partition the infinite space of possible functions into a finite set of equivalence classes. This process involves identifying "Points of Interest" (PoI):

  1. Boundary Points: Values explicitly mentioned in the problem (e.g., altitude intervals).
  2. Turning Points: Values that arise when functions are composed. For a chain $A \to B \to C$, a turning point is an input for the first function that results in a boundary value for the second.
  3. Inductive Propagation: These points are propagated forward and backward through the variable chain to ensure no critical transitions are missed.
Figure 5: A function discretized using points of interest (x, y) between boundary points (1, 2), illustrating the finite abstraction of continuous behavior.

By focusing only on these PoIs, the continuous search problem is transformed into a discrete combinatorial one. If a hypothesis holds for a single representative function within an equivalence class, it holds for all functions in that class.

Key Insights and Results

A critical component of this reasoning is the Coherence Constraint. In any influence chain, the influence of the first variable on the last must be the exact composition of the intermediate functions ($f_{A,C} = f_{B,C} \circ f_{A,B}$). The paper proves that their finite abstraction is "faithful," meaning it preserves all necessary logical information during discretization.

The primary result is the first complete decision procedure for this logic. The authors demonstrate that the problem of SchemeEntailment—deciding if a hypothesis is a logical consequence of a scheme—is decidable and resides within the coNP complexity class. For "flat" schemes (where variables do not form long chains), the problem can even be solved in polynomial time.

Limitations and Future Directions

While providing a significant theoretical leap, the model currently has restrictions:

  • Interval Bounds: Bounds must be finite, though large numbers can approximate infinity.
  • Scheme Behavior: Observations are limited to monotonic, antitonic, or constant behaviors, which, while common in science, is a mathematical constraint.
  • Single-Variable Influence: The logic does not yet support multi-variable influences, such as a chemical reaction requiring both a substrate and a co-factor.

Future work will focus on implementing this reasoner within educational software, potentially leveraging SMT solvers to navigate the discrete search space efficiently.

Summary updated

BibTeX
@inproceedings{moller2025finite,
  author = {Sören Möller and Florian Bruse and Martin Lange},
  title = {{A Finite Abstraction of Real-Valued Functions for Complete Reasoning About Influence}},
  booktitle = {FroCoS},
  year = {2025},
  doi = {10.1007/978-3-032-04167-8\_19},
}
Figure