Solutions of the Iteration Equation and Extensions of the Scalar Iteration Operation
Stephen L. Bloom, Calvin C. Elgot, Jesse B. Wright · SIAM Journal on Computing · 1980
We study the solutions to a (vector) equation somewhat analogous to the traditional equations of linear algebra. Whereas, in introductory linear algebra the domain of discourse is the field of real numbers (or an arbitrary field) our domain of discourse is the algebraic theory of (multi-rooted, leaf-labeled) trees (or, more generally, any iterative theory). As in linear algebra, we obtain a necessary and sufficient condition for our equations to have unique solutions and we can describe “parametrically” the totality of solutions. However, whereas in linear algebra, there is no way of giving $1 \div 0$ meaning in such a way that all the “old laws” hold, we can give meaning to the “iteration operation” (the analogue of division into 1) in such a way that all the “old laws” still hold. Indeed, we can describe “parametrically” all such ways of extending the (partially defined) scalar iteration operation to all trees (more generally, morphisms).