{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T23:45:03Z","timestamp":1791935103043,"version":"4.3.4"},"reference-count":26,"publisher":"Duke University Press","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Notre Dame J. Formal Logic"],"published-print":{"date-parts":[[1996,4,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1305\/ndjfl\/1040046090","type":"journal-article","created":{"date-parts":[[2003,2,25]],"date-time":"2003-02-25T16:11:33Z","timestamp":1046189493000},"page":"283-320","source":"Crossref","is-referenced-by-count":5,"title":["Algebra and Theory of Order-Deterministic Pomsets"],"prefix":"10.1215","volume":"37","author":[{"given":"Arend","family":"Rensink","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"73","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"Aalbersberg, J. J., and G. Rozenberg, \u201cTheory of traces,\u201d <i>Theoretical Computer Science<\/i>, vol. 60 (1988), pp. 1\u201382. Zbl 0652.68017 MR 89j:68042","DOI":"10.1016\/0304-3975(88)90051-5"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Aceto, L., \u201cFull abstraction for series-parallel pomsets,\u201d pp. 1\u201325 in <i>TAPSOFT '91, Volume 1<\/i>, edited by S. Abramsky and T. S. E. Maibaum, vol. 493 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1991. Zbl 0967.68517 MR 92i:68039","DOI":"10.1007\/3-540-53982-4_1"},{"key":"3","doi-asserted-by":"crossref","unstructured":"Baeten, J. C. M., and W. P. Weijland, <i>Process Algebra<\/i>, Cambridge University Press, Cambridge, 1990. Zbl 0716.68002 MR 92i:68041","DOI":"10.1017\/CBO9780511624193"},{"key":"4","doi-asserted-by":"crossref","unstructured":"Boudol, G., and I. Castellani, \u201cPermutations of transitions: An event structure semantics for CCS and SCCS,\u201d pp. 411\u2013427 in <i>Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency<\/i>, edited by J. W. de Bakker, W.-P. de Roever, and G. Rozenberg, vol. 354 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1989. MR 1035282","DOI":"10.1007\/BFb0013028"},{"key":"5","unstructured":"Corradini, A., H. Ehrig, M. L \u00f6we, U. Montanari, and F. Rossi, \u201cAn event structure semantics for safe graph grammars,\u201d pp. 423\u2013446 in <i>Programming Concepts, Methods and Calculi<\/i>, edited by E.-R. Olderog, vol. A\u201356 of <i>IFIP Transactions<\/i>, North-Holland, Amsterdam, 1994. MR 96d:68128"},{"key":"6","doi-asserted-by":"crossref","unstructured":"De Nicola, R., and A. Labella, \u201cA completeness theorem for nondeterministic Kleene algebras,\u201d pp. 536\u2013545 in <i>Mathematical Foundations of Computer Science 1994<\/i>, edited by I. Pr\u00edvara, B. Rovan, and P. Ru\\u zi\u010dka, vol. 841 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1994.","DOI":"10.1007\/3-540-58338-6_100"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Gischer, J. L., \u201cThe equational theory of pomsets,\u201d <i>Theoretical Computer Science<\/i>, vol. 61 (1988), pp. 199\u2013224. Zbl 0669.68015 MR 90b:68058","DOI":"10.1016\/0304-3975(88)90124-7"},{"key":"8","doi-asserted-by":"crossref","unstructured":"Grabowski, J., \u201cOn partial languages,\u201d <i>Fundamenta Informatic\u00e6<\/i>, vol. IV (1981), pp. 427\u2013498. Zbl 0468.68088 MR 83i:68107","DOI":"10.3233\/FI-1981-4210"},{"key":"9","unstructured":"Groote, J. F., <i>Process Algebra and Structured Operational Semantics<\/i>, Ph.D. thesis, University of Amsterdam, 1991."},{"key":"10","doi-asserted-by":"crossref","unstructured":"Heering, J., \u201cPartial evaulation and $\\omega$-completeness of algebraic specifications,\u201d <i>Theoretical Computer Science<\/i>, vol. 43 (1986), pp. 149\u2013167.","DOI":"10.1016\/0304-3975(86)90173-8"},{"key":"11","doi-asserted-by":"crossref","unstructured":"J\u00f3nsson, B., \u201cArithmetic of ordered sets,\u201d pp. 3\u201341 in <i>Ordered Sets<\/i>, edited by I. Rival, Reidel, Dordrecht, 1982. Zbl 0499.06001 MR 83i:06004","DOI":"10.1007\/978-94-009-7798-3_1"},{"key":"12","unstructured":"Kr \u00f6ger, F., <i>Temporal Logic of Programs<\/i>, vol. 8 of <i>EATCS Monographs on Theoretical Computer Science<\/i>, Springer-Verlag, Berlin, 1987. MR 89i:68084"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Lazrek, A., P. Lescanne, and J.-J. Thiel, \u201cTools for proving inductive equalities, relative completeness, and $\\omega$-completeness,\u201d <i>Information and Computation<\/i>, vol. 84 (1990), pp. 47\u201370. Zbl 0691.68026 MR 91k:68124","DOI":"10.1016\/0890-5401(90)90033-E"},{"key":"14","doi-asserted-by":"crossref","unstructured":"Mazurkiewicz, A., \u201cConcurrent program schemes and their interpretations,\u201d DAIMI Report PB\u201378, Aarhus University, 1977.","DOI":"10.7146\/dpb.v6i78.7691"},{"key":"15","doi-asserted-by":"crossref","unstructured":"Mazurkiewicz, A., \u201cBasic notions of trace theory,\u201d pp. 285\u2013363 in <i>Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency<\/i>, edited by J. W. de Bakker, W.-P. de Roever, and G. Rozenberg, vol. 354 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1989. Zbl 0683.68032 MR 1035279","DOI":"10.1007\/BFb0013025"},{"key":"16","unstructured":"Milner, R., <i>Communication and Concurrency<\/i>. Prentice-Hall, Englewood Cliffs, 1989. Zbl 0683.68008"},{"key":"17","doi-asserted-by":"crossref","unstructured":"Nielsen, M., U. Engberg, and K. G. Larsen, \u201cFully abstract models for a process language with refinement,\u201d pp. 523\u2013549 in <i>Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency<\/i>, edited by J. W. de Bakker, W.-P. de Roever, and G. Rozenberg, vol. 354 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1989. Zbl 0683.68069 MR 91b:68031","DOI":"10.1007\/BFb0013034"},{"key":"18","doi-asserted-by":"crossref","unstructured":"Nielsen, M., V. Sassone, and G. Winskel, \u201cRelationships between models for concurrency,\u201d pp. 425\u2013476 in <i>A Decade of Concurrency<\/i>, edited by J. W. de Bakker, W.-P. de Roever, and G. Rozenberg, vol. 803 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1994. MR 95h:68052","DOI":"10.1007\/3-540-58043-3_25"},{"key":"19","doi-asserted-by":"crossref","unstructured":"Pratt, V. R., \u201cModeling concurrency with partial orders,\u201d <i>International Journal of Parallel Programming<\/i>, vol. 15 (1986), pp. 33\u201371. Zbl 0622.68034 MR 88a:68031","DOI":"10.1007\/BF01379149"},{"key":"20","doi-asserted-by":"crossref","unstructured":"Rensink, A., \u201cPosets for configurations!\u201d pp. 269\u2013285 in <i>Concur '92<\/i>, edited by W. R. Cleaveland, vol. 630 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1992. MR 94g:06002","DOI":"10.1007\/BFb0084797"},{"key":"21","unstructured":"Rensink, A., \u201cDeterministic pomsets,\u201d Hildesheimer Informatik-Berichte 30\/94, Institut f\u00fcr Informatik, University of Hildesheim, 1994."},{"key":"22","doi-asserted-by":"crossref","unstructured":"Rensink, A., \u201cA complete theory of deterministic event structures,\u201d pp. 160\u2013174 in <i>Concur '95: Concurrency Theory<\/i>, edited by I. Lee and S. A. Smolka, vol. 962 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1995.","DOI":"10.1007\/3-540-60218-6_12"},{"key":"23","doi-asserted-by":"crossref","unstructured":"Rensink, A., \u201cDenotational, causal, and operational determinism in event structures,\u201d pp. 272\u2013286 in <i>Trees in Algebra and Programming\u2013-CAAP '96<\/i>, edited by H. Kirchner, vol. 1059 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1996. MR 1415912","DOI":"10.1007\/3-540-61064-2_43"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Rutten, J. J. M. M., \u201cProcesses as terms: Non well-founded models for bisimulation,\u201d <i>Mathematical Structures in Computer Science<\/i>, vol. 2 (1992), pp. 257\u2013275. Zbl 0798.68094 MR 93h:68080","DOI":"10.1017\/S096012950000147X"},{"key":"25","doi-asserted-by":"crossref","unstructured":"Winskel, G., \u201cEvent structures,\u201d pp. 325\u2013392 in <i>Petri Nets<\/i>: Applications and Relationships to Other Models of Concurrency, edited by W. Brauer, W. Reisig, and G. Rozenberg, vol. 255 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1987. Zbl 0626.68022 MR 902670","DOI":"10.1007\/3-540-17906-2_31"},{"key":"26","doi-asserted-by":"crossref","unstructured":"Winskel, G., \u201cAn introduction to event structures,\u201d pp. 364\u2013397 in <i>Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency<\/i>, edited by J. W. de Bakker, W.-P. de Roever, and G. Rozenberg, vol. 354 of <i>Lecture Notes in Computer Science<\/i>, Springer-Verlag, Berlin, 1989. Zbl 0683.68074 MR 1035280","DOI":"10.1007\/BFb0013026"}],"container-title":["Notre Dame Journal of Formal Logic"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/journalArticle\/Download?urlid=10.1305\/ndjfl\/1040046090","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T22:54:51Z","timestamp":1791932091000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/notre-dame-journal-of-formal-logic\/volume-37\/issue-2\/Algebra-and-Theory-of-Order-Deterministic-Pomsets\/10.1305\/ndjfl\/1040046090.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4,1]]},"references-count":26,"journal-issue":{"issue":"2","published-online":{"date-parts":[[1996,4,1]]}},"URL":"https:\/\/doi.org\/10.1305\/ndjfl\/1040046090","relation":{},"ISSN":["0029-4527","1939-0726"],"issn-type":[{"value":"0029-4527","type":"print"},{"value":"1939-0726","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,4,1]]}}}