In joint work with Elgot and Wright, the PI used the notion of iteration theories in axiomatizing the control structure of flowchart algorithms. Iteration theories also appear to provide an axiomatization for the functorial description of circular abstract data types as described most recently by Smyth, Lehmann, Plotkin, Arbib & Manes, and others. The PI is now investigating the suitability of iteration theories for the description of abstract data types. It is being determined whether the same equational axioms can be used to describe both the control structure of programs and the structure of the data types, operations and domains on which the programs operate. Also in progress is the development of algorithms for the solution of problems concerning the equivalence of data type descriptions: Given two descriptions (as fixed points of certain endofunctors), do they describe the "same thing"? The question is analogous to the question: Given two flowchart schemes, do they have the save behavior? Verification that the connection between iteration theories and data types is as the PI expects will show that these two questions are identical. The proposed research is expected to lead to an improved understanding of data types. The PI has a fine record of related research accomplishments.
