{"entities":{"Q1099090":{"pageid":1109842,"ns":120,"title":"Item:Q1099090","lastrevid":49143034,"modified":"2026-01-06T16:12:47Z","type":"item","id":"Q1099090","labels":{"en":{"language":"en","value":"Systolic processing for dynamic programming problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4039670"}},"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":"Q1099090$E1171207-D714-4240-A2C7-15B7FDFBD3BF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0ef2af5f19970a63627bef0232435af13386fe06","datavalue":{"value":{"text":"Systolic processing for dynamic programming problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1099090$C95A2E1D-FED0-4B6F-AF5D-6D1121178BA0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"47ac56ba4bfb84e9e9cbae816a5e5d40bca33748","datavalue":{"value":"0637.90098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099090$8EA41739-0BE2-4C4D-9F10-B9CFD5827EA8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"47914d1b2662ce575d133dfa1190c18cc4c0e016","datavalue":{"value":"10.1007/BF01602094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099090$765401BA-797D-4BE2-B351-08A813071D04","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac0188055b78f7bdc09193cefa1d8540feec0a11","datavalue":{"value":{"entity-type":"item","numeric-id":1099089,"id":"Q1099089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$E515E466-A800-459C-AF23-3E86832ECCB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"08dd938ef4693752d42ef6313d94bd33a02dcd6b","datavalue":{"value":{"entity-type":"item","numeric-id":1310958,"id":"Q1310958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$2D3C9C16-1C6F-4DB6-AF46-02AF1A1C5FAE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"25364cb6f58b827e4119f8c3b4fe4fd58b63c477","datavalue":{"value":{"entity-type":"item","numeric-id":163034,"id":"Q163034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$075F6D61-580E-4197-AFBB-017D8FAF7238","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":"Q1099090$5A2B08FC-AE26-40B1-B53F-ED9CCE185ABF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ea8aa34c5d6fdd55bd531f7bb4776ddb0395a2d1","datavalue":{"value":"We investigate systolic processing for problems formulated in dynamic programming. These problems are classified as monadic-serial, polyadic- serial, monadic-nonserial, and polyadic-nonserial. Problems in serial formulations can be implemented easily in systolic arrays; however, nonserial problems may have to be transformed into a serial one before an efficient implementation can be found. A monadic-serial dynamic programming problem can be solved as the search of an optimal path in a multistage graph and can be computed as a string of matrix multiplications. Three efficient systolic-array designs are presented. A polyadic-serial dynamic programming problem can be solved by either a divide-and-conquer algorithm or the search of optimal solutions in a serial AND/OR-graph. We have evaluated the asymptotically optimal architecture for divide-and-conquer algorithms and have developed efficient methods of mapping a regular AND/OR-graph into systolic arrays. Cases are studied for transforming a problem in a nonserial formulation into a serial one.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099090$86AE3D0D-2A40-4E12-B669-52C3D1AAC02B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099090$91C3E0E7-A23B-4211-92D6-36296CB74411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099090$E9DF3EFB-A3A1-4DB1-9EFB-4FB223A19827","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"29ab57850be542577feb61435f71f036f57c91ce","datavalue":{"value":"4039670","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099090$0F0F4148-3ABA-4B55-8182-A6490824CC47","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd4a81f6fd2fb67b0a6dab6d1a53a70474c9ef77","datavalue":{"value":"systolic processing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099090$D79581A1-DC42-473F-9B0F-D7A76281E7A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3611715e191f9b27b41183a3d6b44a200c22525","datavalue":{"value":"monadic-serial dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099090$64C11693-F098-4364-AB1E-581081DFDAFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac5e97f9cb0f2089ba575f6c66d5c51b800ed806","datavalue":{"value":"optimal path in a multistage graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099090$9C29181C-44F6-4C19-9BBB-090EF5A09FFF","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":"Q1099090$FF5AEB81-229A-46E5-9FAC-921E419A2AF5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$FF8D2749-95F5-446B-BB99-7D037C27E5E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a3679937e0b3f254ac30f41e2ac3b68561cd039","datavalue":{"value":{"entity-type":"item","numeric-id":4146248,"id":"Q4146248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$9FB1D259-78A1-49C7-B196-C95BAE270FC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a308e30505dd380998190c7f81f45679fe7a55a5","datavalue":{"value":{"entity-type":"item","numeric-id":3292915,"id":"Q3292915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$EB4879B6-3B5E-4BB4-BFFD-587BB4293A27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fe780cbe8ac816dea3cd02afd53863f5df05807","datavalue":{"value":{"entity-type":"item","numeric-id":2534842,"id":"Q2534842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$0EDC37B1-F21C-47AA-8A37-DB3B213327B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"678e7a4be408fd6129f52f04fe687f74c25ca083","datavalue":{"value":{"entity-type":"item","numeric-id":2554881,"id":"Q2554881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$56650D22-786E-43E8-84CF-28D5E1A337DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d33af0ad9b65302ae80a39899872126ebcb9a5","datavalue":{"value":{"entity-type":"item","numeric-id":5580072,"id":"Q5580072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$EF87062A-A492-4D6F-AA4F-DD424C537561","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e89e6b739e377f860fec3e9a5ac6ebc79bad4cfd","datavalue":{"value":{"entity-type":"item","numeric-id":3926375,"id":"Q3926375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$EA930394-1449-4CE5-9AE2-B659C95AD126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694457bee6f8594efeea869392c907f1e80c487b","datavalue":{"value":{"entity-type":"item","numeric-id":2563309,"id":"Q2563309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$B76C8175-30CB-45E3-ADE1-C1D6C4FE668B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89db3e6b165f6c1970b3e679bc8499eca45ba573","datavalue":{"value":{"entity-type":"item","numeric-id":4133408,"id":"Q4133408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$1248B004-9CA3-4320-BC47-5E0234B5D88E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebfc0a861e4068dcb796730e240203b79ef7b5ea","datavalue":{"value":{"entity-type":"item","numeric-id":5538317,"id":"Q5538317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$6154CD9E-3482-41E8-9D80-B77CC9047DF0","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":"Q1099090$D0B41687-F934-427D-A94C-D119F44BAA32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed64b75b2887a7d966c6bcd5a5a28fd54ded6bb8","datavalue":{"value":{"entity-type":"item","numeric-id":3690226,"id":"Q3690226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$95415B54-0E18-4260-943A-36A2A91839E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36df6b766661c94916e046513766fc7d6a63059e","datavalue":{"value":{"entity-type":"item","numeric-id":4123112,"id":"Q4123112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$FA786AC9-A5B4-44F0-BB1D-96CEA1133E21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3c8227370b23a709289df885ca01c57567c658f","datavalue":{"value":{"entity-type":"item","numeric-id":3856120,"id":"Q3856120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$01E9A1DC-44EC-43A6-9A31-7D7B380EA4F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e23f273863469871a199ac4a03061a146b588596","datavalue":{"value":{"entity-type":"item","numeric-id":3937164,"id":"Q3937164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$F6EE20AD-71F0-48F8-A5E1-56B633E694BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb10ffc3666487ba94065de1928a619aa89c326","datavalue":{"value":{"entity-type":"item","numeric-id":5612245,"id":"Q5612245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099090$309AB99C-D1A8-4F91-8153-FF919D8F5AF9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"82516af3b87d2c1f7333744a85fd85e136d0f956","datavalue":{"value":"https://doi.org/10.1007/bf01602094","type":"string"},"datatype":"url"},"type":"statement","id":"Q1099090$F2BB7466-5293-484F-9C7C-CC9449D01EFA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"81c4c25127c38526a337e3af99edb892e3e5d757","datavalue":{"value":"W248980059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099090$305CC000-37D4-4713-BA16-DDDCA3C238B9","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":"bb2cb3fc83448537e2081a2472386469e420e014","datavalue":{"value":{"amount":"+0.8912582993507385","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":"Q1099090$FE8A27A1-53C4-4680-A99B-D888C08BE35C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a000117e17b10eb9a3c4eeb84993c38cfa64e519","datavalue":{"value":{"entity-type":"item","numeric-id":3727375,"id":"Q3727375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15afda26c2736797f331b415c77e2092c4f09e51","datavalue":{"value":{"amount":"+0.8887368440628052","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":"Q1099090$41D9A71E-D280-4F6F-8E01-B058F2862204","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":"35a62d2b3927aed2c508cb2a62e14f4ff651d252","datavalue":{"value":{"amount":"+0.8732830286026001","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":"Q1099090$A036184C-BCBA-4855-8270-918EB77AAADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea19cf09af8a786566998f2c83121a8a4bb33fdb","datavalue":{"value":{"entity-type":"item","numeric-id":1110461,"id":"Q1110461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a3d7f9806de702ab85ef1f16646a5dd4c6e6702","datavalue":{"value":{"amount":"+0.8640779256820679","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":"Q1099090$A5D864BF-304A-4086-9783-538E090B5D3C","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":"4609513b4070652cbc0205058ed3780f2385e180","datavalue":{"value":{"amount":"+0.8616758584976196","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":"Q1099090$00C4B22F-7EE9-4505-9659-59E6C737B301","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1099090","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1099090"}}}}}