Qualitative versus quantitative fixed point techniques in computer science

Abstract

In 1970, a qualitative xed point technique useful to model the recursive specications in  denotational semantics was developed by means of the celebrated Kleene's xed point theorem. Later on, in 1994 and 1995, quantitative counterparts of the aforesaid technique, but now based on generalized versions of Banach fixed point theorem, were obtained in such a way that the spirit of Kleene's technique was preserved. These new techniques are able to provide a measure of the informa- tion content degree and this fact has constituted an advantage with respect to the qualitative techniques. The main purpose of this paper is to discern the relationship between the afore mentioned qualitative and quantitative fixed point techniques. In particular, we clarify what is the additional real contribution of the quantitative fixed point techniques with respect to the qualitative ones.

Key words: Partial order, quasi-metric, partial metric, complete, fixed point, denotational semantics, algorithmic complexity, fixed point.