{"entities":{"Q1102749":{"pageid":1113501,"ns":120,"title":"Item:Q1102749","lastrevid":69646002,"modified":"2026-04-13T08:26:07Z","type":"item","id":"Q1102749","labels":{"en":{"language":"en","value":"Two-dimensional iterative arrays: Characterizations and applications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4051010"}},"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":"Q1102749$4504F63E-255A-4139-AD89-2C2938FE9FF7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e5cf05e208a640fcd7de669da5eb71148ebc04f7","datavalue":{"value":{"text":"Two-dimensional iterative arrays: Characterizations and applications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1102749$724EE68F-F940-4017-A0D5-64D05D6EBD80","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1758844bcd9c816b9cf70eadac751846d6c30dd9","datavalue":{"value":"0644.68080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102749$93CCF3B8-BF4B-477D-9814-DBF2F5591888","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8cdf8d4a78146002701a8f1084935c6ae02f3bce","datavalue":{"value":"10.1016/0304-3975(88)90163-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102749$87718A33-B954-411C-9F32-BB83027DFDA8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0ccf6eb6c37793d5bd821ffa019f577d6c7be3b","datavalue":{"value":{"entity-type":"item","numeric-id":243823,"id":"Q243823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$0AC35B3E-1FDB-4505-A902-75D9EAD655B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7691c0b5037162d950224611d7e13014b76238ad","datavalue":{"value":{"entity-type":"item","numeric-id":685083,"id":"Q685083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$63EE8929-B9FC-47EA-AC21-480C371D8DAA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$65894653-00F9-4DF6-83C4-AED79F94A288","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":"Q1102749$CD659612-9E3B-4635-BFD9-8028F584FA80","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"da21d97bec02fc4e67943c7f9177db4d3573d116","datavalue":{"value":"We analyze some properties of two-dimensional iterative and cellular arrays. For example, we show that arrays operating in T(n) time can be sped up to operate in time \\(n+(T(n)-n)/k\\). Thus, a running time of the form \\(n+R(n)\\), where R(n) is sublinear (e.g., \\(\\log n\\), \\(\\log^*n\\), etc.), can still be sped up to \\(n+R(n)/k\\). This type of speed-up is stronger than any previously known speed-up for any type of device. Even for Turing machines, the speed-up is only from T(n) to \\(n+T(n)/k.\\)    Another interesting result is that simultaneous space-reduction and speed-up is possible, i.e., the number of processors of the array can be reduced while simultaneously speeding up its computation. Unlike previous approaches, we carry out our analyses using sequential machine characterizations of the iterative and cellular arrays. Consequently, we are able to prove our results on the much simpler sequential machine models.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102749$DC73FEFD-16B1-4482-B5F2-C509E07EDA03","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a8ad18899f7daee4ed2b96373381fb2ababe12b4","datavalue":{"value":"68Q80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102749$257855FC-175C-4BE2-BADB-E138A8322111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102749$D37EA693-0500-4A12-9494-0794B9135CD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102749$A64C76C9-07EE-49DB-9B6A-4CFC2D6C1BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102749$76C4075A-BEB0-47A1-8322-5213601C7263","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"22c2bf24e1761e9e8cd914b9783a7873c179a7bb","datavalue":{"value":"4051010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102749$A4AFEA35-FF6F-4385-817B-0CD6F3005EB8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1977e91ed75500a6313315db9751f0bfc85043b0","datavalue":{"value":"two-dimensional iterative and cellular arrays","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102749$7202DCBA-B61A-4A07-849C-27BF4CE1DDF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102749$5982C079-BB93-4CC0-9EFC-C8DBE430DA6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"871b601c21033be2d6d01641ec21d7ecb527d5ad","datavalue":{"value":"number of processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102749$C4E0A5AC-71B9-4439-A1DF-6D044FD73172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbd8b3f005befa50389573764202c71ded08fb19","datavalue":{"value":"speeding up","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102749$D0ED0A1C-49D5-4D4F-9246-217EFBE24726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72408bc06967f42dd40820afb3047c04fe0e771e","datavalue":{"value":"sequential machine models","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102749$EE552D0A-736C-4C2F-8DDE-15C3BDE06E6B","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":"Q1102749$3FF13A83-AEE5-4945-9ECB-0AE003B48088","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b4cbef92292dce5d0b45467ff055e38bd8bd098d","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90163-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1102749$4A52BDC0-41D8-4C8B-99F2-E4792338CD0B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fb2910d095274c8dfca197efa06e34c7961a57fd","datavalue":{"value":"W1982490259","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102749$99D6A89A-7966-4C2A-95D1-A6269FFB62A5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3840b8b27aa0dca47e74213273da44cdc4044bc0","datavalue":{"value":{"entity-type":"item","numeric-id":3773378,"id":"Q3773378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$336A0DAF-B018-4B25-8A6A-F7DE32F1293D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77be87ab66e2f8859d820e3540a34826228080da","datavalue":{"value":{"entity-type":"item","numeric-id":5560021,"id":"Q5560021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$D41275BD-C3C3-4949-9EFF-40850D3455CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c6cfb441ce15018a206437beae84dca1fb4433c","datavalue":{"value":{"entity-type":"item","numeric-id":1069704,"id":"Q1069704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$6DB3EBC8-6FA3-47D1-9D84-B702323DABE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"966d3c8f316e39e798bda86a5bbdcd1db19a2743","datavalue":{"value":{"entity-type":"item","numeric-id":3885226,"id":"Q3885226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$7E756D09-EBD2-469E-A76B-EE2B95167ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$E8D00E82-33AD-4395-A2B7-B87B61D2B616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b629ebf8eea548c83b1d262dd8d6c97984a24a35","datavalue":{"value":{"entity-type":"item","numeric-id":1102749,"id":"Q1102749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$F9F01332-E908-440C-BD8D-197BBD1AAFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee48b30a85ea1745ddffcd79b90cd77ad60bfc6f","datavalue":{"value":{"entity-type":"item","numeric-id":4772714,"id":"Q4772714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$5760D47E-001F-4CD4-9E34-2CCB061EBEDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84d73eb6590c3d9cf4ea26ff9f4ca49196597a82","datavalue":{"value":{"entity-type":"item","numeric-id":4069798,"id":"Q4069798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$0A9BDAE9-B896-4267-A493-CCFE535B180A","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":"Q1102749$9EBAB339-F478-4FF8-81F3-CD0E4905B114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"baf00f66d21fc49ac8593cea662b38a65132445c","datavalue":{"value":{"entity-type":"item","numeric-id":3042387,"id":"Q3042387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$433F0C34-492D-4F15-A3B0-400BC93E2720","rank":"normal"},{"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":"Q1102749$C1EA44F4-E16C-499E-918F-2F6F5AB44C3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69714eaff54c730c6e075340341cbf001107199e","datavalue":{"value":{"entity-type":"item","numeric-id":3698306,"id":"Q3698306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$4113B0DB-309A-4C08-9FE6-B5AF083B4A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eadab63d290baf65f2bfee890094f3ce6a3b247b","datavalue":{"value":{"entity-type":"item","numeric-id":1230610,"id":"Q1230610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$5320FF0F-13E8-4E8A-AD50-BE90C4946DC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd0090a80119c003b3242ab08c09255f5f9c3e54","datavalue":{"value":{"entity-type":"item","numeric-id":5628032,"id":"Q5628032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$213349E1-C115-4DBF-8488-B46AC81D7C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4d00f377e2761953dfa1ad2164800fbd0161051","datavalue":{"value":{"entity-type":"item","numeric-id":2563020,"id":"Q2563020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$EC48E396-C74D-434D-A166-064D506FDBBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c3844add7153a57b84278b3cbc6ec75afc4eb2c","datavalue":{"value":{"entity-type":"item","numeric-id":1166274,"id":"Q1166274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102749$EF2758D2-B2AD-4001-A96C-544357961EA9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d42b33dad1d4bfd1ec5afe0b1f5c6489f3b9c86c","datavalue":{"value":{"entity-type":"item","numeric-id":4536360,"id":"Q4536360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecf4a9392cf9e1b232a5cbdd693aa61511ad96d5","datavalue":{"value":{"amount":"+0.7838825583457947","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":"Q1102749$D518A4F1-9E88-4997-8524-F62A5A305471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d67850ece14d6582e0bb2a8b2ffd3881867b37f","datavalue":{"value":{"entity-type":"item","numeric-id":4530003,"id":"Q4530003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f078e26ee08243627af014036ef76ca1facd04bd","datavalue":{"value":{"amount":"+0.776683509349823","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":"Q1102749$A2CBD7DB-377C-46E6-BCF9-6C3948156E97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44a0e9ae119fa0279f61b73116cbe4cf756b341e","datavalue":{"value":{"entity-type":"item","numeric-id":1403336,"id":"Q1403336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"222e30efb21f8bc509f47f32fd39bdc24f5c7375","datavalue":{"value":{"amount":"+0.7640341520309448","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":"Q1102749$934B0BC2-F9E7-4098-B385-FCBC6D0D72BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6c409e70002fa8bdfb19a44bbf237f4bd4e435f","datavalue":{"value":{"entity-type":"item","numeric-id":1124336,"id":"Q1124336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c527ae656798aaa9cd0be20484c4f5063495f6c","datavalue":{"value":{"amount":"+0.763580858707428","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":"Q1102749$E97B831E-13D0-40F2-87DF-13C568C2FF60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5f2af6576d466b1dad15bc087592af4febdcefc","datavalue":{"value":{"entity-type":"item","numeric-id":4934326,"id":"Q4934326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d8203df29320f3dfa999f0dadab647748547846","datavalue":{"value":{"amount":"+0.7472739219665527","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":"Q1102749$D4C77E33-B70E-410C-B8B1-031486779F2A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two-dimensional iterative arrays: Characterizations and applications","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two-dimensional_iterative_arrays:_Characterizations_and_applications"}}}}}