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

Ordered algebras abound in program logics and programming language semantics: $\omega$-continuous semirings, star-continuous Kleene algebras and Kleene algebras with tests, context-free languages, OI-macro languages, iteration theories, recursion schemes, and Scott domains, among many others. These structures are all examples of varieties of ordered $\Sigma$-algebras with restricted completeness and continuity properties. In this talk I will give a general characterization of the free algebras of such varieties in terms of submonads of the monad of $\Sigma$-coterms. Varieties of this form are called quasi-regular. For example, the free star-continuous Kleene algebra is the subalgebra of the corresponding free $\Sigma$-continuous semiring determined by those elements denoted by the regular $\Sigma$-coterms, where $\Sigma$ is the signature of Kleene algebra. This is a special case of a more general construction that applies to any quasi-regular family, including all the examples mentioned above.
(joint work with Zoltán Ésik)