Back to Search
Start Over
Fixed-point operations on ccc's. Part I
- 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