TREES AND SEMANTICS

Several types of trees are proposed in the literature to model the beh aviour of nondeterministic processes. The purpose of this paper is to clarify the distinction between the various types of trees and to disc uss their use as semantic domains. Trees (in the sense of Milner's der ivation trees) and bisimulation equivalence classes of trees are consi dered in three different settings: in the category of sets, in the met ric setting and in the partial order setting. Each type of tree is cha racterized by a domain equation. Special attention is given to the use of trees as models for processes which allow for unbounded nondetermi nism as for instance Milners CCS processes. In this case one has to de al with infinitely branching trees which cause problems to give denota tional semantics that are fully abstract w.r.t. a transition system ba sed operational semantics.