Algebra and theory of order-deterministic pomsets
type: Item
instance of: scholarly article
title: Algebra and theory of order-deterministic pomsets
zbMATH Open document ID: 0865.06004
author: Arend Rensink
published in: Notre Dame Journal of Formal Logic
publication date: 1996-12-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 06A99
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68Q55
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 944261
zbMATH Keywords: category of pomsets
zbMATH Keywords: partially ordered multiset
zbMATH Keywords: labeled preordered set
zbMATH Keywords: order-deterministic pomsets
zbMATH Keywords: partially ordered sets
zbMATH Keywords: words over a finite alphabet
zbMATH Keywords: reflexive subcategory
zbMATH Keywords: homomorphisms
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1305/ndjfl/1040046090
OpenAlex ID: W1987134164
cites work: Theory of traces
cites work: Q2736337
cites work: Process Algebra
cites work: Q4733397
cites work: A completeness theorem for Kleene algebras and the algebra of regular events
cites work: The equational theory of pomsets
cites work: Q3922196
cites work: Partial evaluation and \(\omega\)-completeness of algebraic specifications
cites work: Q3964624
cites work: Q3749040
cites work: Tools for proving inductive equalities, relative completeness, and \(\omega\)-completeness
cites work: Q4733400
cites work: Q3992568
cites work: Q4733430
cites work: Modeling concurrency with partial orders
cites work: Processes as terms: non-well-founded models for bisimulation
cites work: Q3030239
cites work: Q4733435
DOI: 10.1305/NDJFL/1040046090
Recommended article: The equational theory of pomsets
Recommended article: Q3811722
Recommended article: Parsing Partially Ordered Multisets
Recommended article: On the homomorphism order of labeled posets
Recommended article: Q4484501
Recommended article: Labeled posets are universal
Recommended article: An algebra for pomsets.
Recommended article: Hyper-lattice algebraic model for data warehousing
Recommended article: Q3814772
Recommended article: Q3126181
description: scientific article; zbMATH DE number 944261