ON THE CONCATENATION OF INFINITE TRACES

There is a straightforward generalization of traces to infinite traces as dependence graphs where every vertex has finitely many predecessor s, or what is the same, as a backward closed and directed set of trace s with respect to prefix ordering. However, this direct approach has a drawback since it does not allow one to describe some basic phenomena which are related to concatenation. We solve this problem by adding t o an infinite trace a second component. This second component is a fin ite alphabetic information which is called the alphabet at infinity. W e obtain a compact and complete ultra-metric space where the concatena tion is uniformly continuous and where the set of finite traces is an open, discrete, and dense subset. Our objects arise in a natural way f rom the consideration of dependence graphs where the induced partial o rder is well-founded. Such a graph splits into a so-called real part a nd a transfinite part. From the transfinite part only its alphabet is of importance. Our approach is a nontrivial generalization of the well -known construction for words and yields a convenient semantics for in finite concurrent processes.