The Apt-Plotkin powerdomain is a powerdomain construction on flat cpo's. It is used to model countable nondeterminism.
Let be a set that is at most countable.
The Apt-Plotkin powerdomain on a flat cpo is the set of nonempty subsets of :
It is ordered by the Egli-Milner order. Equivalently:
The least element is .
The above construction is very closely related to the Plotkin powerdomain.
In fact, the only difference is that we take all nonempty , whereas the Plotkin powerdomain takes only those which are either finite, or contain .
Thus, the Plotkin powerdomain can't model the possible output set , but only the possible output set .
Apt, K. R., and G. D. Plotkin. 1986. ‘Countable Nondeterminism and Random Assignment’. Journal of the ACM 33 (4): 724–67. https://doi.org/10.1145/6490.6494.
@article{apt_1986,
title = {Countable nondeterminism and random assignment},
volume = {33},
doi = {10.1145/6490.6494},
number = {4},
journal = {Journal of the ACM},
author = {Apt, K. R. and Plotkin, G. D.},
year = {1986},
pages = {724--767}
}