{"entities":{"Q1104097":{"pageid":1114849,"ns":120,"title":"Item:Q1104097","lastrevid":49176838,"modified":"2026-01-06T17:22:52Z","type":"item","id":"Q1104097","labels":{"en":{"language":"en","value":"Simulations among concurrent-write PRAMs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4055054"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$E4DD575E-A792-424F-BC7A-13A40A927F7E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fd55ad5a7ccfb9e2f12b3da389a962f5142b082d","datavalue":{"value":{"text":"Simulations among concurrent-write PRAMs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104097$B711E112-0925-46A3-B2E5-C3458FDE1A82","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"80d43010aa234614da602380fdd587c6c91aa980","datavalue":{"value":"0646.68068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104097$80880FDB-300D-4DEE-B075-6D400E633E4E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"17c0e189a897f990b760cf36b8be00671a9b2d97","datavalue":{"value":"10.1007/BF01762109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104097$3A1ACC77-18E8-470D-9F56-A84246DFC5DC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5832eb8522cc074d0d11f3d15788f1238c174fec","datavalue":{"value":{"entity-type":"item","numeric-id":760214,"id":"Q760214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$AA1A2FC7-FDB8-47C1-B02C-07A1BDE6A40A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1078dadceba4c60c801967c8568490c45d0068f0","datavalue":{"value":{"entity-type":"item","numeric-id":919821,"id":"Q919821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$42021DB6-EA4C-4692-B8B6-8E35D944149D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a028a6348dcfc7b43c17e257a75b67ed9a2b7db","datavalue":{"value":{"entity-type":"item","numeric-id":178716,"id":"Q178716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$C0571F11-23E8-4FEE-BA52-81DB435CFF59","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$799A9B03-6469-4C3E-969A-A20B5010CDE5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1104097$A83FC991-751D-4F06-AF58-A841BE6F03B4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"201189109554e256c8b58b11542265f1d13b8661","datavalue":{"value":"The paper is concerned with the relative power of the two most popular concurrent-write models of parallel computation, the PRIORITY PRAM [\\textit{L. M. Goldschlager}, J. Assoc. Comput. Mach. 29, 1073-1086 (1982; Zbl 0489.68042)], and the COMMON PRAM [\\textit{L. Ku\u010dera}, Inf. Process. Lett. 14, 93-96 (1982; Zbl 0498.68029)]. Improving the trivial and seemingly optimal O(log n) simulation, we show that one step of a PRIORITY machine can be simulated by O(log n/(log log n)) steps of a COMMON machine with the same number of processors (8C25    A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the first n/log n processor, O(log n)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$EF8D0B85-5778-4FD7-8754-82C02074309D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104097$6E75473E-7B41-4450-B933-4792F0AD712B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104097$5D802E91-4BEE-4604-AEBD-920684CCBB71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104097$78A17B5D-D433-45F8-9188-9358F5168FBC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"03ac97d9b8b0885de9e8860fdd4979aab2bc4089","datavalue":{"value":"4055054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104097$17746BF5-A630-495A-A85B-DB87719F1838","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36180add95a5b34b7c978882e76c8517566db5ca","datavalue":{"value":"parallel random access machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$44F71F0F-2FDB-4F32-9246-BBBE1AC59DDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2c2a49199cd2857d883040e6175603f614d275f","datavalue":{"value":"write-conflict resolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$667B9364-46B6-45C6-80B6-A10AEDBFD6DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b691edf5c6e204973ef6821e4c1a197b418c6c2","datavalue":{"value":"lower bounds. centroid decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$E945F374-60EB-43AE-A388-112AE2971119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ce5ac37630daaa2988a945d5c08c28efa2c1f27","datavalue":{"value":"list ranking","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$439B0B74-DE16-4D59-891D-E2D69C83149E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6acea2b3bcb312388acd7d58517b0ad6a3e1251","datavalue":{"value":"concurrent-write models of parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$9A5239D4-40AD-48BB-A0E6-8F41EE35E236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28b7e88254f863aa92be9b077e190409db9ce72c","datavalue":{"value":"PRIORITY PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$2C2DBE89-FD8C-41EB-8551-C15A15A8DB88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8ea372025245838aebc8b3780eb4aadf33acf41","datavalue":{"value":"COMMON PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$68B20E09-E8F9-4746-BA78-C3657388AC58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$9A03B279-90F4-4F02-8A19-D14E09CF1EF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e86430f784ceeed0878ab2c6f53cac4dc064431","datavalue":{"value":"EREW PRAM algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$7808DB88-E376-4B96-A803-EF6A69A30632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f9b7fe7cc9feefb5f4c865ec4db4ca5e766113fc","datavalue":{"value":"expression tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104097$9EB47500-D2D9-48DA-8CA3-1F87EB3CE5F2","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$FEEC16BD-2DD7-43C6-BA86-C3D8FA716D8E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"30cca9e21c8c7c104635df4f45250c64914389b4","datavalue":{"value":{"entity-type":"item","numeric-id":3798244,"id":"Q3798244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$CDD51A37-E35B-4341-A82B-CD081C69C352","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07adfa7411d8716c42e7a81a35a8dc21f533009d","datavalue":{"value":{"entity-type":"item","numeric-id":3951543,"id":"Q3951543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$5FCD8406-494C-45D8-B448-CEF728E0714A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"769cf6c7ee115ce4ebdbc44071512764e92350d4","datavalue":{"value":{"entity-type":"item","numeric-id":1171382,"id":"Q1171382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$98698742-6DB5-4675-8909-021D23C7109A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50c5a833f949924e5aa5ac924fedc52e112a1e38","datavalue":{"value":{"entity-type":"item","numeric-id":3776649,"id":"Q3776649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$CAD45988-4179-4D90-AB5F-8CA2E5508F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"701516c01a9c43d8b1d16894c96ff96af0778229","datavalue":{"value":{"entity-type":"item","numeric-id":3802607,"id":"Q3802607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$143E3026-C7FE-4C6E-9AC8-BB9D4879ECD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06b820d7730c4483ffdeaf5f1bb9567aad23b088","datavalue":{"value":{"entity-type":"item","numeric-id":3906428,"id":"Q3906428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$D27FAF58-13D8-42EC-9A66-BA8039750FCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43a25f91f1879c40c0b3374c776578fa61b362f0","datavalue":{"value":{"entity-type":"item","numeric-id":3691060,"id":"Q3691060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104097$D0FD0AFD-D309-41EB-9075-B7C319E78457","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d93bda77a976257f6983e5be753a48418fc68f51","datavalue":{"value":"https://doi.org/10.1007/bf01762109","type":"string"},"datatype":"url"},"type":"statement","id":"Q1104097$B836D4E4-C734-4F3C-9C61-B38E6A304709","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1220aaf0baee494e8664a8f50f42621e31013f44","datavalue":{"value":"W1966913545","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104097$BC5B7495-229E-49BC-AD34-58473A50C773","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de1b82faf18c5ee040573e74577d77df7d57b19f","datavalue":{"value":{"entity-type":"item","numeric-id":1185246,"id":"Q1185246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15f1334492415fd2127e30f3994c79425989e6e9","datavalue":{"value":{"amount":"+0.8424407243728638","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104097$7CCD23A5-4EBC-466E-9075-E9D7914EB054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"881eabb649ac1ccd6e1e15a20ff15969b0951755","datavalue":{"value":{"entity-type":"item","numeric-id":1881272,"id":"Q1881272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23463c3f4f42025d932289a0b8f55e1da2ba68bb","datavalue":{"value":{"amount":"+0.8393527865409851","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104097$0FDA2806-3E1C-41B4-BCC4-1187A532BB65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fbe4720354f15e8c8e74d88f24691419257c8ab","datavalue":{"value":{"entity-type":"item","numeric-id":3974857,"id":"Q3974857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d3655496e3d0ee6487383e1a1085b2a648ce842","datavalue":{"value":{"amount":"+0.8155019879341125","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104097$E5D3D95B-63F8-40D5-8873-73405DAE8B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f697ed45b271efd5e3cdd1b9c19dba23b17fe134","datavalue":{"value":{"entity-type":"item","numeric-id":1104105,"id":"Q1104105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3c372d1673408bb980fcc4d4c7d5b25119f95fb","datavalue":{"value":{"amount":"+0.8138511776924133","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104097$EB2DB408-CCA5-4814-9844-26D173376EC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e5f38a68459f840480cac5e5af4fef40dafe552","datavalue":{"value":{"entity-type":"item","numeric-id":582089,"id":"Q582089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15f43d0161409ce150aab95c513056d1c61cd45d","datavalue":{"value":{"amount":"+0.8073557019233704","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104097$012CAB44-5A76-4035-AC26-F387CC84B639","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1104097","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1104097"}}}}}