{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:37:48Z","timestamp":1787387868710,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1976,9]]},"abstract":"<jats:p>We develop a powerdomain construction, $\\mathcal{P}[ \\cdot ]$, which is analogous to the powerset construction and also fits in with the usual sum, product and exponentiation constructions on domains. The desire for such a construction arises when considering programming languages with nondeterministic features or parallel features treated in a nondeterministic way. We hope to achieve a natural, fully abstract semantics in which such equivalences as $(p\\textit{ par } p) = (q\\textit{ par }p)$ hold. The domain ($D \\to $ Truthvalues) is not the right one, and instead we take the (finitely) generable subsets of D. When D is discrete they are ordered in an elementwise fashion. In the general case they are given the coarsest ordering consistent, in an appropriate sense, with the ordering given in the discrete case. We then find a restricted class of algebraic inductive partial orders which is closed under $\\mathcal{P}[ \\cdot ]$ as well as the sum, product and exponentiation constructions. This class permits the solution of recursive domain equations, and we give some illustrative semantics using $\\mathcal{P}[ \\cdot ]$.<\/jats:p>\n                  <jats:p>It remains to be seen if our powerdomain construction does give rise to fully abstract semantics, although such natural equivalences as the above do hold. The major deficiency is the lack of a convincing treatment of the fair parallel construct.<\/jats:p>","DOI":"10.1137\/0205035","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T05:57:56Z","timestamp":1109224676000},"page":"452-487","source":"Crossref","is-referenced-by-count":474,"title":["A Powerdomain Construction"],"prefix":"10.1137","volume":"5","author":[{"given":"G. D.","family":"Plotkin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","volume-title":"Recursive procedures","author":"de Bakker J. W.","year":"1971"},{"key":"R2","first-page":"167","volume-title":"Automata, languages and programming (Proc. Sympos., Rocquencourt, 1972)","author":"de Bakker J. W.","year":"1973"},{"key":"R3","volume-title":"What can lattices do for you? Trends in Lattice Theory","author":"Birkhoff G.","year":"1970"},{"key":"R4","volume-title":"Elements of mathematics. General topology. Part 1","author":"Bourbaki Nicolas","year":"1966"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"J. M. Cadlou, J. J. L\u00e9vy,  Mechanizable proofs about parallel processes,  14th Annual IEEE Symposium on Switching and Automata Theory (Univ. Iowa, Iowa City, Iowa, 1973), IEEE Comput. Soc., Northridge, Calif.,  1973,  34\u201348 MR0438764 (55:11670)","DOI":"10.1109\/SWAT.1973.14"},{"key":"R6","volume-title":"Universal algebra","author":"Cohn P. M.","year":"1965"},{"key":"R7","first-page":"225","volume-title":"Automata, languages and programming (Proc. Sympos., Rocquencourt, 1972)","author":"Hitchcock Peter","year":"1973"},{"key":"R8","first-page":"471","volume-title":"Information processing 74 (Proc. IFIP Congress, Stockholm, 1974)","author":"Kahn Gilles","year":"1974"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(70)90002-0"},{"key":"R10","unstructured":"R. Milner,  An approach to the semantics of parallel programs,  Proceedings of the Convegno di Informatics Teorica, Institute di Elaborazione Belle Informazione, Pisa,  1973"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71948-7"},{"key":"R12","volume-title":"The mathematical semantics of Algol 60","author":"Mosses P.","year":"1974"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90044-5"},{"key":"R14","volume-title":"Notes on a lattice-theoretic approach to the theory of computation","author":"Reynolds J. C.","year":"1972"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-06841-4_57"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0073967"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0079432"},{"key":"R18","unstructured":"D. Scott, C. Strachey,  Towards a mathematical semantics for computer languages,  Proceedings of the Symposium in Computers and Automata, Vol. 21, Microwave Research Institute Symposia Series,  1971"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0205036"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-07142-3_85"},{"key":"R21","volume-title":"Fixed-point constructions in order-enriched categories","author":"Wand M.","year":"1975"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0205035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:01Z","timestamp":1787337241000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0205035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1976,9]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1976,9]]}},"alternative-id":["10.1137\/0205035"],"URL":"https:\/\/doi.org\/10.1137\/0205035","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1976,9]]}}}