Agent Interpolation for Knowledge

Marta Bílková, Wesley Fussner, Roman Kuznets✉ · 2025

Read Agent Interpolation for Knowledge by Marta Bílková, Wesley Fussner, Roman Kuznets✉ (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-2505-23401.txt.

Introduction

Marta Bílková, Wesley Fussner, and Roman Kuznets built a new proof system in 2025 for logics of knowledge shared among several agents. Multi-agent modal logic, with S5-style knowledge operators for each agent, is a standard language for reasoning about who knows what. Proving things in it cleanly, and extracting consequences automatically, calls for a calculus designed around its structure.

Their formalism merges two known devices: hypersequents, which suit the S5 modalities, and nested sequents, which handle the alternating T-like steps between agents. They prove the calculus sound and complete, free of the cut rule, and guaranteed to terminate, which yields decidability and the finite model property for multi-agent S5. As a payoff they establish the Lyndon interpolation property, counting the agents themselves as part of the shared language, and discuss what blocks extending the results to distributed knowledge.

Catalog record

CREATORMarta Bílková, Wesley Fussner, Roman Kuznets✉
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE190 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-23401

Browse the full library · About the Tower of Babel

Full text

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

Agent Interpolation for Knowledge Marta Bílková, Wesley Fussner, Roman Kuznets✉ Abstract We define a new type of proof formalism for multi-agent modal logics with S5-type modalities. This novel formalism combines the features of hypersequents to represent S5 modalities with nested sequents to represent the T-like modality alternations. We show that the calculus is sound and complete, cut-free, and terminating and yields decidability and the finite model property for multi-agent S5. We also use it to prove the Lyndon (and hence Craig) interpolation property for multi-agent S5, considering not only propositional atoms but also agents to be part of the common language. Finally, we discuss the difficulties on the way to extending these results to the logic of distributed knowledge and to deductive interpolation. 1 Introduction † † The authors were supported by the grant 22-23022L CELIA of Grantová Agentura České Republiky. One logic often has multiple proof-theoretic representations. In most cases, it is not reasonable to see one of them as being objectively better than all others in all respects. A Hilbert-style calculus could be good for proving semantical completeness but give little help for establishing decidability. A cut-free sequent calculus works much better for decidability but may be unsuitable to show the Craig interpolation property ( CIP ) even if it does hold (cf., e.g., [ 5 ] for the Gödel–Dummett logic). If no cut-free calculus exists, an analytic sequent calculus could be one of the simplest alternatives and may even be sufficient for establishing the CIP , but the Lyndon interpolation property ( LIP ) would require something else, e.g., hypersequents. One-size-fits-all proof calculi are exceedingly rare. The choice of calculus is, therefore, dictated, on the one side, by applications and, on the other side, by the range of logics to be applied to. Quite often, the choices can be mapped onto a line between generality and efficiency. The more logics a proof formalism covers, the less likely it is to be efficient for each one of them. Labelled sequents [ 15 ] are on the more general part of the spectrum, with the methods described in [ 16 ] surely sufficient to treat a logic like multi-agent {\sf S5}_{n} . The goal of this work is to develop a proof formalism tailor-made for {\sf S5}_{n} and extract from it a number of results such as decidability and interpolation for both propositional atoms (for which we obtain Lyndon interpolation) and agents (for which we obtain Craig interpolation). We also discuss interpolation for distributed knowledge and agent interpolation for the global consequence relation, which prove more subtle. The format we develop is a hybrid of hypersequents [ 13 , 19 , 1 ] to represent equivalence classes of individual agents and nested sequents [ 2 , 17 , 10 ] to represent the tree structure for alternating agent modalities. Since “nested hypersequents” could be confused with nested sequents, which are sometimes called tree-hypersequents [ 17 ] , we will use a fresh term crossword sequents because our proof structures resemble (multidimensional) crosswords, with multiple hypersequents intersecting in a sequent component, shortening it to cross-sequents because they are a cross between hypersequents and nested sequents. 2 Preliminaries We work with the multi-agent modal language in the negation normal form (NNF). The latter choice enables us to use one-sided sequents. This choice is inessential and can be easily changed to the full language with negation and two-sided sequents. Formulas are defined by the grammar \varphi\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\bot\mid\top\mid p\mid\neg p\mid(\varphi\wedge\varphi)\mid(\varphi\vee\varphi)\mid\Box_{a}\varphi\mid\Diamond_{a}\varphi where p\in\mathrm{Prop} is a (propositional) atom, \neg p is the negation of p , with both called literals , and a\in A is an agent for some countably infinite \mathrm{Prop} and finite A\neq\varnothing . The total number of agents is n . Negation \neg can be recursively extended from atoms to arbitrary formulas using standard De Morgan dualities, e.g., \neg\Box_{a}\varphi\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\Diamond_{a}\neg\varphi . Implication \varphi\to\psi\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\neg\varphi\lor\psi . The variables and agents occurring (positively/negatively) in a formula are defined in the standard way, with \textup{{Col}}\in\{\textup{{Var}},\textup{{Ag}}\} , \circ\in\{\wedge,\vee\} , \ast\in\{+,-\} , \heartsuit\in\{\Box,\Diamond\} , and \textup{{Col}}(\varphi)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}{\textup{{Col}}^{+}}(\varphi)\cup{\textup{{Col}}^{-}}(\varphi) : \textup{{Var}}(\bot)=\textup{{Var}}(\top)=\textup{{Ag}}(\bot)=\textup{{Ag}}(\top)=\textup{{Ag}}(p)=\textup{{Ag}}(\neg p)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\varnothing , so that in these cases the sets {\textup{{Var}}^{+}} and {\textup{{Var}}^{-}} of positively and negatively occurring variables are also empty; further, {\textup{{Col}}^{*}}(\varphi\circ\psi)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}{\textup{{Col}}^{*}}(\varphi)\cup{\textup{{Col}}^{*}}(\psi) ; {\textup{{Var}}^{*}}(\heartsuit_{a}\varphi)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}{\textup{{Var}}^{*}}(\varphi) ; {\textup{{Var}}^{+}}(p)={\textup{{Var}}^{-}}(\neg p)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\{p\} ; {\textup{{Var}}^{-}}(p)={\textup{{Var}}^{+}}(\neg p)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\varnothing ; \textup{{Ag}}(\heartsuit_{a}\varphi)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\{a\}\cup\textup{{Ag}}(\varphi) . Modal depth \mathit{fd}(\varphi) is also defined recursively: \mathit{fd}(\top)=\mathit{fd}(\bot)=\mathit{fd}(p)=\mathit{fd}(\neg p)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}0 , \mathit{fd}(\varphi\circ\psi)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\max(\mathit{fd}(\varphi),\mathit{fd}(\psi)) , and \mathit{fd}(\heartsuit_{a}\varphi)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\mathit{fd}(\varphi)+1 . Modal logic {\sf S5}_{n} is the logic of multi-agent Kripke frames with all accessibility relations being equivalence relations. Definition 1 (Semantics) A structure \mathcal{M}=(W,R,V) is an (epistemic Kripke) model iff W\neq\varnothing is a set of worlds, R maps each agent a\in A to an equivalence relation 1 1 1 An equivalence relation R on W is reflexive, symmetric, and transitive, i.e., wRw , and vRw whenever wRv , and wRu whenever wRv and vRu for all w,v,u\in W . R_{a}\subseteq W\times W on W , and V maps each atom p\in\mathrm{Prop} to a set V(p)\subseteq W of worlds where p is true. R_{a}(w)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\{v\in W\mid wR_{a}v\} . Each R_{a} partitions W into pairwise disjoint clusters \{R_{a}(w)\mid w\in W\} , where an a -cluster is a maximal totally R_{a} -connected set U\subseteq W , i.e., (u,v)\in R_{a} for all u,v\in U and (u,w)\notin R_{a} for all u\in U and w\notin U . uR_{a}v means (u,v)\in R_{a} . Truth of a formula \varphi in a world w of a model \mathcal{M} is defined recursively: \mathcal{M},w\nvDash\bot ; \mathcal{M},w\vDash\top ; \mathcal{M},w\vDash p iff w\in V(p) ; \mathcal{M},w\vDash\neg p iff w\notin V(p) ; \mathcal{M},w\vDash\varphi_{1}\wedge\varphi_{2} iff \mathcal{M},w\vDash\varphi_{i} for both i=1,2 ; \mathcal{M},w\vDash\varphi_{1}\vee\varphi_{2} iff \mathcal{M},w\vDash\varphi_{i} for at least one i=1,2 ; \mathcal{M},w\vDash\Box_{a}\varphi iff \mathcal{M},v\vDash\varphi for all v\in R_{a}(w) ; and \mathcal{M},w\vDash\Diamond_{a}\varphi iff \mathcal{M},v\vDash\varphi for at least one v\in R_{a}(w) . A formula \varphi is {\sf S5}_{n} - valid , written \varphi\in{\sf S5}_{n} iff it is true in all worlds of all epistemic models. The Hilbert-style axiomatization of {\sf S5}_{n} via factivity and positive and negative introspection is well known (see, e.g., [ 6 ] ). It is axiomatized by any complete set of axioms for the classical propositional logic, rule modus ponens , and the following axioms and rules for each agent a\in A : \displaystyle\Box_{a}(\varphi\to\psi)\to(\Box_{a}\varphi\to\Box_{a}\psi)\qquad\Box_{a}\varphi\to\varphi\qquad\frac{\varphi}{\Box_{a}\varphi} \displaystyle\Box_{a}\varphi\to\Box_{a}\Box_{a}\varphi\qquad\Diamond_{a}\varphi\to\Box_{a}\Diamond_{a}\varphi Theorem 2.1 (Semantic Completeness) \vdash_{{\sf S5}_{n}}\varphi iff \varphi\in{\sf S5}_{n} . The goal of this paper is to provide a proof-theoretic description of {\sf S5}_{n} . A (one-sided) sequent is a finite set of formulas, written \Delta=\varphi_{1},\dots,\varphi_{k} . It is true at a world w of model \mathcal{M} , written \mathcal{M},w\vDash\Delta , iff \mathcal{M},w\vDash\varphi_{i} for some \varphi_{i} , i.e., there is a formula interpretation \iota_{s}(\Delta)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\bigvee\Delta=\bigvee_{i=1}^{k}\varphi_{i} such that \mathcal{M},w\vDash\Delta iff \mathcal{M},w\vDash\iota_{s}(\Delta) . No cut-free sequent calculus has been found for the single-agent {\sf S5}_{1} . One way to avoid using the cut rule is to employ hypersequents [ 1 ] , which are multisets of sequents. A hypersequent H=\Delta_{1}\mid\dots\mid\Delta_{m} has the formula interpretation \iota_{h}(H)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\bigvee_{j=1}^{m}\Box\iota_{s}(\Delta_{j}) . Thus, falsifying a hypersequent means finding a cluster containing worlds w_{1},\dots,w_{m} such that \mathcal{M},w_{j}\nvDash\Delta_{j} for each j=1,\dots,m . The multiset sequent structure is sufficient for {\sf S5}_{1} because it matches the accessibility structure of its models, but many modal logics require more structure. For instance, nested sequents [ 10 ] , which are trees of sequents, are not as general as labelled sequents, but provide a robust and purely syntactical representation

Read the complete text