| Summary: | 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.
|
|---|