Recursion and corecursion have the same equational logic

• Published in: Theoretical computer science 2003-02, Vol.294 (1), p.233-267
• Main Author: Moss, Lawrence S.
• Format: Article
• Language: English
• Subjects: Corecursion; Equational logic; Iteration theory
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/S0304-3975(01)00242-0

This paper is concerned with the equational logic of definitions whose semantics is given in terms of final coalgebra maps. The framework for our study is iteration theories (cf. e.g. Bloom and Ésik, Iteration Theories: The Equational Logic of Iterative Processes, EATCS Monographs on Theoretical Computer Science, Springer, Berlin, 1993; Theoret. Comput. Sci. 179 (1–2) (1997)), recently re-introduced as models of the FLR 0 fragment of the formal language of recursion (Hurkens et al., J. Symbolic Logic 63 (2) (1998) 45; Mos Chovakis, J. Symbolic Logic 54 (1989) 1216; in: M.L. Dalla Chiara et al. (Eds.), Logic and Scientific Methods, Kluwer, Dordrecht, 1997, p. 179). We present a new class of iteration theories derived from final coalgebras. This allows us to reason with a number of types of fixed-point equations which heretofore seemed to require metric or order-theoretic ideas. All of the work can be done using finality properties and equational reasoning. Having a semantics, we obtain the following completeness result: the equations involving fixed-point terms which are valid for final coalgebra interpretations are exactly those valid in a number of contexts pertaining to recursion. For example, they coincide with the equations valid for least-fixed-point recursion on dcpo's. We also present a new version of the proof of the well-known completeness result for iteration theories (see Ésik, Comput. Linguistics Comput. Languages 4 (1982) 95; Hurkens et al., 1998). Our work brings out a connection between coalgebraic reasoning and recursion.