Algebra and theory of order-deterministic pomsets (Q1815430)

A partially ordered multiset (pomset for short) is an isomorphism class of labeled preordered sets. A labeled preordered set is a triple \(\langle V,<, \ell \rangle\) where \(V\) is an arbitrary set (of vertices), \(< \subset V\times V\) is an irreflexive and transitive relation and \(\ell: V\to E\) maps into a set \(E\) of labels. Two labeled preordered sets are isomorphic if there exists a bijection between the vertex sets preserving the preorder \(<\) and the label function \(\ell\) [see \textit{J. L. Gischer}, Theor. Comput. Sci. 61, 199-224 (1988; Zbl 0669.68015)]. The order-deterministic pomsets form a class of pomsets still containing all partially ordered sets (all labels are distinct) and all words over a finite alphabet (the preorder is a linear order). This class forms a distributive lattice under pomset prefix (hence prefix closed sets of order-deterministic pomsets are prime algebraic), and it constitutes a reflexive subcategory of the category of all pomsets. For the order-deterministic pomsets an algebra can be defined using the operators concatenation and join. This theory is extended in order to capture refinement of pomsets by incorporating homomorphisms between models as objects in the algebra and homomorphism application as a new operator.