Approximating traces

In order to give a semantics to concurrent processes we need a model having some good mathematical properties. To this end we generalize (infinite) Mazurkiewicz traces by adding some alphabetical information concerning the possible continuations of a process. This allows to define an approximation order compatible with the composition. We obtain a prime algebraic and coherently complete domain where the compact elements are exactly the finite approximations of processes. The composition is shown to be monotone and -continuous. We define a suitable metric which induces the Lawson topology and which yields a compact metric space being therefore complete. The finite approximations of processes form a dense and open subset and the composition is (uniformly) continuous. A preliminary version of this work appeared in [7]. Received: 2 July 1996 / 27 October 1997