RELATIVE COMPLETENESS AND SPECIFICATION OF ABSTRACT DATA TYPES
Huimin Lin · 1988
Completeness is a fundamental concept in the theory of abstract data type specification. In this paper, the concepts of relative-completeness and the base-completeness have been proposed. The correspondence between relative-completeness and computational equivalence and that between base-completeness and behavioral equivalence have been shown. It is proved that every base-complete specification has a unique maximal consistent extension and the initial model of the maximal extension is precisely the final model of the original specification in the sense of the final algebra approach. These results reveal the relationship between the initial algebra and final algebra approaches.