A Characterization of Congruences on Algebraic and Iteration Theories with Applications

This paper presents a characterization of congruences on algebraic and iteration theories. The characterization is used to obtain (1) a subdirect decomposition of the free iteration theory, (2) an infinite class of subdirectly irreducible iteration theories, (3) a simple iteration theory not embeddable in the iteration theory [X, 0] of ‘partial functions’, and (4) a condition ensuring that a congruence on the algebraic theory of finite trees is the restriction of a congruence on the algebraic theory of all trees.