# On Free ω-Continuous and Regular Ordered Algebras

### Dexter Kozen

Ordered algebras abound in computer science: ω-continuous semirings, Kleene algebras and Kleene algebras with tests, context-free languages, OI-macro languages, iteration theories, recursion schemes, and Scott domains, among many others. In this talk I will consider varieties of certain ordered Σ-algebras with restricted completeness and continuity properties. I will give a general characterization of their free algebras in terms of submonads of the monad of Σ-coterms. Varieties of this form are called quasi-regular. For example, if E is a set of inequalities between finite Σ-terms, and if V_{ω} and V_{r} denote the varieties of all ω-continuous ordered Σ-algebras and regular ordered Σ-algebras satisfying E, respectively, then the free V_{r}-algebra R(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.