pith. sign in

arxiv: 1907.09114 · v1 · pith:CWESBVG3new · submitted 2019-07-22 · 💻 cs.GT · cs.AI· cs.LO

Exploiting Belief Bases for Building Rich Epistemic Structures

Emiliano Lorini (IRIT-CNRS , Toulouse University , France) This is my paper

Pith reviewed 2026-05-24 18:04 UTC · model grok-4.3

classification 💻 cs.GT cs.AIcs.LO
keywords epistemic logicbelief basesuniversal epistemic modelsemantic equivalencemodel checkingonly believingKripke structures
0
0 comments X

The pith

Belief bases define possible worlds and epistemic alternatives, enabling a simpler universal epistemic model than inductive constructions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a semantics for epistemic logic in which belief bases are the basic objects, and possible worlds along with epistemic alternatives are derived from them rather than taken as primitive. This construction supports a more compact definition of the universal epistemic model. The semantics is shown to be equivalent to standard Kripke semantics both for the language of individual belief and for its extension with the only-believing operator. A complexity lower bound is given for model checking relative to the universal model built this way.

Core claim

The central claim is that a belief base abstraction, from which possible worlds and epistemic alternatives are derived, yields a simpler and more compact construction of the universal epistemic model than existing inductive constructions while preserving equivalence to standard Kripke models for the basic epistemic language and its extension by only believing.

What carries the argument

The belief base abstraction, used to derive possible worlds and epistemic alternatives that form the epistemic structures.

If this is right

  • Semantic equivalence holds for the basic epistemic language containing individual belief operators.
  • Semantic equivalence extends to the language that additionally contains the only-believing operator.
  • A lower bound on the complexity of model checking for epistemic logic relative to the universal epistemic model follows from the construction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The belief-base approach may simplify the addition of belief-revision operations to epistemic models.
  • It could support more compact representations when epistemic models are used inside automated reasoning systems.
  • Alternative semantics for epistemic logic might be compared or unified by translating them into this belief-base form.

Load-bearing premise

Defining possible worlds and epistemic alternatives from belief bases preserves the intended semantics of the epistemic operators and produces models equivalent to standard Kripke structures.

What would settle it

A concrete formula in the epistemic language whose truth value differs between the belief-base semantics and the standard Kripke semantics when evaluated on the universal model.

Figures

Figures reproduced from arXiv: 1907.09114 by Emiliano Lorini (IRIT-CNRS, France), Toulouse University.

Figure 1
Figure 1. Figure 1: Conceptual framework 2.3 Model classes and validity In some situations, it may be useful to assume that agents’ beliefs are correct, i.e., what an agent believes is true. When talking about correct (or true) explicit and implicit beliefs, it is usual to call them explicit and implicit knowledge. Indeed, we assume that the terms “true belief”, “correct belief” and “knowledge” are synonyms. The following def… view at source ↗
read the original abstract

We introduce a semantics for epistemic logic exploiting a belief base abstraction. Differently from existing Kripke-style semantics for epistemic logic in which the notions of possible world and epistemic alternative are primitive, in the proposed semantics they are non-primitive but are defined from the concept of belief base. We show that this semantics allows us to define the universal epistemic model in a simpler and more compact way than existing inductive constructions of it. We provide (i) a number of semantic equivalence results for both the basic epistemic language with "individual belief" operators and its extension by the notion of "only believing", and (ii) a lower bound complexity result for epistemic logic model checking relative to the universal epistemic model.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 0 minor

Summary. The paper introduces a semantics for epistemic logic based on belief bases, from which possible worlds and epistemic alternatives are derived rather than taken as primitives. It claims this yields a simpler and more compact universal epistemic model than existing inductive constructions. The authors establish semantic equivalence results between this semantics and standard Kripke semantics for the language with individual belief operators and its extension with 'only believing', and prove a lower bound on the complexity of model checking relative to the universal epistemic model.

Significance. If the equivalence results hold, the belief-base approach provides a more compact construction of universal epistemic models while preserving the intended semantics of the epistemic operators. The explicit provision of equivalence proofs (rather than unverified assumptions) and the complexity lower bound are strengths that make the claims verifiable. This could simplify work on epistemic structures in multi-agent settings.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, detailed summary of our contribution on belief-base semantics for epistemic logic, and recommendation to accept the manuscript. No major comments were raised.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper defines possible worlds and epistemic alternatives from the new primitive of belief bases rather than taking them as given, then supplies explicit semantic equivalence proofs between the resulting models and standard Kripke structures for both the basic epistemic language and its extension with 'only believing'. These proofs are internal to the manuscript and establish preservation of the intended semantics without reducing any target result to a fitted parameter, a self-citation chain, or an unverified assumption. The more compact construction of the universal epistemic model is therefore a derived consequence of the definitions plus the stated equivalences, not a circular renaming or self-definition. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Review performed from abstract only; full definitions, proofs, and background assumptions are unavailable. The ledger below is therefore minimal and provisional.

axioms (1)
  • standard math Standard axioms and semantics of epistemic logic (Kripke models, individual belief operators)
    The paper positions its contribution relative to existing epistemic logic.
invented entities (1)
  • belief base no independent evidence
    purpose: Primitive structure from which possible worlds and epistemic alternatives are derived
    New abstraction introduced to replace primitive worlds in the semantics.

pith-pipeline@v0.9.0 · 5647 in / 1153 out tokens · 18521 ms · 2026-05-24T18:04:54.880746+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

  1. [1]

    Aucher & V

    G. Aucher & V . Belle (2015): Multi-Agent Only Knowing on Planet Kripke. In: Proceedings of the Twenty- Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), AAAI Press, pp. 2713–2719

    work page 2015

  2. [2]

    Battigalli & M

    P. Battigalli & M. Siniscalchi (1999): Hierarchies of Conditional Beliefs and Interactive Epistemology in Dynamic Games. Journal of Economic Theory 88(1), pp. 188–230, doi:10.1006/jeth.1999.2555

    work page doi:10.1006/jeth.1999.2555 1999

  3. [3]

    Belle & G

    V . Belle & G. Lakemeyer (2010): Multi-Agent Only-Knowing Revisited . In: Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), AAAI Press, pp. 49–59

    work page 2010

  4. [4]

    Benferhat, D

    S. Benferhat, D. Dubois, H. Prade & M.-A. Williams (2002): A practical approach to revising prioritized knowledge bases. Studia Logica 70(1), pp. 105–130, doi:10.1023/A:1014606325783

    work page doi:10.1023/a:1014606325783 2002

  5. [5]

    van Benthem, J

    J. van Benthem, J. van Eijck, M. Gattinger & K. Su (2015):Symbolic Model Checking for Dynamic Epistemic Logic. In: Proceedings of the 5th International Workshop on Logic, Rationality and Interaction (LORI 2015), LNCS 9394, Springer-Verlag, pp. 366–378, doi:10.1093/comjnl/bxm009

    work page doi:10.1093/comjnl/bxm009 2015

  6. [6]

    van Benthem & D

    J. van Benthem & D. Klein (2019): Logics for Analyzing Games . In: Stanford Encyclopedia of Philosophy

    work page 2019

  7. [7]

    Bjorndahl & J

    A. Bjorndahl & J. Y . Halpern (2017): From Type Spaces to Probability Frames and Back, via Language . In: Proceedings of the Sixteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2017), pp. 75–87

    work page 2017

  8. [8]

    Blackburn, M

    P. Blackburn, M. de Rijke & Y . Venema: Modal Logic . Cambridge University Press, Cambridge, doi:10.1017/CBO9781107050884

    work page doi:10.1017/cbo9781107050884

  9. [9]

    Brandenburger & E

    A. Brandenburger & E. Dekel (1993): Hierarchies of Beliefs and Common Knowledge. Journal of Economic Theory 59, pp. 189–198, doi:10.1006/jeth.1993.1012

    work page doi:10.1006/jeth.1993.1012 1993

  10. [10]

    Charrier, A

    T. Charrier, A. Herzig, E. Lorini, F. Maffre & F. Schwarzentruber (2016): Building Epistemic Logic from Observations and Public Announcements. In: Proceedings of the Fifteenth International Conference on Prin- ciples of Knowledge Representation and Reasoning (KR 2016), AAAI Press, pp. 268–277

    work page 2016

  11. [11]

    H. P. van Ditmarsch, W. van der Hoek & B. Kooi (2007): Dynamic Epistemic Logic . Kluwer Academic Publishers, doi:10.1007/978-1-4020-5839-4

    work page doi:10.1007/978-1-4020-5839-4 2007

  12. [12]

    Fagin, , J

    R. Fagin, , J. Y . Halpern, & M. Y . Vardi (1991): A Model-Theoretic Analysis of Knowledge. Journal of the ACM 38(2), pp. 382–428, doi:10.1145/103516.128680

    work page doi:10.1145/103516.128680 1991

  13. [13]

    Fagin, J

    R. Fagin, J. Geanakoplos, J. Y . Halpern, & M. Y . Vardi (1999): The Hierarchical Approach to Mod- eling Knowledge and Common Knowledge . International Journal of Game Theory 28(3), pp. 331–365, doi:10.1007/s001820050114

    work page doi:10.1007/s001820050114 1999

  14. [14]

    Halpern, Y oram Moses & Moshe Y

    R. Fagin, J. Halpern, Y . Moses & M. Vardi (1995): Reasoning about Knowledge . MIT Press, Cambridge, doi:10.7551/mitpress/5803.001.0001

    work page doi:10.7551/mitpress/5803.001.0001 1995

  15. [15]

    Galeazzi & E

    P. Galeazzi & E. Lorini (2016): Epistemic logic meets epistemic game theory: a comparison between multi- agent Kripke models and type spaces. Synthese 193(7), pp. 2097–2127, doi:10.1007/s11229-015-0834-x

    work page doi:10.1007/s11229-015-0834-x 2016

  16. [16]

    Journal of Logic and Computation 2(1), pp

    V . Goranko & S. Passy (1992): Using the universal modality: gains and questions . Journal of Logic and Computation 2(1), pp. 5–30, doi:10.1093/logcom/2.1.5

    work page doi:10.1093/logcom/2.1.5 1992

  17. [17]

    Grädel & M

    E. Grädel & M. Otto (1999): On logics with two variables. Theoretical Computer Science 224, pp. 73–113, doi:10.1016/S0304-3975(98)00308-9. 346 Exploiting Belief Bases for Building Rich Epistemic Structures

    work page doi:10.1016/s0304-3975(98)00308-9 1999

  18. [18]

    J. Y . Halpern & G. Lakemeyer (2001): Multi-agent only knowing. Journal of Logic and Computation 11(1), pp. 41–70, doi:10.1093/logcom/11.1.41

    work page doi:10.1093/logcom/11.1.41 2001

  19. [19]

    J. Y . Halpern & Y . Moses (1992):A Guide to Completeness and Complexity for Modal Logics of Knowledge and Belief. Artificial Intelligence 54(2), pp. 319–379, doi:10.1016/0004-3702(92)90049-4

    work page doi:10.1016/0004-3702(92)90049-4 1992

  20. [20]

    S. O. Hansson (1993): Theory contraction and base contraction unified . Journal of Symbolic Logic 58(2), pp. 602–625, doi:10.1007/978-3-319-20451-2_14

    work page doi:10.1007/978-3-319-20451-2_14 1993

  21. [21]

    S. O. Hansson (1999): A Textbook of Belief Dynamics: Theory Change and Database Updating . Kluwer, Dordrecht, doi:10.1007/978-94-007-0814-3

    work page doi:10.1007/978-94-007-0814-3 1999

  22. [22]

    J. C. Harsanyi (1967): Games with incomplete information played by ‘Bayesian’ players. Management Sci- ence 14, pp. 159–182, doi:10.1287/mnsc.1040.0270

    work page doi:10.1287/mnsc.1040.0270 1967

  23. [23]

    Heifetz (1993): The Bayesian formulation of incomplete information: the non-compact case

    A. Heifetz (1993): The Bayesian formulation of incomplete information: the non-compact case. International Journal of Game Theory 21, pp. 329–338, doi:10.1007/BF01240148

    work page doi:10.1007/bf01240148 1993

  24. [24]

    Heifetz & D

    A. Heifetz & D. Samet (1998): Topology-Free Typology of Beliefs. Journal of Economic Theory 82, pp. 324–341, doi:10.1006/jeth.1998.2435

    work page doi:10.1006/jeth.1998.2435 1998

  25. [25]

    Wagner (1984): Aggregating Subjective Probabilities: Some Limitative Theorems

    E. Hemaspaandra (1996): The Price of Universality. Notre Dame Journal of Formal Logic 37(2), pp. 174– 203, doi:10.1305/ndjfl/1040046086

    work page doi:10.1305/ndj 1996

  26. [26]

    Hintikka (1962): Knowledge and Belief

    J. Hintikka (1962): Knowledge and Belief. An introduction to the logic of the two notions. Cornell University Press, New York

    work page 1962

  27. [27]

    van der Hoek, P

    W. van der Hoek, P. Iliev & M. Wooldridge (2012):A logic of revelation and concealment. In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012) , IFAAMAS, pp. 1115–1122

    work page 2012

  28. [28]

    Kets (2014): Finite Depth of Reasoning and Equilibrium Play in Games with Incomplete Information

    W. Kets (2014): Finite Depth of Reasoning and Equilibrium Play in Games with Incomplete Information . Northwestern University, Center for Mathematical Studies in Economics and Management Science Discus- sion Papers 1569

    work page 2014

  29. [29]

    Konieczny & R

    S. Konieczny & R. Pino Pérez (2002): Merging information under constraints: a logical framework. Journal of Logic and Computation 12(5), pp. 773–808, doi:10.1093/logcom/12.5.773

    work page doi:10.1093/logcom/12.5.773 2002

  30. [30]

    Lakemeyer (1993): All they know: a study in multi-agent autoepistemic reasoning

    G. Lakemeyer (1993): All they know: a study in multi-agent autoepistemic reasoning. In: Proceedings of the 13th International Joint Conference on Artificial intelligence (IJCAI’93), Morgan Kaufmann, pp. 376–381

    work page 1993

  31. [31]

    H. J. Levesque (1990): All I know: a study in autoepistemic logic. Artificial Intelligence 42(2-3), pp. 263–309, doi:10.1016/0004-3702(90)90056-6

    work page doi:10.1016/0004-3702(90)90056-6 1990

  32. [32]

    Lomuscio, H

    A. Lomuscio, H. Qu & F. Raimondi (2015): MCMAS: an open-source model checker for the verification of multi-agent systems . International Journal on Software Tools for Technology Transfer 19, pp. 1–22, doi:10.1007/s10009-015-0378-x

    work page doi:10.1007/s10009-015-0378-x 2015

  33. [33]

    Lorini (2018): In Praise of Belief Bases: Doing Epistemic Logic Without Possible Worlds

    E. Lorini (2018): In Praise of Belief Bases: Doing Epistemic Logic Without Possible Worlds. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), AAAI Press, pp. 1915–1922

    work page 2018

  34. [34]

    Lorini & F

    E. Lorini & F. Romero (2019): Decision procedures for epistemic logic exploiting belief bases. In: Proceed- ings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019) , ACM, pp. 944–952

    work page 2019

  35. [35]

    Makinson & L

    D. Makinson & L. van der Torre (2000): Input/output logics. Journal of Philosophical Logic29, pp. 383–408, doi:10.1023/A:1004748624537

    work page doi:10.1023/a:1004748624537 2000

  36. [36]

    J. F. Mertens & S. Zamir (1985): Formulation of Bayesian analysis for games with incomplete information . International Journal of Game Theory 14, pp. 1–29, doi:10.1007/BF01770224

    work page doi:10.1007/bf01770224 1985

  37. [37]

    J.-J. C. Meyer & W. van der Hoek (1995): Epistemic Logic for AI and Theoretical Computer Science. Cam- bridge University Press, Oxford, doi:10.1017/CBO9780511569852

    work page doi:10.1017/cbo9780511569852 1995

  38. [38]

    Reiter (1988): On integrity constraints

    R. Reiter (1988): On integrity constraints. In: Proceedings of the 2nd Conference on Theoretical aspects of Reasoning about Knowledge (TARK’88), Morgan Kaufmann Publishers, pp. 97–111. E. Lorini 347

    work page 1988

  39. [39]

    Shoham (2009): Logical Theories of Intention and the Database Perspective

    Y . Shoham (2009): Logical Theories of Intention and the Database Perspective . Journal of Philosophical Logic 38(6), pp. 633–648, doi:10.1007/s10992-009-9116-8

    work page doi:10.1007/s10992-009-9116-8 2009

  40. [40]

    Stalnaker (2002): Common ground

    R. Stalnaker (2002): Common ground . Linguistics and Philosophy 25(5-6), pp. 701–721, doi:10.1023/A:1020867916902

    work page doi:10.1023/a:1020867916902 2002

  41. [41]

    L. J. Stockmeyer (1973): Word problems requiring exponential time (Preliminary Report) . In: Pro- ceedings of the Fifth Annual ACM symposium on Theory of Computing (STOC ’73) , ACM, pp. 1–9, doi:10.1145/800125.804029. A Proofs This appendix presents a selection of the proofs of the technical results presented in the paper. A.1 Proof of Theorem 10 Proof. W...

    work page doi:10.1145/800125.804029 1973

  42. [42]

    Furthermore, by the fact that (B′,B⊤)|=⃝1p and (B′′,B⊤)|=⃝1p, we have that: ∀B′′′′∈ R[ [λ′] ](B′′),∃B′′′∈ R[ [λ′] ](B′) such that ( V′′′′∩ Atm(π) ) = ( V′′′∩ Atm(π) )

    Moreover, by the initial assumption that ( V∩ Atm(π) ) = ( V′∩ Atm(π) ) = ( V′′∩ Atm(π) ) , B(χ,V) 1 ⊆ B′ 1 and B(χ,V) 1 ⊆ B′′ 1, for all B′′′∈ ( R[ [λ′] ](B′)∪ R[ [λ′] ](B′′) ) we have: B(λ′.π,V∪{p}) 1 ⊆ B′′′ 1 ; B(λ′.π,V\{p}) 1 ⊆ B′′′ 1 ;( (V∪{ p})∩ Atm(π) ) = ( V′′′∩ Atm(π) ) or( (V\{ p})∩ Atm(π) ) = ( V′′′∩ Atm(π) ) . Furthermore, by the fact that (B′...

    work page