paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Linear-time logics -- a coalgebraic perspective

线性时间逻辑:一种余代数视角
LMCS vol.Volume 20, Issue 22024匹配度 1/10 · 该论文属于余代数视角下的线性时间逻辑与形式语义理论研究,重在语义等价性证明,与用户画像的核心方向(ML/Agentic 程序的静态分析、LLM 与静态分析/形式化验证的交叉、浮点或贝叶斯程序分析)没有直接交集,也未涉及工具落地或 benchmark 问题。引用 2 inbox
Corina Cirstea
crossref: 2026-09-10

AI 速览

一句话:用余代数统一构造线性时间逻辑,并证明逐步语义与路径语义等价。

本文提出一种从余代数视角统一推导线性时间逻辑的一般方法,面向广泛的状态基定量系统。作者将系统建模为一种余代数,其类型同时编码分支行为与线性行为;逻辑的语法由线性行为类型决定,真值域由分支行为类型决定。论文给出两种语义:类似标准余代数逻辑的逐步语义,以及类似标准线性时间逻辑的路径语义,前者便于模型检测,后者更自然地度量给定状态沿计算路径满足定性属性的程度。主要结果是两种语义的等价,并对由这些逻辑诱导的逻辑距离给出语义刻画。实例表明该框架可推理线性时间属性的可能性、似然或最小代价。

问题
如何为状态基、定量系统统一地构造线性时间逻辑,并给出既便于模型检测又符合路径直觉的语义?
方法
把系统建模为同时包含分支与线性行为的余代数;由线性行为类型确定逻辑语法、分支行为类型确定真值域,并定义逐步语义与路径语义。
评估
以两种语义等价为主要理论结果,并给出逻辑距离的语义刻画;通过可能性、似然和最小代价等实例说明适用性。
原文摘要(Abstract)

We describe a general approach to deriving linear-time logics for a wide variety of state-based, quantitative systems, by modelling the latter as coalgebras whose type incorporates both branching and linear behaviour. Concretely, we define logics whose syntax is determined by the type of linear behaviour, and whose domain of truth values is determined by the type of branching behaviour, and we provide two semantics for them: a step-wise semantics akin to that of standard coalgebraic logics, and a path-based semantics akin to that of standard linear-time logics. The former semantics is useful for model checking, whereas the latter is the more natural semantics, as it measures the extent with which qualitative properties hold along computation paths from a given state. Our main result is the equivalence of the two semantics. We also provide a semantic characterisation of a notion of logical distance induced by these logics. Instances of our logics support reasoning about the possibility, likelihood or minimal cost of exhibiting a given linear-time property.

链接与引用

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

BibTeX
@article{paperbot2755,
  title = {Linear-time logics -- a coalgebraic perspective},
  author = {Corina Cirstea},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 20, Issue 2},
  year = {2024},
  doi = {10.46298/lmcs-20(2:13)2024}
}