Domain semantics of possibility computations

The purpose of this paper is to introduce a kind of computational model, called possibility computation, to deal with non-determinism. Both its denotational and logical semantics in the framework of domain theory are established and their equivalence is verified. In this approach, the denotational semantics will be set up by assigning to programs possibility state transformers, i.e., Scott-continuous functions from the domain of input states to the possibility powerdomain of the codomain of final states. This possibility powerdomain of a dcpo will consist of all possibility valuations, ordered pointwise, of this dcpo. The logical semantics will be given by fuzzy predicate transformers introduced by the first author and Jung following Dijkstra’s predicate transformers. Two semantics equivalence will be verified in terms of the integration of fuzzy predicates with respect to possibility valuations. The categorical monad of the possibility powerdomain will be investigated.