Iterative factor algebras and induced metrics (Q790606): Difference between revisions

Iterative theories were introduced by \textit{C. C. Elgot} to study the semantics of flowchart algorithms [Logic Colloquium '73, Proc., Bristol 1973, 175-230 (1975; Zbl 0327.02040)]. These theories may also be studied in the form of algebras in which every nontrival system of fixed point equations has a unique solution. It was shown by the reviewer [Universal algebra and applications, Semester 1978, Banach Center Publ. 9. 209-224 (1982; Zbl 0516.18007)] that all of the standard examples of iterative theories could be equipped with complete metrics so that the non-trivial polynomials induced contraction mappings. In particular, the free iterative theories, which may be represented as regular trees have this property. The present paper gives a necessary and sufficient condition for a congruence K on a free theory R to have the property that R/K is again an iterative theory.