A quasi-metric computational model from modular functions on monoids

Abstract

Domain Theory has a wide range of applications to model computational processes where the information about the final stage is increased successively in each passage of the process. Two distinguished examples of domains are the so-called domain of words and the interval domain. Both can be structured as monoids with a property of left cancellativity on the non-left-absorbing elements. Motivated by these two models we present a general method for generating a weightable quasi-metric from ϵ -modular functions on certain monoids. Such a quasi-metric structure captures, in a unified approach, the main properties of the two mentioned domains.

Keywords:

• computational model
• weightable quasi-metric
• monoid
• ϵ-modular function
• domain of words
• interval domain
• the Scott topology

2000 AMS Subject Classifications :

• 68Q01
• 68Q05
• 54E35
• 06A06
• 06A11
• 06B35
• 06F05

Acknowledgements

The authors are grateful to the referees for their constructive and useful comments that have allowed us to improve the article. The authors thank the support of the Spanish Ministry of Education and Science and FEDER, under grant MTM2006-14925-C02-01.