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