Denotational semantics for programming languages, balanced quasi-metrics and fixed points

Abstract

A new mathematical model is introduced for the study of the domain of words. We do it by means of the introduction of a suitable balanced quasi-metric on the set of all words over an alphabet. It will be shown that this construction has better quasi-metric and topological properties than several classical constructions. We also prove a fixed point theorem which allows us to develop an application for the study of probabilistic divide and conquer algorithms.

Keywords:

• Algorithm
• Baire metric
• Balanced quasi-metric
• Domain of words
• Recurrence equation

Acknowledgements

The authors thank the referees for their valuable suggestions. The authors are also grateful for the support of the Spanish Ministry of Education and Science, and FEDER, grant MTM2006-14925-C02-01.