Deterministic Pomsets

    Research output: Book/ReportReportOther research output

    55 Downloads (Pure)


    This paper is about partially ordered multisets (pomsets for short). We investigate a particular class of pomsets that we call 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 deterministic pomsets are prime algebraic), and it constitutes a reflective subcategory of the category of all pomsets. For the deterministic pomsets we develop an algebra with a sound and (ω-)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 with the special property that it yields the least upper bound with respect to pomset prefix. This theory is then extended in several ways. We capture refinement of pomsets by incorporating homomorphisms between models as objects in the algebra and homomorphism application as a new operator. This in turn allows to formulate distributed termination and sequential composition of pomsets, where the latter is different from concatenation in that it is right-distributive over union. To contrast this we also formulate a notion of global termination. Each variation is captured equationally by a sound and ω-complete theory.
    Original languageUndefined
    Place of PublicationHildesheim, Germany
    PublisherUniversity of Hildesheim
    Number of pages42
    Publication statusPublished - Nov 1994

    Publication series

    NameHildesheimer Informatik-Bericht
    PublisherInstitut für Informatik, University of Hildesheim
    ISSN (Print)0941-3014


    • EWI-8253
    • IR-66642

    Cite this