Comparing approaches to free dcpo-algebra constructions

摘要

Algebraic structures play an important role for the semantics of programming languages. One application is the use of free algebra constructions for modelling computational effects in categorical frameworks for denotational semantics, as proposed by Plotkin and Power. It is well-known that, for abstract reasons, free algebra constructions are available in the category of dcpos and Scott continuous maps. However, only very recently, this construction has been investigated in concrete settings to obtain explicit characterisations of free dcpo algebras. Thereby three approaches have been developed: one order-theoretic approach by Jung, Moshier and Vickers, and two topological approaches, one by Keimel and Lawson the other by Battenfeld. In this paper we compare these approaches. In particular, we show that the order-theoretic approach can be translated into the topological setting where it is generalised by Keimel and Lawson's approach. Furthermore, we explain the problems in comparing the order-theoretic approach with Battenfeld's approach. Finally, we show that the two topological approaches differ on a more general scale.