Order and metric in the stream semantics of elemental concurrency (Q1085602)

Two denotational semantics for a language with simple concurrency are presented. The language has parallel composition in the form of the shuffle operation, in addition to the usual sequential concepts including full recursion. Two linear time models, both involving sets of finite and infinite streams, are given. The first model is order-theoretic and based on the Smyth order. The second model employs complete metric spaces. Various technical results are obtained relating the order-theoretic and metric notions. The paper culminates in the proof that the two semantics for the language considered coincide. The paper completes previous investigations of the same language, establishing the equivalence of altogether four semantic models for it.