Both iteration and recursion are operations yielding fixed points. They have the same equational properties in standard models. See the following articles: S. Bloom and Z. Esik,``Fixed point operations in ccc's'', Theoretical Computer Science, 155:1996, 1--38, S. Bloom and Z. Esik,``The equational logic of fixed points'' , Theoretical Computer Science, 179(1997), 1--60, and Z. Esik and A. Labella: Equational properties of iteration in algebraically complete categories. Mathematical foundations of computer science (Cracow, 1996). Theoret. Comput. Sci. 195 (1998), no. 1, 61--89. and the book: Iteration Theories: The Equational Logic of Iterative Processes, EATCS Monograph Series on Theoretical Computer Science, Springer-Verlag, 1993 ISBN 0-387-56378-4, by Bloom and Esik.
On fixed-point operators and their axiomatizations including the iteration theories of Bloom and Esik, one of the latest (and concise) accounts is found in Alex Simpson and Gordon Plotkin: Complete Axioms for Categorical Fixed-point Operators. Fifteenth Annual IEEE Symposium on Logic in Computer Science, pp.30-41, 2000 available from Simpson's page http://www.dcs.ed.ac.uk/home/als/Research/ . - Masahito Hasegawa
participants (2)
-
HASEGAWA Masahito -
Stephen Bloom