![]() |
![]() |
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.