paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Semipullbacks of labelled Markov processes

标记马尔可夫过程的半拉回
LMCS vol.Volume 17, Issue 22021匹配度 2/10 · 该论文属于纯形式语义与范畴论工作,研究标记马尔可夫过程的行为等价与 semipullback,与用户核心关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析及其交叉方向无直接关联;仅在概率计算形式化方面有边缘联系。引用 2 inbox
Jan Pachl, Pedro Sánchez Terraf
crossref: 2026-09-10

AI 速览

一句话:将标记马尔可夫过程中行为等价可构造互模拟 semipullback 的结果推广到更广的可测空间。

标记马尔可夫过程(LMP)由可测空间及一族 Markov kernel 组成,用于建模概率计算。其核心问题是判断两个 LMP 是否行为相同:互模拟要求存在共同的 LMP 通过保测映射分别映射到二者,行为等价则要求存在共同的余锥。二者对一般可测空间不等价;Doberkat 在 Edalat 工作基础上证明,对 analytic Borel 空间二者一致,且可从行为等价图构造出交换的 semipullback。本文把该结果推广到与 Polish 空间的普遍可测子集同构、并带上 Borel σ-代数迹的可测空间。证明使用 Strassen 定理的一个版本,处理有限可加测度的共同扩展,从而在更广空间类上得到所需的 semipullback。

问题
问题:对标记马尔可夫过程,互模拟与行为等价两种范畴式行为相同定义在一般可测空间上不一致;已有结果仅覆盖 analytic Borel 空间,本文关注能否推广到更广的可测空间类。
方法
方法:采用范畴论与测度论证明,将行为等价图转化为互模拟的交换 semipullback,并借助 Strassen 关于有限可加测度共同扩展的定理版本。
评估
评估:纯数学证明,推广 Doberkat 与 Edalat 的结果,表明在普遍可测子集(带 Borel 迹)这类空间上行为等价仍可推出 semipullback。
原文摘要(Abstract)

A labelled Markov process (LMP) consists of a measurable space $S$ together with an indexed family of Markov kernels from $S$ to itself. This structure has been used to model probabilistic computations in Computer Science, and one of the main problems in the area is to define and decide whether two LMP $S$ and $S'$ "behave the same". There are two natural categorical definitions of sameness of behavior: $S$ and $S'$ are bisimilar if there exist an LMP $ T$ and measure preserving maps forming a diagram of the shape $ S\leftarrow T \rightarrow{S'}$; and they are behaviorally equivalent if there exist some $ U$ and maps forming a dual diagram $ S\rightarrow U \leftarrow{S'}$. These two notions differ for general measurable spaces but Doberkat (extending a result by Edalat) proved that they coincide for analytic Borel spaces, showing that from every diagram $S\rightarrow U \leftarrow{S'}$ one can obtain a bisimilarity diagram as above. Moreover, the resulting square of measure preserving maps is commutative (a semipullback). In this paper, we extend the previous result to measurable spaces $S$ isomorphic to a universally measurable subset of a Polish space with the trace of the Borel $\sigma$-algebra, using a version of Strassen's theorem on common extensions of finitely additive measures.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1325,
  title = {Semipullbacks of labelled Markov processes},
  author = {Jan Pachl and Pedro Sánchez Terraf},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 2},
  year = {2021},
  doi = {10.23638/lmcs-17(2:3)2021}
}