paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On Free $\omega$-Continuous and Regular Ordered Algebras

论自由 ω-连续与正则有序代数
LMCS vol.Volume 15, Issue 42019匹配度 1/10 · 该论文属于纯形式语义与代数理论,研究有序代数、自由代数、Σ-余项单子和ω-连续/正则结构,未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等用户核心方向。虽然 Kleene 代数、迭代理论等与程序验证有间接理论联系,但距离用户研究画像过远。引用 0 inbox
Zoltan Esik, Dexter Kozen
crossref: 2026-09-10

AI 速览

一句话:用 Σ-余项单子的子单子刻画准正则有序代数簇的自由代数,并给出 ω-连续与正则有序代数自由代数的关系。

本文研究具有受限完备性与连续性性质的有序 Σ-代数簇,旨在统一构造其自由代数。作者提出“准正则”簇的概念,利用 Σ-余项(Σ-coterms)单子的子单子来刻画这类簇的自由代数,将自由代数中的元素对应于可由特定余项指称的元素。作为特例,给定有限 Σ-项之间的不等式集 E,令 V_ω 与 V_reg 分别为满足 E 的 ω-连续有序 Σ-代数簇和正则有序 Σ-代数簇;则 V_reg 在生成元 X 上的自由代数 F_reg(X) 恰好是相应 V_ω 自由代数 F_ω(X) 中由正则 Σ-余项指称的元素构成的子代数。该构造适用于任意准正则族,并统一了 *-连续 Kleene 代数、上下文无关语言、ω-连续半环、ω-连续幂等半环、OI-macro 语言和迭代理论等例子。

问题
如何刻画具有受限完备性与连续性性质的有序 Σ-代数簇的自由代数,尤其是 ω-连续与正则有序代数自由代数之间的关系。
方法
引入准正则簇,利用 Σ-余项单子的子单子刻画自由代数;并证明正则自由代数是 ω-连续自由代数中由正则 Σ-余项指称的元素构成的子代数。
评估
通过数学证明和一系列实例(*-连续 Kleene 代数、上下文无关语言、ω-连续半环与幂等半环、OI-macro 语言、迭代理论)展示该构造的普适性。
原文摘要(Abstract)

We study varieties of certain ordered $\Sigma$-algebras with restricted completeness and continuity properties. We give a general characterization of their free algebras in terms of submonads of the monad of $\Sigma$-coterms. Varieties of this form are called \emph{quasi-regular}. For example, we show that if $E$ is a set of inequalities between finite $\Sigma$-terms, and if $\mathcal{V}_\omega$ and $\mathcal{V}_\mathrm{reg}$ denote the varieties of all $\omega$-continuous ordered $\Sigma$-algebras and regular ordered $\Sigma$-algebras satisfying $E$, respectively, then the free $\mathcal{V}_\mathrm{reg}$-algebra $F_\mathrm{reg}(X)$ on generators $X$ is the subalgebra of the corresponding free $\mathcal{V}_\omega$-algebra $F_\omega(X)$ determined by those elements of $F_\omega(X)$ denoted by the regular $\Sigma$-coterms. This is a special case of a more general construction that applies to any quasi-regular family. Examples include the *-continuous Kleene algebras, context-free languages, $\omega$-continuous semirings and $\omega$-continuous idempotent semirings, OI-macro languages, and iteration theories.

链接与引用

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

BibTeX
@article{paperbot748,
  title = {On Free $\omega$-Continuous and Regular Ordered Algebras},
  author = {Zoltan Esik and Dexter Kozen},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 4},
  year = {2019},
  doi = {10.23638/lmcs-15(4:4)2019}
}