Back to Search Start Over

Fixed-point operations on ccc's. Part I

Authors :
Zoltán Ésik
Stephen L. Bloom
Source :
Theoretical Computer Science. (1):1-38
Publisher :
Published by Elsevier B.V.

Abstract

Most studies of fixed points involve their existence or construction. Our interest is in their equational properties. We study certain equational properties of the fixed-point operation in computationally interesting cartesian closed categories. We prove that in most of the poset categories that have been used in semantics, the least fixed-point operation satisfies four identities we call the Conway identities. We show that if %plane1D;49E; 0 is a sub-ccc of any ccc %plane1D;49E; with a fixed-point operation satisfying these identities, then there is a simple normal form for the morphisms in the least sub-ccc of %plane1D;49E; containing %plane1D;49E; 0 closed under the fixed-point operation. In addition, the standard functional completeness theorem is extended to Conway ccc's.

Details

Language :
English
ISSN :
03043975
Issue :
1
Database :
OpenAIRE
Journal :
Theoretical Computer Science
Accession number :
edsair.doi.dedup.....57af2f3bb5254bef8ec4584c91c19bbb
Full Text :
https://doi.org/10.1016/0304-3975(95)00010-0