Algebra and Theory of Order-Deterministic Pomsets

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)
    49 Downloads (Pure)

    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 languageUndefined
    Article number10.1305/ndjfl/1040046090
    Pages (from-to)283-320
    Number of pages38
    JournalNotre Dame Journal of Formal Logic
    Volume37
    Issue number2
    DOIs
    Publication statusPublished - 1996

    Keywords

    • 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",

    }

    Algebra and Theory of Order-Deterministic Pomsets. / Rensink, Arend.

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

    Research output: Contribution to journalArticleAcademicpeer-review

    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 -