Regular trees and the free iterative theory

摘要

This paper establishes the relationship between regular trees, equationally defined trees, and Elgot's iterative algebraic theories; in particular, it provides a regular tree characterization of the free iterative theory and an equational tree characterization of the free iterative theory. These tree characterizations have implications for decision problems involving flowchart schemes interpreted in iterative theories and they also help to explicate the connections between order theoretic and non-order theoretic fixed point models for iteration.