CS Paper Radar

Monad Structures on Topological Spaces Comprising Mislove's Random Variables

Chengyu Zhou, Qingguo Li

cs.LO ·submitted 2026-08-19 08:33 UTC · v1

Abstract

Mislove, Goubault and Varacca investigated how to define random variables in Domain theory to form monads over the category of bounded complete domains. They intended to model probabilistic programming languages with their random variables monads. In this paper, we focus on the random variables defined by Mislove from a topological perspective. We provide a topology for $\surd$-max continuous random variables on a $T_0$ space, we construct a new $T_0$ space, where $\surd$-max property is essential for the monad structures. We show that the spaces of normalized $\surd$-max simple random variables form a monad over the category of $T_0$ spaces and that the spaces of normalized $\surd$-max continuous random variables give a monad over the category of d-spaces. In addition, on a sober space, the space of normalized $\surd$-max continuous random variables is the sobrification of the space of normalized $\surd$-max simple random variables.

Closest papers

Nearest neighbours by meaning across the whole index.

Metrization of Quasi-Uniformities, Powerset Monads, and Qualitative Robustness Analysis

cs.LO math.GN ·2026-09-02 ·Francesco Dagnino, Amin Farjudian, Eugenio Moggi
theory similarity 0.64
Abstract · 24 pages

We study the relationship between quasi-uniform spaces, topological spaces, and quantale-valued metric spaces. Our main result is a metrization theorem establishing an equivalence between the category of quasi-uniform spaces and a category of quantale-valued metric spaces. We also obtain a quantale-based metrization theorem for arbitrary topological spaces that refines existing constructions. These results identify quasi-uniformities as the appropriate qualitative counterpart of quantale-valued metrics. Building on this correspondence, we show that the Hausdorff-Smyth monad on quantale-valued metric spaces, which is used in quantitative robustness analysis, arises as a lifting of a corresponding monad on quasi-uniform spaces along the equivalence. This provides a unified categorical framework connecting topology, quasi-uniformity, and quantitative robustness analysis.

0.23

Compositional Information Geometry of Probabilistic Programs

cs.PL cs.CG ·2026-10-13 ·Jacek Karwowski, Frank Nielsen, Sam Staton
highly cited similarity 0.58
Abstract

We study the compositional, intensional information geometry of probabilistic programs. For a first-order probabilistic programming language with finite random variables, we construct a contravariant lax monoidal functor that, for a program of type $X \to Y$, pulls back a (degenerate) Riemannian metric on $Y$ to $X$. It specialises to the Fisher metric in the case of standard statistical models and to ordinary pullback in the case of deterministic programs. We further justify this construction in two ways. First, we show that this functor arises as a pullback of geometry from a universal space of programs over a type $Y$ with a fixed trace space. Second, we show that it is a special case of a more general pullback construction over weighted measures. Our compositional geometry depends on the presentation of the program, and we study how it relates to the (non-compositional) geometry of the realised measures by establishing a three-level inequality relating our score-velocity metric for the program, the program's corresponding output-conditioned metric, and the standard Wasserstein-Fisher-Rao metric of the realised family. Finally, we show how the theory can be extended to accommodate continuous random variables using diffeological quasi-Borel spaces. We also discuss several concrete directions for future work.

0.43

Sample-Smooth Spaces: A Convenient Category for Differentiable Probabilistic Programming

cs.LG math.CTcs.LOcs.PL+1 ·2026-08-14 ·Patrick Forré
theory similarity 0.55
Abstract

We introduce the category $\mathbf{SSS}$ of sample-smooth spaces over a mixed site. The test objects are the products $Ω_n := \mathbb{R}^n \times Ω$ of a Cartesian space with the universal Hilbert cube $Ω$ carrying all universally measurable sets, and a space is a set with a family of admissible plots $Ω_n \to \mathcal{X}$ closed under precomposition. Smoothness and measurability are then not two structures glued along an axiom, but one structure over one site. The site has finite non-empty products, because $Ω$ absorbs its own square; its Karoubi envelope contains every $\mathbb{R}^n$; and it has mixed morphisms $ω\mapsto (W(ω),Φ(ω))$, which turn measurability of a smooth family from an axiom into a consequence. $\mathbf{SSS}$ is a concrete quasitopos: complete, cocomplete, cartesian closed and locally cartesian closed, with a classifier for embeddings. Morphisms of Cartesian spaces are exactly the $C^\infty$ maps and manifolds embed full and faithfully, both without Boman's theorem. Every object has tangent and cotangent spaces, every morphism a differential. The modalities sit in an adjoint string $Π\dashv \flat \dashv \natural \dashv \sharp \dashv Λ$, making $\mathbf{SSS}$ cohesive over quasi-universal spaces. The point is the probability monad. Defining the plots of $\mathsf{P}(\mathcal{X})$ as push-forwards of $\mathcal{X}$-plots at every test object, $\mathsf{P}$ is an unconditional strong commutative affine monad on all of $\mathbf{SSS}$ -- functor, unit, product of kernels, multiplication and the monad laws are each one line of seed splitting -- and its Kleisli category, of differentiable simulators, is a Markov category. The reparametrisation trick holds by construction: every Kleisli morphism is plot-wise a sampler, stably under composition. A reflection theorem locates the whole gain in a single plot family.

0.04

Fibered Separation Logic: Weakest Preconditions, Universal Constructions, and Local Independence

cs.PL cs.LO ·2026-11-05 ·John M. Li, Ryan Doenges, Pedro H. Azevedo de Amorim
similarity 0.53
Abstract · 41 pages, 5 figures

This paper introduces a categorical framework for models of higher-order separation logic including the weakest precondition modality. Weakest preconditions are interpreted by strong monads on a category fibered over a model of Moggi's computational lambda calculus. The fibered categories in question are termed bunched fibrations and shown to be equivalent to BI hyperdoctrines. Well-known heuristic techniques for obtaining weakest preconditions are shown to be expressible in categorical terms and are proved sound. The ``baking in the frame rule'' trick is shown to satisfy a universal property. Constructions are given for extending a program logic with cost credits. Our largest case study is parametrized by a category having local independent product (LIP) structure, a notion due to Simpson that axiomatizes name generation, randomness, and local state. From an LIP category, we construct an allocation monad, a bunched fibration, and a monad lifting. We instantiate our construction to obtain a novel probabilistic separation logic for measure-theoretic probability that both simplifies and clarifies prior work.

0.31

Bayes Rule for Conditioning Probabilistic Programs

cs.PL cs.LO ·2026-10-07 ·Feras A. Saad
similarity 0.53
Abstract

Probabilistic programs provide a rigorous programming-language foundation for expressing rich probabilistic models and offer language-level support for solving challenging statistical inference problems. A key theoretical challenge that probabilistic programs inherit from probability theory is conditioning a probability distribution on an observation that has probability zero. Many languages address this challenge by using computational rules for conditioning that may work well for some problems but are statistically unsound for others. This article introduces a principled mathematical approach for conditioning probabilistic programs. We first show that existing techniques based on "soft conditioning" and "neighborhood limits" exhibit semantic issues from the perspective of measure theory and produce inference results that disagree with sound statistical reasoning. By leveraging tools from geometric measure theory, we construct a novel disintegration-based semantics for probabilistic program traces that enables sound conditioning. The theory delivers an explicit Bayes rule representation of the conditional distribution, which is directly compatible with widely used probabilistic inference algorithms that require access to unnormalized posterior densities. Our Bayes rule handles probabilistic models with loops, branches, discrete, continuous, and mixed-type distributions, observations on manifolds, differentiable structure, and additional modeling motifs that arise in practice.

0.15

A Hoare Logic for Continuous-Time Stochastic Processes

cs.LO cs.PLmath.PR ·2026-11-09 ·Kei Imada, Justin Hsu
similarity 0.53
Abstract

Programming language researchers have developed a wide array of tools to reason about probabilistic programs, but it remains unclear how to apply these proof techniques to continuous-time stochastic processes. To bridge this gap, we propose a verification method for properties of continuous-time stochastic processes by reasoning about them as standard programs. To demonstrate our approach, we define a continuous semantics for a probabilistic imperative language $\mathrm{pWhile}^{\mathrm{dt}}$ by taking the Kuratowski limit of the standard semantics, which collects limit points of the standard program semantics as the time-step approaches zero. Then, we present a Hoare-style logic that uses loop invariants and decreasing functions to verify properties of continuous programs. To establish soundness, we identify a broad class of assertions that are preserved from the standard semantics to the continuous semantics. To demonstrate our approach, we verify properties of ten continuous-time stochastic processes modeled in $\mathrm{pWhile}^{\mathrm{dt}}$, including variants of Brownian motion and a stochastic hybrid system.

0.41

Contributions to the hierarchy of probabilistic languages

cs.FL cs.CLmath.LOmath.PR ·2026-09-20 ·Lothar Sebastian Krapp, Remo Nitschke
similarity 0.51
Abstract

We reconsider the theory of probabilistic formal languages generated by n-gram models and by probabilistic context-free grammars (PCFGs). The expected hierarchy of probabilistic grammars is established by proving that every probabilistic language generated by an n-gram model is also generated by some PCFG, while some probabilistic languages generated by PCFGs cannot be generated by any $n$-gram model. We introduce the notion of fully connected PCFGs, namely PCFGs in Chomsky normal form where every production rule only involving non-terminals has non-zero probability. Our main result shows that any probabilistic language generated by an $n$-gram model differs from any probabilistic language generated by a fully connected PCFG. Therefore, the class of probabilistic languages generated by $n$-gram models is not a subset of the class generated by fully connected PCFGs.

0.46

A Taxonomy of Predicate Transformer Monads for Specifying Monadic Programs

cs.PL ·2026-10-16 ·Abigail Pribisova, Yao Li, Cezar-Constantin Andrici, Catalin Hritcu, Kenji Maillard +1 more
similarity 0.51
Abstract · Submitted to ESOP'27, in v2 same PDF but fixed author order in metadata

Monads of weakest precondition predicate transformers are the foundation of several verification frameworks for monadic programs. For specifying monadic computations with nondeterminism and nontermination, in addition to weakest preconditions, we introduce the first strongest postcondition monads covering all combinations of angelic or demonic nondeterminism and partial or total interpretations of nontermination. For extending these base strongest postcondition monads with side effects such as mutable state, monad transformers do not yield the expected monads, so we instead generalize the base monads to arrows and use arrow transformers. We give a taxonomy of weakest precondition and strongest postcondition monads, for the base monads and for their versions with state, and show that the known relationships between under- and over-approximate triples based on predicate transformers already hold at the level of the predicate transformers themselves. We use the predicate transformer monads to define under- and over-approximate triples and, where possible, Dijkstra monads. Finally, we relate these two specification styles.

0.06