{"entities":{"Q1198059":{"pageid":1208808,"ns":120,"title":"Item:Q1198059","lastrevid":66847299,"modified":"2026-04-12T13:15:26Z","type":"item","id":"Q1198059","labels":{"en":{"language":"en","value":"Sorting on PRAMs with reconfigurable buses"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92118"}},"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":"Q1198059$00E44D70-A06E-4FAB-AFF5-8BD8EB9BA318","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5990aadabb9b2a547282e91df479804f36c0939d","datavalue":{"value":{"text":"Sorting on PRAMs with reconfigurable buses","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198059$589D36D5-E13C-4344-A6F2-219D4AE8C7C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8d16bd6ef081cd482a6ed924caf817e4c0fdcfc8","datavalue":{"value":"0772.68024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198059$495F6B69-254E-4ADD-911E-7A8BC3A3BF92","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"df66cab675d9d207fff2b93396ffbbbb7f6c5206","datavalue":{"value":"10.1016/0020-0190(92)90240-V","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198059$C276FDDE-5D60-4491-AD0A-15FFD423C8C6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb8112f391e48b28783318307853b48a4655e6fa","datavalue":{"value":{"entity-type":"item","numeric-id":586338,"id":"Q586338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198059$F2A039CA-7934-418D-81FB-FB8308EFBB58","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198059$A492F5B8-A298-42FB-ADD1-35567E413E84","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198059$C6E96BE6-714C-4895-85BB-F841EA59DB2D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1904ae809c21e7461410f1da890c82f6485db10f","datavalue":{"value":"We propose a new model of computation called the B-PRAM, which is a PRAM augmented with reconfigurable buses that provide additional channels of communication. We prove that the OR of \\(n\\) bits can be computed on an EREW B-PRAM in \\(O(1)\\) time, thus showing that the addition of reconfigurable buses makes the model strictly more powerful that the CREW PRAM. We also show that \\(n\\) \\(m=O(\\log n)\\)-bit numbers can be sorted (integer sorting) in:   (i) \\(O(\\log n)\\) time on an EREW B-PRAM with \\(n/\\log n\\) processors and \\(O(n^ \\varepsilon\\)) buses, for any arbitrarily small constant \\(\\varepsilon>0\\);   (ii) \\(O(\\log n/\\log\\log n)\\) time on a Common CRCW B-PRAM with \\({{n\\log\\log n}\\over {\\log n}}\\) processors and \\(O(n^ \\varepsilon)\\) buses, for any arbitrarily small constant \\(\\varepsilon>0\\).   The above results for integer sorting are the best possible for the PRAM and have not been achieved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198059$C231BF62-9FCD-453E-B60A-FADEB473D119","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198059$2E6FF160-E7D5-4550-8400-F269C7B06CC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198059$12C4958D-EE38-4839-9E63-0F02E4DA7F03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198059$9AF3CBC5-1775-45E4-98BB-76661FABFEAD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"748763a260f9b17e08914756ca02ac788b409252","datavalue":{"value":"92118","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198059$3540617D-475F-49A1-92EB-9B5C987906EC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7968ddab794c07bcfa530eeadfb1b60c19d359e5","datavalue":{"value":"reconfigurable bus systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198059$61405060-43ED-4F98-BAD9-24B01274C39D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9d91784302c294c611860b15ae726840e15d2c9","datavalue":{"value":"EREW B-PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198059$235E4CF9-8E13-48E5-A157-3351086C9F6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f11a697ca4320b2c5e334107aae45a37f7f8f8b","datavalue":{"value":"sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198059$DB0517CB-6E31-4AC2-B41C-E7E8F68C8ADE","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":"Q1198059$CE3872EE-C3CA-44DE-93C3-4710CE63152C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198059$8EF4C9AA-745C-4258-8E6F-9BC698ADC6CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a19cf57099b1e6be1c56b1d816323c5aec82421","datavalue":{"value":{"entity-type":"item","numeric-id":3798228,"id":"Q3798228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198059$CBA04048-E179-42FD-AF7A-363386AFC078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb44e08a53e4c007a1970cc14d1cf388b1586e9","datavalue":{"value":{"entity-type":"item","numeric-id":4710686,"id":"Q4710686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198059$FFD2395A-5D39-42BE-B46D-A5C2A57E5DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7d664273a45028f8303ed3135b7eb7b45763d0f","datavalue":{"value":{"entity-type":"item","numeric-id":1175944,"id":"Q1175944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198059$B0EF5788-7947-4543-B5DA-AE211826FAE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc7e469a8fa14b237d73aa7dbd98d094baae506d","datavalue":{"value":{"entity-type":"item","numeric-id":3719831,"id":"Q3719831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198059$D259BCDA-DEE4-4EDC-AF84-D5F1FBBDA985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b2d5bb5db7e32a5821b335641e2247dc1a32fd7","datavalue":{"value":{"entity-type":"item","numeric-id":915452,"id":"Q915452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198059$AFD5640D-E288-4315-81AE-62276E3BE466","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94d0d20404a99cd5a5dc7174f471a975d7aae248","datavalue":{"value":{"entity-type":"item","numeric-id":582111,"id":"Q582111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79a0d51efdb6ead4341f3d2c741364b0f125d8d6","datavalue":{"value":{"amount":"+0.84714484","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198059$CB91B2A7-21D0-44CC-A6A3-5EF92DCCD267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36c845c614c5ea4b3dbc97fb5b921cc5fad5794c","datavalue":{"value":{"entity-type":"item","numeric-id":4843440,"id":"Q4843440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab233ee3cc3dd4adb8338e6d64e026a1b4fb4b5e","datavalue":{"value":{"amount":"+0.8282171","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198059$9A5D571D-D5A6-4AE7-9882-350D828207D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eea7a3d18ddceb61238043ab298e96af1c19f1e2","datavalue":{"value":{"entity-type":"item","numeric-id":3628619,"id":"Q3628619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8741d28e0313db1b08ecabfcb9204903a790ec5c","datavalue":{"value":{"amount":"+0.8277791","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198059$84D88FCD-B358-4F25-AC94-DBD0950E6046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1e2f62d219ecc5ba8a9a27b2b7745c49fb57af5","datavalue":{"value":{"entity-type":"item","numeric-id":915452,"id":"Q915452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb6ff012472968e387956bb7b195473390e252a5","datavalue":{"value":{"amount":"+0.7989612","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198059$D9FB514B-B5F7-402D-A1C1-00DA6711045A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e6ef1db1813a2b0398306248b92d69635aadf59","datavalue":{"value":{"entity-type":"item","numeric-id":831850,"id":"Q831850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2725b3cd0fc7bf6a6bc73e306bd4270fd84be978","datavalue":{"value":{"amount":"+0.7957328","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198059$F45F7B26-9D70-4980-BCFA-1EE356021560","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9be593567ed2816cca812d343f0d82c70be62862","datavalue":{"value":{"entity-type":"item","numeric-id":5404915,"id":"Q5404915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"782878c0918ab93743ad2092b66f55828eaf5506","datavalue":{"value":{"amount":"+0.7898276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198059$416D15AB-3D69-4056-B8FC-09D656798F98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bea6bbb77bdec6db4f41aa2c7897e02741584aea","datavalue":{"value":{"entity-type":"item","numeric-id":917287,"id":"Q917287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"931239a53694c2c023b01e4c2c981a36f5209a33","datavalue":{"value":{"amount":"+0.78942883","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198059$37BB22E9-93D0-4CB9-8D17-52AEAEE19C91","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sorting on PRAMs with reconfigurable buses","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Sorting_on_PRAMs_with_reconfigurable_buses"}}}}}