pith. sign in

arxiv: 2604.25355 · v3 · pith:LZHW2GCUnew · submitted 2026-04-28 · 💻 cs.LO

From Coalgebraic Determinization to Belief Construction for Partial Observability

Mayuko Kori , Kazuki Watanabe This is my paper

Pith reviewed 2026-07-01 08:57 UTC · model grok-4.3

classification 💻 cs.LO
keywords coalgebraic determinizationbelief constructionpartial observabilityPOMDPsmonad liftingslice categoriesweighted transition systems
0
0 comments X

The pith

The semantics of a partially observable system coincides with that of the corresponding belief coalgebra.

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

The paper develops a coalgebraic framework for the belief construction that converts partially observable systems into fully observable ones while preserving semantics. It lifts a monad to slice categories and introduces a belief decomposition to reorganize states by observations. This is combined with coalgebraic determinization to generalize the belief construction. The authors show that the semantics of the original system match those of the belief coalgebra, and under further conditions also match the fully observable counterpart. This recovers the standard POMDP to belief MDP equivalence and yields a new result for weighted transition systems.

Core claim

By lifting a monad to slice categories and introducing a belief decomposition that reorganizes states according to their observations, the authors combine it with the coalgebraic determinization of Silva et al. to obtain a coalgebraic generalization of the belief construction. In this framework the semantics of a partially observable system coincides with that of the corresponding belief coalgebra. The paper then studies when the belief coalgebra further agrees with its fully observable counterpart and uses this to identify conditions under which the semantics of a partially observable system coincides with that of the corresponding fully observable belief system.

What carries the argument

Belief decomposition together with monad lifting to slice categories, combined with coalgebraic determinization.

If this is right

  • The semantics of POMDPs coincide with those of the corresponding belief MDPs.
  • A new equivalence holds between weighted transition systems with the semimodule monad and their belief counterparts.
  • Conditions are identified under which the semantics of a partially observable system coincides with that of its fully observable belief system.

Where Pith is reading between the lines

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

  • The same lifting and decomposition steps could be instantiated for other monads that model different notions of observation or nondeterminism.
  • The coalgebraic setting may allow compositional constructions when partial observability appears inside larger systems.
  • The framework supplies a uniform way to derive determinization results for new classes of systems once a suitable monad and decomposition are exhibited.

Load-bearing premise

The belief decomposition and monad lifting to slice categories preserve the relevant semantics when combined with coalgebraic determinization.

What would settle it

A concrete partially observable system and monad for which the accepted language or behavior of the original coalgebra differs from that of the constructed belief coalgebra.

read the original abstract

The belief construction is a fundamental technique for transforming partially observable systems to fully observable ones while preserving the relevant semantics. It plays a central role in the analysis of partially observable systems, in particular partially observable Markov decision processes (POMDPs), which is a central model in artificial intelligence and formal verification. In this paper, we develop a coalgebraic framework for the belief construction. To handle observations categorically, we lift a monad to slice categories and introduce a belief decomposition that reorganizes states according to their observations. This allows us to introduce a coalgebraic generalization of the belief construction, obtained by combining the belief decomposition with the coalgebraic determinization of Silva, Bonchi, Bonsangue, and Rutten. In this framework, we show that the semantics of a partially observable system coincides with that of the corresponding belief coalgebra. We then study when the latter further agrees with the semantics of its fully observable counterpart, and use this to identify conditions under which the semantics of a partially observable system coincides with that of the corresponding fully observable belief system. As consequences, we recover the standard equivalence between POMDPs and belief MDPs, and obtain a new equivalence result for weighted transition systems with the semimodule monad.

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

1 major / 2 minor

Summary. The paper develops a coalgebraic framework for the belief construction on partially observable systems. It lifts monads to slice categories to handle observations categorically, defines a belief decomposition that reorganizes states by observations, and obtains a coalgebraic generalization by composing this decomposition with the coalgebraic determinization of Silva et al. The central results are that the semantics of a partially observable coalgebra coincides with the semantics of the corresponding belief coalgebra, together with conditions under which the belief coalgebra further agrees with its fully observable counterpart; as consequences the standard POMDP–belief-MDP equivalence is recovered and a new equivalence is obtained for weighted transition systems under the semimodule monad.

Significance. If the derivations hold, the work supplies a uniform categorical account of belief constructions that recovers a well-known equivalence and yields a new one for the semimodule monad. The explicit use of monad liftings to slice categories and the composition with existing coalgebraic determinization constitute reusable technical machinery that could support further coalgebraic analyses of partial observability.

major comments (1)
  1. [§4] §4 (the composition theorem): the proof that the lifted monad on the slice category commutes with the determinization functor up to the semantics functor is load-bearing for both the general coincidence result and the new semimodule-monad equivalence; the side conditions required on the monad (e.g., preservation of the relevant final-coalgebra semantics) are stated only informally and should be made explicit with a precise statement of the required naturality or Beck–Chevalley condition.
minor comments (2)
  1. Notation for the slice-category monad lifting is introduced without an explicit diagram showing the two functors involved; adding such a diagram would clarify the belief decomposition.
  2. The statement of the new equivalence for weighted transition systems should cite the precise semimodule (e.g., the free semimodule over a semiring) used in the example.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comment point by point below.

read point-by-point responses

  1. Referee: [§4] §4 (the composition theorem): the proof that the lifted monad on the slice category commutes with the determinization functor up to the semantics functor is load-bearing for both the general coincidence result and the new semimodule-monad equivalence; the side conditions required on the monad (e.g., preservation of the relevant final-coalgebra semantics) are stated only informally and should be made explicit with a precise statement of the required naturality or Beck–Chevalley condition.

    Authors: We agree that the side conditions on the monad in the composition theorem of §4 are stated only informally. In the revised manuscript we will replace the informal description with an explicit statement of the required hypotheses, formulated as naturality conditions on the relevant diagrams together with any Beck–Chevalley condition needed to ensure that the lifted monad commutes with the determinization functor up to the semantics functor. This will make the theorem’s hypotheses fully precise and will allow direct verification for the semimodule monad and other concrete instances. revision: yes

Circularity Check

0 steps flagged

No circularity: new categorical lifts composed with external determinization yield independent equivalence proof

full rationale

The paper introduces monad lifting to slice categories and belief decomposition as original constructions, then combines them with the coalgebraic determinization of Silva et al. (distinct authors) to prove that partially observable coalgebra semantics coincides with belief coalgebra semantics. This yields recovered POMDP equivalence and a new result for semimodule monads. No self-definitional steps, no fitted parameters renamed as predictions, and the cited determinization is external rather than a self-citation chain. The central claim rests on a compositional proof of semantics preservation, not on presupposing the result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The framework rests on standard category-theoretic constructions (monad lifting, slice categories) and the cited prior coalgebraic determinization result; no free parameters, ad-hoc axioms, or invented entities are visible in the abstract.

axioms (2)
  • standard math Standard properties of monads and slice categories in category theory
    Invoked when lifting a monad to slice categories to handle observations
  • domain assumption Semantics preservation under the cited coalgebraic determinization construction
    Used when combining the belief decomposition with determinization to obtain the belief coalgebra

pith-pipeline@v0.9.1-grok · 5749 in / 1368 out tokens · 73333 ms · 2026-07-01T08:57:02.269010+00:00 · methodology

Review history (3 revisions) →

discussion (0)

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

Reference graph

Works this paper leans on

20 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Dual- and multi-energy CT: principles, technical approaches, and clinical applications,

    C. H. McCollough, S. Leng, L. Yu, and J. G. Fletcher, “Dual- and multi-energy CT: principles, technical approaches, and clinical applications,”Radiology, vol. 276, no. 3, pp. 637–653, 2015

    2015

  2. [2]

    Energy-selective reconstructions in X-ray comput- erized tomography,

    R. E. Alvarez and A. Macovski, “Energy-selective reconstructions in X-ray comput- erized tomography,”Phys. Med. Biol., vol. 21, no. 5, pp. 733–744, 1976

    1976

  3. [3]

    Material differentiation by dual energy CT: initial experi- ence,

    T. R. C. Johnsonet al., “Material differentiation by dual energy CT: initial experi- ence,”Eur. Radiol., vol. 17, no. 6, pp. 1510–1517, 2007

    2007

  4. [4]

    Dual-energy CT-based monochromatic imag- ing,

    L. Yu, S. Leng, and C. H. McCollough, “Dual-energy CT-based monochromatic imag- ing,”Am. J. Roentgenol., vol. 199, no. 5, pp. S9–S15, 2012

    2012

  5. [5]

    Empirical dual energy calibration (EDEC) for cone-beam computed tomography,

    P. Stenner, T. Berkus, and M. Kachelriess, “Empirical dual energy calibration (EDEC) for cone-beam computed tomography,”Med. Phys., vol. 34, no. 9, pp. 3630– 3641, 2007

    2007

  6. [6]

    Quantitative imaging of element composition and mass fraction using dual-energy CT: three-material decom- position,

    X. Liu, L. Yu, A. N. Primak, and C. H. McCollough, “Quantitative imaging of element composition and mass fraction using dual-energy CT: three-material decom- position,”Med. Phys., vol. 36, no. 5, pp. 1602–1609, 2009

    2009

  7. [7]

    Advanced empirical dual energy calibration,

    L. Hellwege, M. Schaar, T. M. Buzug, and M. Stille, “Advanced empirical dual energy calibration,” inProc. IEEE NSS-MIC-RTSD, Vancouver, BC, Canada, 2023

    2023

  8. [8]

    Multi-material decomposition using statistical image reconstruction for spectral CT,

    Y. Long and J. A. Fessler, “Multi-material decomposition using statistical image reconstruction for spectral CT,”IEEE Trans. Med. Imaging, vol. 33, no. 8, pp. 1614– 1626, 2014

    2014

  9. [9]

    Joint statistical iterative material image reconstruction for spectral computed tomography using a semi-empirical forward model,

    K. Mechlem, S. Prinber, S. Ehnet al., “Joint statistical iterative material image reconstruction for spectral computed tomography using a semi-empirical forward model,”IEEE Trans. Med. Imaging, vol. 37, no. 1, pp. 68–80, 2018

    2018

  10. [10]

    Multi-energy CT decomposition using convolutional neural networks,

    D. P. Clark, M. Holbrook, and S. Bhardwaj, “Multi-energy CT decomposition using convolutional neural networks,” inProc. SPIE, vol. 10573, 2018, p. 1057310

    2018

  11. [11]

    Image decomposition algorithm for dual-energy computed tomography via fully convolutional network,

    Y. Xu, B. Yan, J. Zhanget al., “Image decomposition algorithm for dual-energy computed tomography via fully convolutional network,”Comput. Math. Methods Med., vol. 2021, p. 6624957, 2021

    2021

  12. [12]

    Unsupervised CT super-resolution with hybrid model,

    Z. Chen, Y. Gao, and Y. Liu, “Unsupervised CT super-resolution with hybrid model,” Comput. Biol. Med., vol. 145, p. 105407, 2022

    2022

  13. [13]

    Noise2Inverse: Self-supervised deep convolutional denoising for tomography,

    A. A. Hendriksen, D. M. Pelt, and K. J. Batenburg, “Noise2Inverse: Self-supervised deep convolutional denoising for tomography,”IEEE Trans. Comput. Imaging, vol. 6, pp. 1320–1335, 2020

    2020

  14. [14]

    Unsupervised deep learning for inverse problems in computed tomography,

    L. Hellwege, J. C. Engster, M. Schaar, T. M. Buzug, and M. Stille, “Unsupervised deep learning for inverse problems in computed tomography,”BMC Med. Imaging, submitted, 2024. 11

    2024

  15. [15]

    DL-Spectral CT Challenge

    AAPM, “DL-Spectral CT Challenge.” [Online]. Available: https://www.aapm.org/GrandChallenge/DL-spectral-CT/

  16. [16]

    UNet++: A nested U- Net architecture for medical image segmentation,

    Z. Zhou, M. M. R. Siddiquee, N. Tajbakhsh, and J. Liang, “UNet++: A nested U- Net architecture for medical image segmentation,” inDeep Learning in Medical Image Analysis and Multimodal Learning for Clinical Decision Support. Cham, Switzerland: Springer, 2018, pp. 3–11

    2018

  17. [17]

    Aggregated residual transformations for deep networks,

    S. Xie, R. Girshick, P. Doll´ ar, Z. Tu, and K. He, “Aggregated residual transformations for deep networks,” inProc. IEEE CVPR, Honolulu, HI, USA, 2017, pp. 1492–1500

    2017

  18. [18]

    Segmentation models PyTorch,

    P. Iakubovskii, “Segmentation models PyTorch,” 2019. [Online]. Available: https://github.com/qubvel/segmentation models.pytorch

    2019

  19. [19]

    Adam: A Method for Stochastic Optimization

    D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” arXiv preprint arXiv:1412.6980, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  20. [20]

    Image quality assessment: From error visibility to structural similarity,

    Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: From error visibility to structural similarity,”IEEE Trans. Image Process., vol. 13, no. 4, pp. 600–612, 2004. 12

    2004