{"entities":{"Q1105377":{"pageid":1116126,"ns":120,"title":"Item:Q1105377","lastrevid":69653580,"modified":"2026-04-13T08:28:36Z","type":"item","id":"Q1105377","labels":{"en":{"language":"en","value":"Optimal dynamic embedding of X-trees into arrays"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4058872"}},"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":"Q1105377$3F46BE2C-C843-4D31-8A89-7646BAA7B8B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e3614379a2eb3411092dc6cee6380de70cf3362","datavalue":{"value":{"text":"Optimal dynamic embedding of X-trees into arrays","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1105377$2BAC46E7-4628-491F-B2F9-B24BB74C8E3C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b50115686cb1f005e41f1275d18fd1af735a9a59","datavalue":{"value":"0648.68064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105377$F73D980C-AAF2-4F02-A57D-62B9016DA3A9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"62074390814ee6cb5a7445acd3d12f1f823aaf1d","datavalue":{"value":"10.1016/0304-3975(88)90144-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105377$FCC78CA8-8D82-4B96-8EB3-8D5B245EDBD7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f171cb22b85167751cc7633abf02a7a314612020","datavalue":{"value":{"entity-type":"item","numeric-id":1105376,"id":"Q1105376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$48658D02-1DF0-4947-A785-2330FE87043F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"81a20ea94e2ea429e6afe984dad2da3494412836","datavalue":{"value":{"entity-type":"item","numeric-id":1060009,"id":"Q1060009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$0A29D4A1-7F5B-49B9-8A86-0A5768ED6EAA","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":"Q1105377$4EBC8100-9BEF-426A-81E9-1FFFF1D56835","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":"Q1105377$8BFD6283-1F3F-4CB5-9B13-7DA338ED099A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"854a4400ceffbcac0b57e41d5b1ea90ccd50ad3e","datavalue":{"value":"We present a dynamic embedding of the contents of a storage medium organized as an X-tree into a storage medium organized as a d-dimensional array. Let X be a multihead bounded activity machine with a single storage tape organized as an X-tree. A multihead bounded activity machine D with a single tape organized as a d-dimensional array is used to simulate X on-line. If X runs in time t(n) on inputs of length n, then D simulates X in time \\(O(t(n)^{1+1/d}/\\log t(n))\\). Furthermore, this simulation is optimal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105377$262BD827-4B70-4252-84C1-70D4174F7D97","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105377$6D45FEB5-CA2A-477D-A876-4C6F698C5D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105377$0DE2BB99-BC58-4FEE-8AFC-293EB125BD32","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6d3276ead4fa3c0d03ef5fad7dc8061ef1108ce1","datavalue":{"value":"4058872","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105377$1D5360F4-9F34-4693-99C8-FDDC5B9B3CDB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f7ef08f60df3d2f476100b4e10b28c2754d5b6a","datavalue":{"value":"on-line simulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105377$7D560E5C-5D1A-4500-B3A3-CC930E3D8FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b415bf93787590464eb46e1aa4d9845d85f82774","datavalue":{"value":"dynamic embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105377$73CF9B7F-3F18-4C15-83F4-0ED6A5410CD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f46436938ff89e6870cb73a8eec3cfb8548f196","datavalue":{"value":"storage medium","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105377$0F18B7E9-0FEF-4EE1-85DD-97FB97A28CB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2f6fc003a68b5549a7f46839dbd7ef9fac5f62c","datavalue":{"value":"X-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105377$2D326518-4AE0-4EDC-9CEA-3373963713F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f98b054f0f1d80c4d5f81acc12a80f93a378f42","datavalue":{"value":"array","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105377$56770F5F-66F3-41BA-9526-89050ABFEA00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97d870676d3e263c5012773554596c0a437d4611","datavalue":{"value":"multihead bounded activity machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105377$66F2CCDC-CDB1-4359-9D3D-20329D81FDC6","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":"Q1105377$0A6A555C-F274-4CA2-8BD1-5B8912F91F6B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a4a9967cfa76759aed8949bc5376bb8a7f057769","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90144-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1105377$CFBC3117-701E-4A2E-89BD-A7830DBE42CA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"78848b9d53e8046f293ac4fd45fcfa5e3aa89969","datavalue":{"value":"W1977252619","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105377$69F40F9E-F877-417D-82D7-53D8B5A1EBCA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"de1226518f6234cb515843a172beeb3ee5f693f0","datavalue":{"value":{"entity-type":"item","numeric-id":5582354,"id":"Q5582354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$20883B08-14B6-41FE-823B-540D193697B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f96dd575faf7b0179518adb24af9e6d05ea1210","datavalue":{"value":{"entity-type":"item","numeric-id":3862426,"id":"Q3862426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$87FBE562-6AB3-4E59-8E46-127010BEF26B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bfca8d74ac085074d3fdc3c376a602f25e71f42","datavalue":{"value":{"entity-type":"item","numeric-id":3763589,"id":"Q3763589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$F8924D51-227A-43DA-8030-EF9DAC383CF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd8627ae51c8f96016094e71da8699fd81260454","datavalue":{"value":{"entity-type":"item","numeric-id":3946200,"id":"Q3946200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$7C8040A5-0AA4-4EF3-8B82-054CAD7611A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74e9d1ee0da68d5eb9df0468a9695af2ac492042","datavalue":{"value":{"entity-type":"item","numeric-id":4099200,"id":"Q4099200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$86CAB942-56F4-4A97-AD8D-4489DD342F76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55441fcfcec00635e4ea4f80f64402f439cd915a","datavalue":{"value":{"entity-type":"item","numeric-id":3040491,"id":"Q3040491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$A7F23944-A413-4398-A9B1-7610ECF26B5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e00236ff2873c2738b9cfad7e5c705ce72670c8","datavalue":{"value":{"entity-type":"item","numeric-id":1165001,"id":"Q1165001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$716FBCD0-9027-4F65-9BFF-0895226CEB3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6de891d5a6744d6bc5da3b977613039967f9d10","datavalue":{"value":{"entity-type":"item","numeric-id":4191603,"id":"Q4191603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$82A0A85F-3883-4B3D-BBED-5C1F5A5F8D8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8b0effc062fd0b5749cb5cf7f342c7ece2cafe1","datavalue":{"value":{"entity-type":"item","numeric-id":1166931,"id":"Q1166931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105377$2CEA98B9-83B6-444C-ABD2-540039E46925","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fb5f8e17f6d43ff4940694170ec60e080e7a982","datavalue":{"value":{"entity-type":"item","numeric-id":1120283,"id":"Q1120283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc90b7d5256ea44bd9e198ba4447f85937e92e2a","datavalue":{"value":{"amount":"+0.7638940811157227","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":"Q1105377$11558B4A-FF58-44A1-AFFE-42DB865557BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3533668e04dcb6c6d871ba5162c572171d7d8134","datavalue":{"value":{"entity-type":"item","numeric-id":3150271,"id":"Q3150271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a34c02e649e83745c46004720dba94f2fdcadb0a","datavalue":{"value":{"amount":"+0.7290846705436707","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":"Q1105377$A74D1EAE-60C9-425B-82F3-A1A4F0A3D0F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8aa34b409cba031bad5890b4894e686fbf152f06","datavalue":{"value":{"entity-type":"item","numeric-id":4226499,"id":"Q4226499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a54d0a95a7df04ca19b6142fc887b5807bc166b","datavalue":{"value":{"amount":"+0.7235518097877502","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":"Q1105377$220B2A43-C5D6-4B3E-86AC-F2E8E29C39EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f976a7a7078adfee71bd73290b6d5183dc2609cf","datavalue":{"value":{"entity-type":"item","numeric-id":3990107,"id":"Q3990107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dae498b6c2adaffe39f7e2082f8f8e2c96ea9bb1","datavalue":{"value":{"amount":"+0.7185584306716919","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":"Q1105377$2B9C1EF9-8713-4A47-BC3C-7DF2C2AFCDE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92651f8fbc33daf7eabb4422e607dafd65cb5d72","datavalue":{"value":{"entity-type":"item","numeric-id":5949497,"id":"Q5949497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"431acfb033fcaa77a3079ba8cacf2d7623e8d915","datavalue":{"value":{"amount":"+0.7154014110565186","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":"Q1105377$87EEDA10-54EA-4FEF-BBAB-9633589FA899","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal dynamic embedding of X-trees into arrays","badges":[]}}}}}