Metric Iteration Theories

Article type: Research Article

Authors: Troeger, Douglas R.

Affiliations: Stevens Institute of Technology, Hoboken

Abstract: It is known that it is possible to impose a metric on the free iteration theory Γtr of Γ-trees such that the iterate f† of any tree f : n → p + n is a limit of of ‘finite approximations’ of f. Since this notion of limiting computation corresponds to our intuitive notion of iteration, it is natural to ask which other theories in the variety generated by Γtr admit such a metric. An algebraic characterization of these theories is presented In this paper.

Keywords: iterative theories, fixed points, metric interpretations

DOI: 10.3233/FI-1982-5205

Journal: Fundamenta Informaticae, vol. 5, no. 2, pp. 187-216, 1982