# Algebra and Theory of Order-Deterministic Pomsets

5 Citations (Scopus)

### Abstract

This paper is about partially ordered multisets (pomsets for short). We investigate a particular class of pomsets that we call order-deterministic, properly including all partially ordered sets, which satisfies a number of interesting properties: among other things, it forms a distributive lattice under pomset prefix (hence prefix closed sets of order-deterministic pomsets are prime algebraic), and it constitutes a reflective subcategory of the category of all pomsets. For the order-deterministic pomsets we develop an algebra with a sound and ($\omega$-) complete equational theory. The operators in the algebra are concatenation and join, the latter being a variation on the more usual disjoint union of pomsets. This theory is then 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.
Original language Undefined 10.1305/ndjfl/1040046090 283-320 38 Notre Dame Journal of Formal Logic 37 2 https://doi.org/10.1305/ndjfl/1040046090 Published - 1996

• EWI-8293
• IR-66660

### Cite this

@article{9a4ce7bd98f747e7a3a82914de5928ca,
title = "Algebra and Theory of Order-Deterministic Pomsets",
abstract = "This paper is about partially ordered multisets (pomsets for short). We investigate a particular class of pomsets that we call order-deterministic, properly including all partially ordered sets, which satisfies a number of interesting properties: among other things, it forms a distributive lattice under pomset prefix (hence prefix closed sets of order-deterministic pomsets are prime algebraic), and it constitutes a reflective subcategory of the category of all pomsets. For the order-deterministic pomsets we develop an algebra with a sound and ($\omega$-) complete equational theory. The operators in the algebra are concatenation and join, the latter being a variation on the more usual disjoint union of pomsets. This theory is then 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.",
keywords = "EWI-8293, IR-66660",
author = "Arend Rensink",
year = "1996",
doi = "10.1305/ndjfl/1040046090",
language = "Undefined",
volume = "37",
pages = "283--320",
journal = "Notre Dame Journal of Formal Logic",
issn = "0029-4527",
publisher = "Duke University Press",
number = "2",

}

In: Notre Dame Journal of Formal Logic, Vol. 37, No. 2, 10.1305/ndjfl/1040046090, 1996, p. 283-320.

TY - JOUR

T1 - Algebra and Theory of Order-Deterministic Pomsets

AU - Rensink, Arend

PY - 1996

Y1 - 1996

N2 - This paper is about partially ordered multisets (pomsets for short). We investigate a particular class of pomsets that we call order-deterministic, properly including all partially ordered sets, which satisfies a number of interesting properties: among other things, it forms a distributive lattice under pomset prefix (hence prefix closed sets of order-deterministic pomsets are prime algebraic), and it constitutes a reflective subcategory of the category of all pomsets. For the order-deterministic pomsets we develop an algebra with a sound and ($\omega$-) complete equational theory. The operators in the algebra are concatenation and join, the latter being a variation on the more usual disjoint union of pomsets. This theory is then 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.

AB - This paper is about partially ordered multisets (pomsets for short). We investigate a particular class of pomsets that we call order-deterministic, properly including all partially ordered sets, which satisfies a number of interesting properties: among other things, it forms a distributive lattice under pomset prefix (hence prefix closed sets of order-deterministic pomsets are prime algebraic), and it constitutes a reflective subcategory of the category of all pomsets. For the order-deterministic pomsets we develop an algebra with a sound and ($\omega$-) complete equational theory. The operators in the algebra are concatenation and join, the latter being a variation on the more usual disjoint union of pomsets. This theory is then 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.

KW - EWI-8293

KW - IR-66660

U2 - 10.1305/ndjfl/1040046090

DO - 10.1305/ndjfl/1040046090

M3 - Article

VL - 37

SP - 283

EP - 320

JO - Notre Dame Journal of Formal Logic

JF - Notre Dame Journal of Formal Logic

SN - 0029-4527

IS - 2

M1 - 10.1305/ndjfl/1040046090

ER -