A characterization of Plotkin's order in powerdomains, and some of its properties

Abstract

In 1976, Plotkin introduced powerdomains adapting to them, in some sense, Egli- Milner's order. Lately, Smyth (1978) presented the same results starting from generating trees, and adding a new order that he denoted by 0. He also gave a characterization of the first order M, without making any further use of it. This charactererization turned out to be wrong, and starting from this fact (which shall be proved in the sequel) I have developed a new one (which is the same as the one that has been exposed by Plotkin, although it has been got from another approach), obtaining in some cases a canonical representative of the equivalence classes induced by the preorder M. As it would be expected, this representative is maximal with respect to the ⊆-order. Nevertheless, in other cases such a canonical ‘representative’ would not be finitely generable, and some consequences of it will be exposed.