Zoltan Esik ; Dexter Kozen - On Free ω-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 ω-Continuous and Regular Ordered AlgebrasArticle

Authors: Zoltan Esik ; Dexter Kozen

    We study varieties of certain ordered Σ-algebras with restricted completeness and continuity properties. We give a general characterization of their free algebras in terms of submonads of the monad of Σ-coterms. Varieties of this form are called \emph{quasi-regular}. For example, we show that if E is a set of inequalities between finite Σ-terms, and if Vω and Vreg denote the varieties of all ω-continuous ordered Σ-algebras and regular ordered Σ-algebras satisfying E, respectively, then the free Vreg-algebra Freg(X) on generators X is the subalgebra of the corresponding free Vω-algebra Fω(X) determined by those elements of Fω(X) denoted by the regular Σ-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, ω-continuous semirings and ω-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 2141 times.
    This article's PDF has been downloaded 504 times.