{"entities":{"Q1110461":{"pageid":1121210,"ns":120,"title":"Item:Q1110461","lastrevid":66150642,"modified":"2026-04-12T07:53:12Z","type":"item","id":"Q1110461","labels":{"en":{"language":"en","value":"Dynamic programming on two-dimensional systolic arrays"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4072740"}},"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":"Q1110461$90D566ED-1B4C-490F-9252-DDC6E8A78304","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0e5d28043e67c2ffc968ed3e63bda7d90e8319ff","datavalue":{"value":{"text":"Dynamic programming on two-dimensional systolic arrays","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1110461$28C495C8-B04E-4B1D-9851-E74E88959D66","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"567e6db353962b168bff4e59e9ac6723eb61b905","datavalue":{"value":"0656.90096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110461$F3003C91-9387-43EF-9F92-D8E2CC7B6504","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d7b5ae0650cb920344877473e229db9d6661d5d9","datavalue":{"value":"10.1016/0020-0190(88)90036-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110461$CE6E5BD3-28E3-4B08-8700-F98137DBAF59","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebe21808ddccb5643b39ca69ed0e7e8fa93487ba","datavalue":{"value":{"entity-type":"item","numeric-id":920563,"id":"Q920563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110461$69AA272B-C596-4AE4-B043-D2097B8BF963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2eaadc1334874e5b5e9f7aada6692b673949bda","datavalue":{"value":{"entity-type":"item","numeric-id":407577,"id":"Q407577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110461$A837DD4F-F7E7-4157-9202-93CA13C47666","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":"Q1110461$252DA033-AD3F-451F-92F9-744891001382","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":"Q1110461$4D4B1869-6012-4D58-A8C4-A0CA49CD85BC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2acc6a7dacff3f73d8d5a7fa0f5b75b386b7acf8","datavalue":{"value":"Given w(i,j), \\(1\\leq i<j\\leq n\\), and \\(c(i,i+1)\\), \\(1\\leq i<n\\), the problem is to compute \\(c(i,j)=w(i,j)+\\min_{i<k<j}\\{c(i,k)+c(k,j)\\}\\), for \\(1\\leq i<j\\leq n\\). We show that this dynamic programming problem can be solved in optimal time \\(T=2n\\) on a systolic array whose size \\(\\frac{1}{8}n^ 2+O(n)\\) is two times smaller than the number of processors required by the best previously known solution.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110461$D919C2CE-5B28-4026-9CEE-E348FD06F9EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110461$9D626163-7711-4A80-8077-D1A191220BCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110461$8310E302-2BDE-46A8-89EC-3C5735D9A469","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"286ded37c23d8712d8bb1bb93122baf0eaa663f1","datavalue":{"value":"4072740","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110461$2775D941-17E0-43DA-88A5-FE6A853AE72A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32a8e81ea691d5d514cff76becff162c83f1629a","datavalue":{"value":"task allocation method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110461$D3872C0E-76E9-4A11-9F6C-A28538CEC1C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8e550e889f00ad92c92eb888df704d788ee2875","datavalue":{"value":"dependence graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110461$604D03A2-3584-42BB-8C42-5D1D999239C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93ed0ce67b68133eb031097707302af304ec01c6","datavalue":{"value":"earliest optimal timing function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110461$BE5100D0-CE16-4AFD-BFE6-FA6A2C86EE6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e5d3e55bd1c9e9fb37a3e5b23503cca363a4dfd","datavalue":{"value":"allocation function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110461$BF66E33C-57D4-45EC-882D-20F3C91AF0F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cca7fcd295eb9f695785426eee51f5160fdc1137","datavalue":{"value":"systolic array","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110461$E18EECF0-8511-401F-8518-53BD6E0B1D46","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":"Q1110461$CB3CF083-7279-40FF-9B65-8E6B3D2D1BF7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"060d50558623a189632b3e84345acd7c55199147","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90036-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1110461$4BDF9D69-271D-4821-86E5-83CAE8B0D659","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3425b32b322e5bb5e02eb30702b636bc6f1878cc","datavalue":{"value":"W2087977785","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110461$E010B2B9-9B1C-46CF-A11B-3774485F83AE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"95881289436e1f41c650fea9ed8b8214cfa08b2d","datavalue":{"value":{"entity-type":"item","numeric-id":1053457,"id":"Q1053457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110461$09619F27-1330-4114-A587-98E6458F4A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"090625e426b30fe72d5b2b9c92c295e05148bff9","datavalue":{"value":{"entity-type":"item","numeric-id":3768390,"id":"Q3768390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110461$3E9E6E5D-D9A9-4997-A631-14AF411FF6D9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f09b45d733e718e29c8a53a96ccf62f2b79bbf1","datavalue":{"value":{"entity-type":"item","numeric-id":2365569,"id":"Q2365569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52d12bb5758b44ff9102ebd56b096e3d36a00701","datavalue":{"value":{"amount":"+0.891663134098053","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":"Q1110461$73F9BEAC-0960-4F3C-98F5-C5A361EBEB1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64664646206a3e00c2e6ceadde681068aaa1d0c9","datavalue":{"value":{"entity-type":"item","numeric-id":3989775,"id":"Q3989775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f368f7ea359f566b67bd3b5325be25007985b4d0","datavalue":{"value":{"amount":"+0.8916584253311157","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":"Q1110461$C898E222-081B-4634-A210-6D808B837D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff1cf8afccd203728a39edc9d95d1fff2a6bc7ab","datavalue":{"value":{"entity-type":"item","numeric-id":4031601,"id":"Q4031601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"754d76d331ac4c03c0c91944bfc4605d976d3330","datavalue":{"value":{"amount":"+0.8888976573944092","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":"Q1110461$DB81FD45-030A-41C5-8035-6E78F81F5C71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8223875fede01272f1b44635e3ae1dd2df5b879","datavalue":{"value":{"entity-type":"item","numeric-id":1324387,"id":"Q1324387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e833f9a44d607512227921410bb24d9167669d0e","datavalue":{"value":{"amount":"+0.8789880275726318","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":"Q1110461$BE2943EF-0146-447D-84EC-00CEAC548FA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e263286bbf039d7bccee334d74f5434e48b9dc7","datavalue":{"value":{"entity-type":"item","numeric-id":3743144,"id":"Q3743144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03f8fec66bbd2954f8e0bbb10d98d4f9b775d79e","datavalue":{"value":{"amount":"+0.8764960765838623","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":"Q1110461$FCDABC42-5A9A-4107-8FDC-15D282994EFF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Dynamic programming on two-dimensional systolic arrays","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Dynamic_programming_on_two-dimensional_systolic_arrays"}}}}}