{"entities":{"Q1098633":{"pageid":1109385,"ns":120,"title":"Item:Q1098633","lastrevid":49142188,"modified":"2026-01-06T16:06:43Z","type":"item","id":"Q1098633","labels":{"en":{"language":"en","value":"Separation and lower bounds for ROM and nondeterministic models of parallel computation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4039292"}},"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":"Q1098633$C9C33E3B-9072-4DE8-B4A3-381D6AD44537","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fba7fe9e98ac9936703091182f98bb851c529140","datavalue":{"value":{"text":"Separation and lower bounds for ROM and nondeterministic models of parallel computation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098633$F09483AC-FA7B-4936-8B52-4FD53746B883","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1fd019391f268568c3f07a0a818f3be6c27e9c7a","datavalue":{"value":"0637.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098633$BC5FBDE1-0904-4EC5-BDC7-24F2C56CE91C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c5729ef95f95d5002ac7025282ab44024f3c4422","datavalue":{"value":"10.1016/0890-5401(87)90017-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098633$BDFC856F-82F0-44EA-9BDC-000C3AE013F7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"95e666d41882411f9ee5a3d11cf0ad33cabba8b2","datavalue":{"value":{"entity-type":"item","numeric-id":672057,"id":"Q672057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098633$C2C8185A-F8E1-4E2A-9053-CA94DE5FDF66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9859a4dcc00fc8d1566f43eb1abbd6d402c90633","datavalue":{"value":{"entity-type":"item","numeric-id":751803,"id":"Q751803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098633$F1E6B9CE-AF79-4284-BC7F-CFF810BA3668","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098633$8AA8BFAF-2B27-4000-976E-DCFB70A547F5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1098633$DA8EC386-6255-4696-A2BA-BA8ACEE763D9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6bf1fbe90e8265c560b56a5a8d5d3efc5ed8a831","datavalue":{"value":"The paper contains a collection of separation results between variants of the CRCW-PRAM model of parallel computation having a shared memory of size m where m is relatively small. The variants differ in the way they handle write conflicts: In a COMMON(m) all processors attempting to write into the same location write the same value, in an ARBITRARY(m) an arbitrary processor succeeds, and in a PRIORITY(m) the one with minimum index. Furthermore, the input \\((x_ 1,...,x_ n)\\) may be in a shared read-only memory (variant with ROM) or it may be distributed such that processor P(i) knows only \\(x_ i\\) (variant without ROM).    It is shown that with respect to the computation of relatively simple functions there are tight \\(\\Omega\\) (log n/log(m\\(+1))\\) gaps between a COMMON(m) with ROM and n a processors \\((a<2)\\) and an ARBITRARY(1) (with or without ROM) and between an ARBITRARY(m) with ROM and a PRIORITY(1) (with or without ROM). In addition to these separation results a lower bound of \\(\\Omega\\) (log log n) and an upper bound of \\(O(n^{1/3})\\) is proved for the nondeterministic computation of the parity function on a PRIORITY(1) with ROM and a tight lower bound of \\(\\Omega\\) (\\(\\sqrt{n})\\) for the nondeterministic computation on a PRIORITY(1) without ROM. The paper is worth reading mainly because of the quite sophisticated lower bound proofs (which might have been improved by the choice of a more suggestive notation).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098633$D8491113-09D1-4256-8FD5-2AFEC61613E6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"80e51cd7d7fb06dcf3d39ea7090bd669bdc6f79e","datavalue":{"value":{"entity-type":"item","numeric-id":789161,"id":"Q789161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098633$2581A306-49CB-40EB-AC42-154FF50420EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098633$146F37B5-930A-44F5-AD9D-42BDE7A001F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098633$7C6F7520-041B-4C59-8763-84EA37B6EA49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098633$F58C35C7-EECF-4BBA-8248-06D9ED1A44B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"321e618034f0c20bd62e1696302236314231d277","datavalue":{"value":"4039292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098633$235BE2AF-C793-431A-902E-A84E31852C75","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b22b8f5949bfeb39f3cc5968462ee2578e2cdb91","datavalue":{"value":"information sharing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098633$B58A2D51-AC1F-4E57-9F0E-3160067EDED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f90139540a7d903d3d1c4be37d3cee7145f7063","datavalue":{"value":"PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098633$CE9FD91E-DAFC-424C-99B3-4A3E032C113E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098633$6EDC2104-82B1-483A-BF17-E305285FEA15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0f6a9c56246517914e9f9c699b4175e9b980538","datavalue":{"value":"write conflicts","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098633$CE55272A-5E3C-40D8-A875-78E919E0042F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9199d2a34e605cbe9885e79eb427d00c0efb1ae","datavalue":{"value":"nondeterministic computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098633$52F13629-D84E-49C8-9CFE-87D02DDEAE7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098633$03107A4D-7A58-4754-A45F-674FC7495CEB","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":"Q1098633$A8F1F26B-F763-489C-B523-2421E21113C1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2310afb7db2c571ae2c6a5ecaa4d3bd8379995e7","datavalue":{"value":"https://doi.org/10.1016/0890-5401(87)90017-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1098633$8FB8889C-01E2-42F2-92B1-CF69CD6EB2DE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"da65bf31755078794553f20d41fc3caf3fcb7316","datavalue":{"value":"W1975320892","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098633$C19FFBA6-3CEF-4204-93E4-6D735D2396A4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"211a953e4b4520afe71207d1214fd4a9f86b2ed5","datavalue":{"value":{"entity-type":"item","numeric-id":3786431,"id":"Q3786431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098633$955CEF80-BF8C-4268-9DF0-D243672D0E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098633$0038BB41-F518-497A-AD3B-8704D7AC72E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00708b4078648865d18948bef9499b484690d96c","datavalue":{"value":{"entity-type":"item","numeric-id":3867197,"id":"Q3867197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098633$F1AD5CE4-AD78-4023-AC0F-A5A075985C94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f25501d4f91c50463305e45206dfc07064eecfa","datavalue":{"value":{"entity-type":"item","numeric-id":4118828,"id":"Q4118828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098633$56564F1F-E272-4708-B4F1-469B71C9FFB1","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":"Q1098633$731979FB-D6B0-4C50-8C52-854ABF83AB15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a9db4a207e2ab9eef002ed1bcd0688887d186bc","datavalue":{"value":{"entity-type":"item","numeric-id":3957960,"id":"Q3957960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098633$B9C55AE7-40BA-435D-A856-352EF449F037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"956ac7ee1487d89c4382f105c0c7b7c72aee11a2","datavalue":{"value":{"entity-type":"item","numeric-id":797283,"id":"Q797283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098633$8C36DAE4-7B34-4500-982C-8212F12AFA36","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":"Q1098633$B2A711CE-0036-44AF-BF33-51F23597E715","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1585579ebfd8a69178e5e73a04953474dacef6a4","datavalue":{"value":{"entity-type":"item","numeric-id":919822,"id":"Q919822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee397a0437aef89ea6897e9984c5bcac7720feef","datavalue":{"value":{"amount":"+0.8222922086715698","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":"Q1098633$94779F41-E773-4409-9E0A-77B2B4CF6965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f64be5d32daf6b6f82af29b49dbde89ec5247e3c","datavalue":{"value":{"entity-type":"item","numeric-id":3204042,"id":"Q3204042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c012bce343f55a783e42b7737d73b29c5050b1b","datavalue":{"value":{"amount":"+0.8202906847000122","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":"Q1098633$781CE97D-3ECD-40CC-8CCC-A31E03A43505","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":"b721448864338d81a8b293fc5c9131e63cc5579c","datavalue":{"value":{"amount":"+0.8195182681083679","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":"Q1098633$909F8668-190C-4B0E-9C1C-758D4C999B86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f250817672c0ee83e3761812a7226eb584e914e","datavalue":{"value":{"entity-type":"item","numeric-id":1816745,"id":"Q1816745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0abdd66f97a5bbaf6c590e13da91c74deb44f42","datavalue":{"value":{"amount":"+0.8182566165924072","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":"Q1098633$DBAC614E-B77D-4CA7-9397-6CDDC3071D29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91a9e74e76a94b35a62f147f0619a48084488c3b","datavalue":{"value":{"entity-type":"item","numeric-id":3783554,"id":"Q3783554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0abdd66f97a5bbaf6c590e13da91c74deb44f42","datavalue":{"value":{"amount":"+0.8182566165924072","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":"Q1098633$12C4E014-6F2B-447D-BFFD-9F0BCB87D882","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1098633","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1098633"}}}}}