💻 computer science

Knowledge on a Budget

Dit paper introduceert semiring-geannoteerde topologische ruimtes om kwalitatieve epistemische logica te koppelen aan kwantitatieve resourcebeperkingen, waardoor redeneren over wat waarneembaar is binnen een specifiek budget mogelijk wordt.

Oorspronkelijke auteurs: Ondrej Majer, Krishna Manoorkar, Wolfgang Poiger, Igor Sedlár

Gepubliceerd 2026-04-15

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ondrej Majer, Krishna Manoorkar, Wolfgang Poiger, Igor Sedlár

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Kennis op de Budget: Waarom weten niet altijd gratis is

Stel je voor dat je een detective bent die een mysterie moet oplossen. In de klassieke logica (de "standaard" manier waarop computers en filosofen over kennis nadenken) is het vinden van bewijs een magisch proces: je denkt eraan, en poef, je hebt het bewijs. Het kost je geen tijd, geen energie en geen geld.

Maar in het echte leven werkt dat niet zo. Als je een database wilt doorzoeken, kost dat rekenkracht. Als je een robot een opdracht geeft om een kamer te verkennen, kost dat batterijvermogen. Als je als agent in een veiligheidsprotocol informatie wilt opvragen, moet je misschien eerst een dure paspoortcheck doorlopen.

De auteurs van dit paper, Ondrej Majer en zijn collega's, zeggen: "Wacht even, we moeten die 'gratis kennis' in onze modellen stoppen en vervangen door 'kennis op budget'."

Hier is een simpele uitleg van hun idee, met wat creatieve vergelijkingen.

1. De Wereld als een Grote Lijst (Topologie)

Stel je de wereld voor als een enorme, ondoorzichtige doos met verschillende lagen. In de wiskundige taal van de auteurs (topologie) zijn deze lagen "open sets".

Hoe het werkt: Als je een stukje bewijs hebt (bijvoorbeeld een foto), kun je een deel van die doos openen. Als dat stukje bewijs klopt met alles wat je al weet, kun je een conclusie trekken.
Het probleem: De oude modellen dachten dat je elk stukje bewijs uit die doos kon pakken, ongeacht hoe diep het verstopt zat.

2. De Muntstukken van de Wereld (Semiringen)

Nu komt het nieuwe idee: Kennis kost iets.
De auteurs introduceren een systeem dat ze "seats" noemen (een knipoog naar semiring-annotated topological spaces, maar laten we het simpel houden).

Stel je voor dat je een rekenmachine hebt die niet alleen optelt en aftelt, maar ook "kosten" berekent.

Tijd: Je kunt een bewijs krijgen door 5 minuten te wachten.
Geld: Je kunt een bewijs kopen voor €10.
Toegang: Je kunt een bewijs krijgen als je een "Beveiligingsniveau 3" badge hebt.

In dit paper gebruiken ze geen simpele euro's, maar een flexibel systeem (een semiring) dat alles kan meten: van tijd en geld tot complexe beveiligingscodes. Het mooie is: je kunt verschillende soorten "geld" mengen. Je kunt zeggen: "Ik heb 5 minuten en een niveau 2 badge nodig om dit te weten."

3. De "Kennis op Budget" Logica

De auteurs bouwen een nieuwe taal (een logica) waarmee we kunnen zeggen:

"Ik weet dat het regent, als ik 10 minuten heb om naar buiten te kijken."
"Ik kan bewijzen dat de deur open is, als ik de sleutel (mijn budget) heb."

Ze maken onderscheid tussen:

Wat je in theorie kunt weten: Als je oneindig veel tijd en geld had, zou je alles weten.
Wat je nu kunt weten: Gezien je huidige portemonnee en batterij, wat is er haalbaar?

4. Drie Leuke Voorbeelden uit het Paper

Om hun theorie te testen, kijken ze naar drie situaties:

De Streamer (Tijd als kosten):
Stel je hebt een videostreamer. Je kunt de stream niet in één keer zien; je moet wachten tot hij laadt.
- Oude logica: Je ziet de hele stream.
- Nieuwe logica: Je kunt alleen zien wat er is geladen in de eerste 10 seconden. Als je meer wilt zien, moet je "wacht-tijd" (je budget) spenderen.
De Database (Rechten als kosten):
In een bedrijf heeft iedereen een rol (bijv. "Klerk" of "Manager").
- Oude logica: Iedereen kan alle bestanden zien.
- Nieuwe logica: Je kunt alleen het bestand zien als je de juiste "rol" (je budget) hebt. Als je budget te laag is, is het bestand voor jou onbereikbaar, zelfs als het bestaat.
De Robot (Afstand als kosten):
Een robot moet een gebouw verkennen.
- Oude logica: De robot weet direct hoe het gebouw eruitziet.
- Nieuwe logica: De robot moet erheen lopen. Elke stap kost batterij. Als de batterij op is (budget op), kan de robot niet meer verder kijken en weet hij niet meer wat er achter de volgende hoek zit.

5. Waarom is dit belangrijk?

Dit paper is als het bouwen van een nieuwe soort bril voor computers en filosofen.

Vroeger: Computers dachten dat ze alles konden weten zonder moeite.
Nu: Met deze nieuwe "bril" kunnen we modellen maken die realistisch zijn. We kunnen nu vragen stellen als: "Is deze beslissing veilig, gezien de beperkte rekenkracht van de robot?" of "Kan deze hacker de data kraken binnen zijn tijdslimiet?"

Conclusie

Kortom: De auteurs hebben een manier bedacht om kennis te koppelen aan kosten. Ze zeggen: "Weten is niet gratis." Door dit in te bouwen in de wiskundige logica, kunnen we betere systemen bouwen voor robots, beveiliging en databases die rekening houden met de beperkte middelen waar we in het echte leven mee werken.

Het is alsof je van een droomwereld (waar alles gratis is) wakker wordt in de echte wereld (waar je moet betalen, wachten en moeite doen om iets te weten te komen). En dat is precies waar deze paper over gaat.

Titel: Knowledge on a Budget

Auteurs: Ondrej Majer, Krishna Manoorkar, Wolfgang Poiger en Igor Sedlár
Context: Een brug slaan tussen kwalitatieve epistemische logica en kwantitatieve resource-beperkingen.

1. Het Probleem

In de meeste computationele systemen (zoals database-query engines, beveiligingsprotocollen of robotagenten) is toegang tot informatie niet gratis; het kost tijd, geheugen, energie of geld. Standaard epistemische logica's modelleren het verwerven van bewijs echter als een kostenloos en geïdealiseerd proces. Dit beperkt de toepasbaarheid van deze logica's in realistische scenario's waar agenten moeten opereren binnen strikte resource-beperkingen.

De kernvraag is: Hoe kunnen we kwantitatieve resource-beperkingen integreren in een kwalitatieve logica van bewijs en rechtvaardiging? Bestaande benaderingen gebruiken vaak specifieke numerieke schalen (zoals natuurlijke getallen) en discrete structuren (Kripke-modellen), wat onvoldoende is voor niet-lineaire resource-structuren (zoals beveiligingsniveaus of multidimensionale budgetten).

2. Methodologie: Semiring-geannoteerde Topologische Ruimtes (Seats)

De auteurs bouwen voort op Topological Evidence Logic (TEL), waar bewijs wordt gemodelleerd als open verzamelingen in een topologische ruimte. In TEL is een hypothese $P$ gerechtvaardigd als er een dichte open verzameling $U$ bestaat die $P$ ondersteunt, en bekend als $x \in U$ . Echter, TEL is "resource-blind".

Om dit op te lossen, introduceren de auteurs Semiring-annotated Topological Spaces, afgekort als Seats.

Definitie van een Seat: Een tuple $\mathbf{S} = \langle X, \mathcal{T}, \mathcal{A}_K \rangle$ , waarbij:
- $\langle X, \mathcal{T} \rangle$ een topologische ruimte is (waar open verzamelingen corresponderen met observaties/bewijs).
- $K = \langle K, \oplus, \odot, 0, 1 \rangle$ een semiring is die de resources vertegenwoordigt.
- $\mathcal{A}_K: \mathcal{T} \times X \to \mathcal{P}(K)$ een annotatiefunctie is die voor elke open verzameling $U$ en toestand $x$ de verzameling resources $a \in K$ toewijst die voldoende zijn om bewijs $U$ in $x$ te verkrijgen.
Semiring-eigenschappen:
- $\oplus$ (optelling) staat voor resource keuze (" $a$ of $b$ ").
- $\odot$ (vermenigvuldiging) staat voor resource combinatie (" $a$ samen met $b$ ").
- De annotatie voldoet aan eigenschappen zoals resource-versterking, bewijs-verzwakking en resource-combinatie.
Voorbeelden van toepassing:
- Observatie van binaire streams: Resources zijn tijd (lengte van het geobserveerde woord).
- Role-Based Access Control (RBAC): Resources zijn rollen/qualificaties.
- Grafexploratie: Resources zijn gewichten (afstand/batterijverbruik).
- Distributed Systems: Resources zijn groepen agenten.

3. Epistemische Operatoren en Logica

Op basis van Seats definiëren de auteurs nieuwe epistemische operatoren die afhankelijk zijn van het budget:

$\mathbf{F_a \varphi}$ : Er is bewijs voor $\varphi$ dat verkregen kan worden met resource $a$ .
$\mathbf{\Box_a \varphi}$ : Er is waar bewijs (factive) voor $\varphi$ dat verkregen kan worden met resource $a$ .
$\mathbf{Bel^a_b \varphi}$ en $\mathbf{Kn^a_b \varphi}$ : Gerechtvaardigd geloof en kennis waarbij $a$ het budget is voor het vinden van bewijs en $b$ het budget is voor het vinden van tegenbewijs (counter-arguments).

De auteurs definiëren een familie van logica's, beginnend met $S4_K$ (de minimale seat-gebaseerde logica), en breiden deze uit met axioma's voor specifieke klassen van Seats:

$S4_{sbK}$ : Voor strong en bounded Seats (waarbij bewijs altijd gratis verkregen kan worden voor tautologieën en waar resources monotoon zijn).
$S4_{subK}$ : Voor uniform Seats (waarbij de kosten niet van de toestand afhangen).
Uitbreiding met globale modale: Door de toevoeging van de globale modale operator $\mathbf{A}$ (waar $\mathbf{A}\varphi$ betekent dat $\varphi$ overal waar is), kunnen de auteurs de operatoren voor geloof en kennis volledig karakteriseren.

4. Belangrijkste Resultaten

Axiomatisatie en volledigheid:
De auteurs bewijzen sterke volledigheid (strong completeness) voor de logica's $S4_K$ , $S4_{sbK}$ en $S4_{subK}$ (en hun uitbreidingen met de globale modale) ten opzichte van de respectievelijke klassen van Seats. Dit betekent dat elke formule die semantisch geldig is in deze modellen, ook formeel afleidbaar is.
- De bewijzen maken gebruik van canonieke modellen en een aangepaste constructie voor uniforme modellen.
Expressiviteit en Onbepaaldheid:
De auteurs definiëren concepten van bisimulatie en disjuncte unie voor Seats. Hiermee tonen ze aan:
- De klasse van uniforme Seats is niet definieerbaar in de taal zonder de globale modale ( $\mathcal{L}_K$ ).
- De globale modale operator $\mathbf{A}$ is niet definieerbaar in $\mathcal{L}_K$ .
- Dit markeert de grenzen van de expressieve kracht van de logica's.
Unificatie van domeinen:
Het framework verenigt structuren uit diverse gebieden van de informatica (programmeersemaniek, databasebeveiliging, robotica, gedistribueerde systemen) onder één wiskundige paraplu.

5. Significantie en Bijdrage

Generaliteit: In tegenstelling tot eerdere werken die vaak specifieke numerieke kosten gebruiken, maakt dit framework gebruik van willekeurige semiringen. Dit stelt onderzoekers in staat om niet-lineaire resource-structuren (zoals beveiligingsniveaus of vector-budgetten) te modelleren.
Topologische Basis: Door de logica te situeren binnen de topologische semantiek van TEL, wordt er een brug geslagen tussen resource-bewuste logica en het bestaande werk over de topologie van waarneembare eigenschappen.
Praktische relevantie: Het biedt een formele basis voor redeneren over de afweging tussen de precisie van kennis en de kosten van observatie. Dit is cruciaal voor systemen waar agenten moeten beslissen wat ze kunnen "bekomen" binnen hun beperkte middelen.

Conclusie en Toekomstperspectief

Het artikel legt de fundamenten voor "Resource-Aware Topological Evidence Logic". Toekomstig werk richt zich op:

Het bepalen van de beslisbaarheid en computationele complexiteit.
Het ontwikkelen van dynamische extensies om veranderingen in kosten en informatie te modelleren.
Uitbreiding naar multi-agent systemen waar agenten samenwerken binnen hun respectievelijke budgetten.
Toepassing in leertheorie (learnability in the limit) en inductieve probleemoplossing.

Kortom, dit werk transformeert epistemische logica van een abstracte, kostenloze discipline naar een praktisch instrument voor het modelleren van kennis in een wereld van beperkte middelen.