All solutions of a system of recursion equations in infinite trees and other contraction theories (Q791310): Difference between revisions

A system of recursion equations is a finite set of equations \(f_ i=t_ i\), \(i=l,...,n\), where the expressions \(t_ i\) denote terms built from individual variables, functions constants and the function variables \(f_ i\). An interpretation of such a system assigns a meaning to each function constant and a possible meaning to each individual and function variable. Standard interpretations include an ordering on the class of possible ''solutions'' of the system and only the least (or greatest) solution is found. In this paper, contraction theories are defined and used as interpretations. Several known kinds of interpretations are shown to be contraction theories, including the collection of rooted labeled trees. No ordering is imposed on solutions in a contraction theory, but a metric is involved. All solutions of a system of recursion equations in any contraction theory are described.