💻 computer science

The Logic of Data Access and Data Exchanges

This paper introduces and axiomatizes a new logic that extends Dynamic Epistemic Logic to model agents' conditional non-propositional knowledge of variable values and their ability to narrow down possibilities, while also incorporating dynamic modalities for complex data-exchange events like hacking and public sharing, ultimately proving the system's decidability and co-expressivity.

Original authors: Alexandru Baltag (ILLC, University of Amsterdam), Sonja Smets (ILLC, University of Amsterdam)

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexandru Baltag (ILLC, University of Amsterdam), Sonja Smets (ILLC, University of Amsterdam)

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: A New Rulebook for Information

Imagine you are trying to build a rulebook for how people share secrets, solve puzzles, and hack databases. Most existing rulebooks (called "Dynamic Epistemic Logic") are great at handling simple "Yes/No" facts. For example: "Alice knows that the light is on."

But in the real world, information isn't just "Yes" or "No." It's numbers, passwords, addresses, and complex data. This paper introduces a new, more powerful rulebook that handles non-propositional data (like numbers) and group collaboration.

Think of this new logic as a super-powered detective kit that can track not just what people know, but which specific numbers they know, and how they can narrow down a list of possibilities together.

1. The Characters: Agents and Data Sources

In this story, "Agents" aren't just people; they are also databases, websites, or even a locked envelope.

The Scenario: Imagine Alice and Bob. Alice has a secret number ( $x_a$ ), Bob has a secret number ( $x_b$ ), and there is an envelope ( $e$ ) containing the sum of their numbers ( $x_e = x_a + x_b$ ).
The Problem: Alice knows her own number but not Bob's. Bob knows his but not Alice's. However, if they put their heads together (a "group"), they can figure out the sum in the envelope.

The paper's logic allows us to write down exactly what the group knows, even if no single person knows the answer yet.

2. The New Superpowers: "Narrowing Down" and "Naming"

The authors added two special tools to their logic:

A. The "Narrowing Down" Tool ( $|x| \le N$ )

Imagine you are trying to guess a password.

Old Logic: You either know the password, or you don't.
New Logic: You can say, "I don't know the exact password, but I know it's one of these 3 possibilities."
The Metaphor: Think of a detective who can't identify the killer yet but has narrowed the suspect list from 1,000 people down to just 5. The paper's logic can mathematically express: "Given the evidence $\phi$ , the group can narrow the variable $x$ down to at most $N$ possibilities."
Why it matters: If a hacker can narrow a password down to just 5 possibilities, they can crack it by trying all 5. The logic captures this "capability to guess."

B. The "Naming" Tool (Definite Descriptions)

Once you have narrowed a list down to 5 possibilities, how do you talk about them?

The authors introduce a way to name them based on an order (like a list sorted from smallest to largest).
The Metaphor: If the possible passwords are 10, 20, 30, 40, and 50, the logic allows you to say: "The first possible password is 10," or "The second possible password is 20."
This is done using a special operator (called $\mu$ ) that picks the "least" (smallest) value from the list of possibilities. It's like having a robot that sorts your suspect list and points to the top name.

3. The Action: Data Exchange Events

The paper isn't just about what people know now; it's about what happens when they swap information. They call these "Data-Exchange Events."

Think of these events as scenes in a play where the script changes:

Public Announcements: Everyone shouts, "The sum is 5!" (Everyone updates their knowledge).
Semi-Public Sharing: Alice whispers to Bob, "Here is my number." Now Bob knows both numbers, but Charlie (who wasn't listening) still doesn't.
Secret Hacking: Alice secretly hacks Bob's computer. She copies his password. The paper's logic can model this:
- Scenario: Alice hacks Bob only if she already knows his password.
- Scenario: Alice hacks Bob, but only Bob knows she did it (he sees the logs).
- Scenario: Alice changes her password only if she knows Bob has narrowed her old password down to 2 possibilities.

The logic tracks how these events change the "map" of what everyone knows, including how they gain access to entire "chunks" of data (like a whole database) at once.

4. The Mathematical Magic: Proving the Rules Work

The authors didn't just invent these rules; they proved they work perfectly.

Completeness: They showed that their rulebook is "complete." This means if a statement is true in every possible scenario, their rulebook can prove it.
Decidability: They proved that there is a mechanical way to check if any statement is true or false. You don't need a supercomputer to guess; there is a step-by-step algorithm to solve it.
The "Tree" Trick: To prove this, they built a giant imaginary tree of all possible scenarios. They showed that even though the tree is infinite, the rules for "narrowing down" and "naming" keep everything organized so that the math doesn't break.

5. What They Didn't Do (The Limitations)

The authors were honest about what they left out to keep the paper manageable:

Common Knowledge: They didn't include the concept of "Common Knowledge" (where everyone knows that everyone knows that everyone knows...). They say this is too complex for this specific paper and will be added in a future, longer version.
Real-World Apps: They focused entirely on the mathematical logic. They didn't test this on real banking systems or medical records in this paper; they just built the theoretical engine.

Summary

This paper builds a mathematical language for a world where information is messy, numerical, and shared in complex ways. It gives us the tools to say:

"I know the value of this variable."
"I know it's one of these 3 numbers."
"I can name the smallest of those 3 numbers."
"If we swap our data like this, here is exactly how our knowledge changes."

It turns the chaotic process of hacking, sharing, and guessing passwords into a precise, solvable logic puzzle.

Technical Summary: The Logic of Data Access and Data Exchanges (LDAE)

Problem Statement
The paper addresses the limitations of existing Dynamic Epistemic Logic (DEL) frameworks in modeling non-propositional information (e.g., numbers, passwords, cryptographic keys) and complex data-exchange dynamics. While previous works have formalized "knowing-what" (knowledge of a variable's value) and distributed knowledge, they often fail to capture scenarios where agents gain access to entire "chunks" of data (sources) or where agents can narrow down a variable's value to a finite set of possibilities without uniquely identifying it. Specifically, prior frameworks either restricted dynamics to "semi-public" events (excluding secret hacking) or lacked explicit non-propositional operators (preventing assertions about specific data values or conditional hacking scenarios). The authors aim to unify and generalize these approaches to create a logic capable of handling arbitrary data-exchange events, including private modifications, secret hacking, and conditional access based on partial knowledge.

Methodology
The authors develop LDAE (Logic of Data Access & Exchange), a dynamic-epistemic logic extending DEL with the following components:

Syntax and Semantics:
- Variables and Terms: The logic includes basic variables, functions, and definite descriptions based on minimization operators ( $\mu N x^\phi_A$ ). These operators denote the "least" of at most $N$ possible values of a variable $x$ according to a group $A$ , given condition $\phi$ , based on a fixed total order.
- Cardinality Operators: A key generalization is the operator $|x|^\phi_A \le N$ , expressing that group $A$ can narrow the possible values of $x$ (conditional on $\phi$ ) to at most $N$ possibilities. This subsumes standard "knowing-what" ( $K^\phi_A x$ , where $N=1$ ).
- Dynamic Events: The logic models "data-exchange events" as pointed event models. These events allow agents to access other agents' databases (sources), copy information, or modify values. Events include public announcements, semi-public sharing (e.g., "tell us all you know"), secret hacking, and conditional password changes.
- Semantics: Models are defined over ordered value domains. The semantics of the minimization operator relies on the Order Extension Principle (and thus the Axiom of Choice) to ensure a total order exists on the constructed value domain.
Axiomatization:
- The static fragment (LDA) is axiomatized using classical propositional logic, axioms for equality and order, and specific axioms for distributed knowledge and minimization (e.g., "Reaching the Minimum").
- The dynamic logic (LDAE) employs reduction axioms to eliminate dynamic modalities $[e]\phi$ and event terms $e(x)$ , reducing them to equivalent static formulas. A critical component is the "Cutoff-Min. Change" axiom, which handles the reduction of minimization terms after an event by considering the union of possible values across indistinguishable event outcomes.
Proof Techniques:
- Completeness: The authors prove completeness for the static logic using a quasi-model construction. They construct a "quasi-model" (a syntactic structure where variables lack concrete values and group relations are non-standard) and then "unravel" it into an infinite tree of histories. They define an equivalence relation on pairs of (history, variable) to construct a canonical model, ensuring the preservation of variable values and order properties across the tree.
- Decidability and Co-expressivity: The paper proves that LDAE is co-expressive with its static fragment LDA. By demonstrating that every dynamic formula and term can be reduced to a static equivalent via the reduction axioms, the decidability of the dynamic logic follows directly from the decidability of the static logic.

Key Contributions and Results

Generalized Knowledge Operators: The introduction of $|x|^\phi_A \le N$ allows for the formalization of "narrowing down" possibilities, which is crucial for modeling cryptographic attacks where an intruder can brute-force a password if the search space is small enough.
Unrestricted Dynamics: The framework supports a broader class of data-exchange events than previous works, including secret hacking and conditional events (e.g., a password change triggered only if an intruder has narrowed down the possibilities).
Definite Descriptions: The use of $\mu N$ operators allows the logic to name and reason about hypothetical values (e.g., "the first possible value of $x$ given $\phi$ "), even when the exact value is unknown.
Formal Guarantees: The paper provides a complete axiomatization for both the static and dynamic fragments and proves that the logic is decidable.
Expressivity: The logic is shown to be co-expressive with its static base, meaning the dynamic operators do not increase the expressive power beyond what is achievable in the static logic, but they significantly simplify the description of dynamic processes.

Significance and Claims
The authors claim that LDAE provides a robust, decidable framework for reasoning about complex information dynamics involving non-propositional data. The logic is particularly significant for its ability to model scenarios where agents gain access to distributed knowledge bases and where the "value" of information is defined by the ability to narrow down possibilities rather than uniquely identifying a value.

The paper is modest regarding its scope, explicitly noting that common knowledge operators ( $C_A \phi$ ) are excluded due to the complexity of their dynamics and are reserved for a future journal version. Additionally, the authors acknowledge that their axioms are somewhat complex because they have not yet proven the Finite Model Property (FMP) for the logic. Proving FMP would have allowed for simpler axioms by replacing "cutoff-minimization" with standard minimization. The absence of a counterexample to FMP leaves this as an open question. The work builds upon and generalizes previous formalizations of "knowing-what" and data exchange, aiming to bridge the gap between static epistemic logic and dynamic information flow in multi-agent systems.