Fixed Point Clones in Computer Science
by
Zoltán Ésik
Dept. of Computer Science, University of Szeged, Hungary

Previous work has resulted in a complete description of the equational laws satisfied by the fixed point operation in the computationally significant models including ordered and metric models, continuous semirings, and 2-categories. The desciption takes the form of the axioms of Iteration Theories, or Iteration Clones, cf. [1, 2, 6]. In the lecture I will review the axiomation of iteration clones by the Conway identities and the group-identities [3, 4]. This completeness result confirms a conjecture of J. H. Conway in a very general setting. I will also provide some applications of iteration clones to solve axiomatization problems in computer science (see, e.g., [5, 7]).

[1] S. L. Bloom and Z. Ésik: Iteration Theories: The Equational Logic of Iterative Processes, Springer, 1993.

[2] S. L. Bloom and Z. Ésik: The equational logic of fixed points, Theoretical Computer Science, 179(1997), 1-60.

[3] Z. Ésik: Group axioms for iteration, Information and Computation, 148(1999), 131-180.

[4] Z. Ésik: The power of the group identities for iteration, Int. J. Algebra and Computation, 10(2000), 349-373.

[5] Z. Ésik: Axiomatizing the least fixed point operation and binary supremum, in: proc. Computer Science Logic, 2000, LNCS 1862, Springer, 2000, 302-316.

[6] S. L. Bloom, Z. Ésik, A. Labella and E. Manes: Iteration 2-theories, Applied Categorical Structures, 9(2001), 173-216.

[7] Z. Ésik: The equational theory of fixed points with applications to generalized language theory, in: proc. Developments in Language Theory, Vienna, July 2001, 25-44.

Date received: July 31, 2001