💻 computer science

Knowledge on a Budget

This paper introduces semiring-annotated topological spaces to extend Topological Evidence Logic with resource-indexed modalities, enabling the formal reasoning of epistemic states under specific time, memory, or energy budget constraints while providing sound and strongly complete axiomatizations.

Original authors: Ondrej Majer, Krishna Manoorkar, Wolfgang Poiger, Igor Sedlár

Published 2026-04-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ondrej Majer, Krishna Manoorkar, Wolfgang Poiger, Igor Sedlár

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Knowledge Isn't Free

Imagine you are trying to solve a mystery. In many traditional logic puzzles, finding a clue is magic: you just "know" it, and it costs you nothing. You don't need time, you don't need money, and you don't need energy.

But in the real world, knowledge costs something.

To check a database, you need time.
To access a secure file, you need permissions (like a security clearance).
To drive a robot to a location, you need battery power.
To ask a group of friends for the truth, you need social capital.

This paper argues that standard logic is too "idealistic" because it ignores these costs. The authors want to build a new kind of logic that asks: "Can I afford to know this?"

The New Tool: "Seats" (Semiring-Annotated Topological Spaces)

To solve this, the authors invented a mathematical structure they call a "Seat" (short for Semiring-Annotated Topological Space). That sounds scary, so let's break it down with a metaphor.

1. The Map (Topology)

Imagine a giant map of a city. In this city, "knowledge" is represented by neighborhoods (open sets).

If you are in a specific neighborhood, you know certain things about that area.
If a neighborhood is "dense," it means it overlaps with almost every other possible neighborhood, making it a very strong, reliable piece of evidence.

2. The Price Tag (Semiring)

Now, imagine every neighborhood on this map has a price tag.

Some neighborhoods are free (like looking out your window).
Some cost $5 (like buying a coffee to get a tip).
Some cost "Security Clearance Level 5" (like accessing a government vault).

The authors use a mathematical tool called a Semiring to handle these price tags. Think of a semiring as a flexible currency system. It doesn't just handle dollars; it can handle:

Time: (Minutes)
Permissions: (Roles like "Manager" or "Admin")
Energy: (Battery percentage)
Complexity: (How hard a math proof is)

The "Semiring" rules tell you how to combine costs.

Example: If I need "Time" AND "Money" to get a clue, the cost is the combination of both.
Example: If I can get a clue using "Time" OR "Money," the cost is whichever is cheaper.

3. The "Seat"

A Seat is simply the Map + The Price Tags. It tells you not just what you can see, but what you can afford to see with your current budget.

How It Works in Real Life (The Analogies)

The paper uses four main examples to show how this works:

1. The Streaming Video (Time Budget)

Scenario: You are watching a live video stream.
The Logic: To know what happens at minute 10, you have to wait 10 minutes.
The Seat: Your "budget" is time. You can only access evidence (the video) if your time budget is greater than the length of the clip. If you only have 5 minutes, you can't "know" what happens at minute 10.

2. The Office Database (Permission Budget)

Scenario: A company database where different employees have different roles (HR, Manager, Intern).
The Logic: You can only see certain files if your role matches the file's security level.
The Seat: Your "budget" is your job title. You can't just "see" the file; you must "pay" with the correct security clearance. If you are an Intern, you can't afford the "Manager" evidence.

3. The Robot Explorer (Battery Budget)

Scenario: A robot exploring a maze.
The Logic: The robot can only see what is within its battery range.
The Seat: The "budget" is battery life. If the maze is too big, the robot runs out of power before it finds the treasure. It can't claim to "know" the treasure exists because it couldn't afford the trip.

4. The Group Chat (Social Budget)

Scenario: A group of agents trying to figure out the truth.
The Logic: To know something, a specific group of people must pool their information.
The Seat: The "budget" is the size of the group. A single person might not have enough info, but a group of 5 might. The cost is the effort to coordinate that many people.

The Main Results: What Did They Prove?

The authors didn't just come up with a cool idea; they built a rigorous mathematical system around it.

They wrote the rules (Axioms): They created a set of logical rules (like a grammar for this new language) that describes how agents reason when they have a budget.
They proved it works (Completeness): They showed that their rules are perfect. If something is true in the real world (with budgets), their logic can prove it. If their logic says it's true, it is true. There are no gaps.
They defined "Bisimulation": This is a fancy way of saying "When are two situations effectively the same?"
- Analogy: Imagine two different video games. In Game A, you need 10 coins to buy a sword. In Game B, you need 10 gems. If the rules of the game are identical, they are "bisimilar." The authors proved that their logic can tell the difference between a game where you can afford the sword and one where you can't.

Why Does This Matter?

This is a bridge between pure math and real-world computing.

Before: Logicians said, "If the evidence exists, the agent knows it." (Ignoring the fact that the agent might be broke, tired, or locked out).
Now: Logicians can say, "The agent knows it only if they have the time, money, or clearance to get it."

This helps us build better:

AI Agents: Robots that know their own battery limits.
Security Systems: Models that understand exactly what a hacker could afford to access.
Distributed Systems: Networks that know when a group of computers has enough combined power to solve a problem.

Summary

Think of this paper as giving logic a wallet. It stops treating knowledge as a magical gift and starts treating it as a resource that must be earned, spent, and managed. By using "Seats," the authors created a universal language to describe how much "knowledge" we can afford in a world of limited resources.

1. Problem Statement

Standard epistemic logics (logics of knowledge and belief) typically model the acquisition of evidence as a cost-free, idealized process. In these frameworks, if evidence exists (modeled as an open set in a topological space), an agent can access it regardless of the resources required. However, in real-world computational systems (databases, robotics, security protocols), accessing information incurs tangible costs in terms of time, memory, energy, or money.

The central problem addressed is the discrepancy between qualitative epistemic reasoning and quantitative resource constraints. Existing frameworks either ignore resource costs or handle them using specific numerical scales (e.g., natural numbers) within discrete structures (like Kripke frames), failing to capture:

Non-linear resource structures (e.g., security clearance levels).
Multi-dimensional budgets (e.g., time vs. money).
The connection between resource constraints and the topology of observable properties.

2. Methodology: Semiring-Annotated Topological Spaces (Seats)

The authors bridge this gap by extending Topological Evidence Logic (TEL). TEL models evidence as open sets in a topological space $\langle X, \mathcal{T} \rangle$ , where a proposition is "justified" if supported by a dense open set and "known" if supported by a dense open set containing the current state.

The authors introduce a new mathematical structure called a Semiring-Annotated Topological Space (Seat):

Structure: A tuple $\mathbf{S} = \langle X, \mathcal{T}, \mathcal{A}_K \rangle$ , where $\langle X, \mathcal{T} \rangle$ is a topological space and $K = \langle K, \oplus, \odot, 0, 1 \rangle$ is a semiring representing resources.
Annotation Function: $\mathcal{A}_K: \mathcal{T} \times X \to \mathcal{P}(K)$ maps an open set (evidence) and a state to a set of resources sufficient to obtain that evidence at that state.
Semiring Operations:
- $\oplus$ (Addition): Represents resource choice (e.g., "resource $a$ OR resource $b$ ").
- $\odot$ (Multiplication): Represents resource combination (e.g., "resource $a$ AND resource $b$ ").
- $0$: The strongest resource (often representing infinite capacity or a "free" tautology depending on context).
- $1$: The unit resource (often representing "no cost" or identity).
Key Properties: The annotation function satisfies axioms reflecting resource strengthening, evidence weakening, resource choice, and resource combination. This allows the framework to model diverse scenarios, from binary stream observation (time cost) to role-based access control (qualification sets).

3. Key Contributions

A. Formal Framework (Seats)

The paper defines Seats as the foundational structure. It introduces specific classes of seats to model different scenarios:

Strong Seats: Where the set of sufficient resources forms a strong ideal (monotonic under additive strength).
Bounded Seats: Where tautologous evidence is "free" ($1$-bounded) or contradictory evidence is accessible via the strongest resource ($0$-bounded).
Uniform Seats: Where resource requirements do not depend on the specific state.
Cost Seats: Where a specific "weakest" resource (cost) can be assigned to every piece of evidence.

B. Epistemic Logics and Modalities

The authors develop a family of logics extending the topological modal logic S4.

Language: Introduces a resource-indexed modality $\mathbf{F}_a \varphi$ , meaning "there is evidence for $\varphi$ obtainable with resource budget $a$ ."
Derived Operators:
- $\mathbf{\Box}_a \varphi \equiv \mathbf{F}_a \varphi \land \mathbf{\Box} \varphi$ : Truthful evidence for $\varphi$ obtainable with budget $a$ .
- Weighted Belief ( $\mathbf{B}^a_b \varphi$ ) and Knowledge ( $\mathbf{K}^a_b \varphi$ ): Defined using a global modality ( $\mathbf{A}$ ), these operators capture justification where $a$ is the budget for finding supporting evidence and $b$ is the budget for finding counter-evidence (defending against refutation).

C. Axiomatization and Completeness

The paper provides sound and strongly complete axiomatizations for several logics:

$\mathbf{S4}_K$ : The minimal logic for all $K$ -seats.
$\mathbf{S4}_{sb}K$ : Characterizes strong and bounded seats.
$\mathbf{S4}_{sub}K$ : Characterizes strong, uniform, and bounded seats.
Extensions with Global Modality ( $\mathbf{A}$ ): The authors extend the language with a global modality to define weighted belief/knowledge operators and prove completeness for these expanded logics.

D. Expressiveness and Definability

To delineate the expressive power of the framework, the authors define:

Disjoint Unions: Used to prove that the class of uniform seats is not definable in the base language $\mathcal{L}_K$ (without the global modality).
Bisimulation: A novel notion of bisimulation for seats is introduced. It is used to prove that the global modality $\mathbf{A}$ is not definable in $\mathcal{L}_K$ and that cost-seat properties are not locally definable.

4. Key Results

Completeness Theorems: The paper establishes strong completeness for the minimal seat-based logic and its extensions characterizing specific structural properties of seats (strongness, boundedness, uniformity).
Generalization of TEL: The framework generalizes Topological Evidence Logic. When resources are ignored (or set to a trivial semiring), the logic reduces to standard TEL.
Unification: The framework unifies disparate areas of computer science:
- Programming Semantics: Observable properties of binary streams.
- Database Security: Role-based access control (qualifications as resources).
- Robotics: Graph exploration with energy/time constraints.
- Distributed Systems: Group communication limits.
Non-Definability: The paper proves that certain structural properties (like uniformity) and the global modality itself cannot be expressed without specific extensions to the language, clarifying the boundaries of the logic's expressiveness.

5. Significance and Impact

Bridging Qualitative and Quantitative: The paper successfully integrates quantitative resource constraints into a qualitative topological logic, moving beyond the "cost-free" assumption of standard epistemic logic.
Flexibility via Semirings: By using arbitrary semirings instead of fixed numerical scales (like $\mathbb{N}$ or $\mathbb{Q}$ ), the framework can model complex, non-linear resource structures (e.g., security clearances, multi-dimensional vectors) that previous logics could not handle.
Theoretical Foundation: It provides a rigorous mathematical foundation for "Resource-Aware Topological Evidence Logic," offering tools to reason about the trade-offs between the precision of knowledge and the cost of observation.
Future Directions: The framework opens avenues for studying decidability, dynamic updates of costs (dynamic epistemic logic on topological spaces), multi-agent cooperation under budget constraints, and connections to learning theory and Markovian logics.

In summary, "Knowledge on a Budget" presents a robust, mathematically rigorous extension of epistemic logic that accounts for the reality that knowledge acquisition is a resource-intensive process, providing a unified framework for reasoning about evidence, justification, and knowledge under constraints.