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 Vr denote the varieties of all ω-continuous ordered Σ-algebras and regular ordered Σ-algebras satisfying E, respectively, then the free Vr-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.