Zoltan Esik ; Dexter Kozen - On Free $\omega$-Continuous and Regular Ordered Algebras

lmcs:2586 - Logical Methods in Computer Science, October 29, 2019, Volume 15, Issue 4 - https://doi.org/10.23638/LMCS-15(4:4)2019
On Free $\omega$-Continuous and Regular Ordered AlgebrasArticle

Authors: Zoltan Esik ; Dexter Kozen

    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.


    Volume: Volume 15, Issue 4
    Published on: October 29, 2019
    Accepted on: August 28, 2019
    Submitted on: December 8, 2016
    Keywords: Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 1721 times.
    This article's PDF has been downloaded 377 times.