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

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.