ITERATION ALGEBRAS
Stephen L. Bloom, Zoltán Ésik · International Journal of Foundations of Computer Science · 1992
We assume the reader has some familiarity with theories and iteration theories. The main topic of the paper is properties of varieties of iteration algebras. After a preliminary section which contains all of the necessary definitions, we spend some time on a coproduct construction which is needed to prove a fundamental lemma: for each iteration theory T, any T-algebra is a retract of a T-iteration algebra. The proof of the lemma shows that only one property of iteration theories is used: the parameter identity. Hence, the lemma applies to any preiteration theory in which this identity is valid. It follows from this fact that the variety of all T-iteration algebras has “nice” properties only when every T-algebra is an iteration algebra. Some of the possible pathology in varieties of iteration algebras is demonstrated. It is shown that for each set Z of non-negative integers there is a variety of iteration algebras having an n-generated free algebra iff n∈Z. Also given is a theorem characterizing certain functors between varieties of iteration theories which are induced by iteration theory morphisms. We find an explicit description of all of the theory congruences on theories of partial functions. The last section is connected with the strong iteration algebras introduced in a paper by Ésik (1983).