paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Demonic Lattices and Semilattices in Relational Semigroups with Ordinary Composition

具有普通复合的关系半群中的 demonic 格与半格
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 2/10 · 该论文属于关系代数与形式语义的理论工作,讨论 demonic 格运算下非确定性程序的全正确性表示问题,与用户关注的静态分析、LLM/Agent、浮点程序分析和贝叶斯程序分析没有直接交集。仅在最宽泛的“程序形式化推理”意义上与形式验证略有弱关联,因此匹配度很低。引用 0 inbox
Robin Hirsch, Jas Semrl
crossref: 2026-09-12

AI 速览

一句话:研究带普通复合与 demonic 格运算的关系半群,揭示其表示类的有限公理化与可判定性边界。

关系代数及其归约(reducts)可用来推理非确定性程序的部分正确性;demonic calculus 通过将非确定性视为恶魔控制,把此类推理扩展到全正确性。本文用带普通复合(ordinary composition)和 demonic 格运算的半群,形式化非确定性程序全正确性的关系推理框架。作者研究若干表示类:证明可表示 demonic 并半群类不可有限公理化;demonic 交半群表示类对其有限成员不具备有限表示性质。对于同时含复合、demonic 并与 demonic 交的格半群,证明有限代数的表示问题不可判定,有限表示问题亦不可判定,从而推出表示类不可有限公理化且有限表示性质失败。

问题
如何为带普通复合和 demonic 格运算的关系半群建立非确定性程序全正确性的关系推理框架,并刻画相应表示类的公理化与可判定性边界。
方法
以关系代数的归约、半群和 demonic 并/交运算为代数语义,研究表示类及其有限成员的性质。
评估
通过证明不可有限公理化、有限表示性质失败以及表示问题与有限表示问题的不可判定性等元数学结果来评估。
原文摘要(Abstract)

Relation algebra and its reducts provide us with a strong tool for reasoning about nondeterministic programs and their partial correctness. Demonic calculus, introduced to model the behaviour of a machine where the demon is in control of nondeterminism, has also provided us with an extension of that reasoning to total correctness. We formalise the framework for relational reasoning about total correctness in nondeterministic programs using semigroups with ordinary composition and demonic lattice operations. We show that the class of representable demonic join semigroups is not finitely axiomatisable and that the representation class of demonic meet semigroups does not have the finite representation property for its finite members. For lattice semigroups (with composition, demonic join and demonic meet) we show that the representation problem for finite algebras is undecidable, moreover the finite representation problem is also undecidable. It follows that the representation class is not finitely axiomatisable, furthermore the finite representation property fails.

链接与引用

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

BibTeX
@inproceedings{paperbot6213,
  title = {Demonic Lattices and Semilattices in Relational Semigroups with Ordinary Composition},
  author = {Robin Hirsch and Jas Semrl},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470509}
}