{"entities":{"Q795505":{"pageid":797353,"ns":120,"title":"Item:Q795505","lastrevid":64399596,"modified":"2026-04-11T19:36:40Z","type":"item","id":"Q795505","labels":{"en":{"language":"en","value":"Minimizing access pointers into trees and arrays"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3862436"}},"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":"Q795505$F6B67C8B-72C1-46D9-A6F5-A57886F89685","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b4cca968362b28636f89295433141a42d612b1f","datavalue":{"value":{"text":"Minimizing access pointers into trees and arrays","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q795505$3D32DD38-819D-471F-9C03-74428B0EBF5D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1848d0b20ae5e84523f6c791817d5f1dfe39a6c0","datavalue":{"value":"0542.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795505$D3C4F5B5-E81A-4F83-8921-4B0690895B8C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bd59436b993e632d0e1590dfc911168c54563638","datavalue":{"value":"10.1016/0022-0000(84)90019-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795505$10F5897D-AB77-43DD-BAD4-23604FF68120","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795505$C992202E-CB8A-4B09-84FA-2EB15C784704","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q795505$8AFA6D98-A06A-4E21-9872-78861D7DA25E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"03ac472f46faa6d9f7e6a4cb90da1c111d988e46","datavalue":{"value":"Multihead tree machines and multihead multidimensional machines are used to develop new methods for minimizing access pointers into trees and arrays. Every multihead tree machine of time complexity t(n) can be simulated on-line by a tree machine with only two access heads in time \\(O(t(n) \\log t(n)/\\log \\log t(n)).\\) Every multihead e-dimensional machine of time complexity t(n) can be simulated on-line by a d-dimensional machine with two access heads in time \\(O(t(n)^{1+1/d-1/de} \\log t(n)).\\) The simulation for trees is optimal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q795505$9DF04AFA-3372-43F4-AE3F-EFFA12A52C56","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795505$50D27528-278D-468E-9236-479682A93EB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795505$652D7FA8-DA3B-45E7-9CBF-8041343C3107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795505$3A6D1B3B-D04E-43BB-BB27-8609556585F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795505$18DC7AA2-C678-4703-AD33-E07A897706B4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5c5068a339be7ead77f70032e0271898f7234ba1","datavalue":{"value":"3862436","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795505$AA44B27C-17ED-4353-9A3F-1D30993A5A6D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d6c94e262c4b03b2992983de20348792520d315","datavalue":{"value":"multidimensional Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q795505$8E4AAC0E-301D-41BB-B200-9811098D75CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f828563fee5a57e5f16da87a79378ac587cea3ac","datavalue":{"value":"simulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q795505$EE3DAFE1-3B4B-4838-B23A-477D710ABD7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q795505$0DC2F4DC-3E30-40F6-8B9D-B1676E114EC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5c0ca12856c944b0f991a948a67401f2c8eb279","datavalue":{"value":"Multihead tree machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q795505$94B9EFA8-D45A-418C-A89E-FE2F3A41217B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42b64c52a6d085499fee3edac196171c1dde412e","datavalue":{"value":"multihead multidimensional machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q795505$4AE7406C-425B-4A7F-B053-1AB596441D31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d9751be47180d854ad83124d2d11b56f8be709d","datavalue":{"value":"access pointers","type":"string"},"datatype":"string"},"type":"statement","id":"Q795505$CF97D00A-76B4-4442-AD2A-3DF3C41BDDD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q795505$5FD6D065-46C6-4CBB-94B3-08982AD3FC53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3270f1a4769ce41d92ad7a61e341b778f67336e6","datavalue":{"value":"arrays","type":"string"},"datatype":"string"},"type":"statement","id":"Q795505$C6367EC7-7361-4B32-9557-0936A7B3D262","rank":"normal"}],"P16":[{"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":"Q795505$8B3556AA-1C72-483C-868F-BBD1D04BEE3C","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":"Q795505$673D09FF-F30E-4C4A-9F2D-3E334D4C2207","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"971e02bc3d590d547a2a365c22936a52401bda29","datavalue":{"value":"https://doi.org/10.1016/0022-0000(84)90019-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q795505$9D9DC8AF-A5D0-428D-BB00-5F09CA3BE7C2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d49e90d5b7526f4701c74e34f2783fd4106a0937","datavalue":{"value":"W1576817182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795505$A8B1DF47-AD7E-41B4-B0CB-E2EB231CD0F2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"700ae2d00348856a62260143ca5e8fbfc44cef28","datavalue":{"value":{"entity-type":"item","numeric-id":3938480,"id":"Q3938480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795505$7D7BC8A1-74E5-4EF6-934F-15D573374EC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ceef573154a92e6e4286836ae267be7e42e9ffc","datavalue":{"value":{"entity-type":"item","numeric-id":1226857,"id":"Q1226857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795505$E5BCA822-1E93-4643-B86C-C62535DF1092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a1abf0ec1abf337ad5daf1409b3e69fe79a4c97","datavalue":{"value":{"entity-type":"item","numeric-id":5526975,"id":"Q5526975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795505$7D55D4B0-CF53-4138-BB29-FB9C22C661FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795505$366C1581-97A4-461E-A47F-7455FBEA623E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795505$1FDB7A83-D265-4164-ADEB-2D6E417CB0B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"609827d615096bb66d710b3f486ba33c91600d45","datavalue":{"value":{"entity-type":"item","numeric-id":3902483,"id":"Q3902483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795505$DCF2BC13-6F1F-4970-A79F-36D159CFF66B","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":"Q795505$00A4FBA4-0C4A-43AB-BD2D-B3EA67BF9079","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":"Q795505$493143F5-DFD1-47DA-871F-C372F19F9FEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f784fed1af1400bbd1a75108ed44085f78e30f5","datavalue":{"value":{"entity-type":"item","numeric-id":1156484,"id":"Q1156484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795505$CE423EC9-B188-4508-AE87-B6995629B230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d576f2c4009976628e3d23d58af4decef38eafd","datavalue":{"value":{"entity-type":"item","numeric-id":1152954,"id":"Q1152954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795505$FA4DECDD-A81F-46D9-BF33-A2CC317D3628","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":"Q795505$07FB5FDA-18A4-4095-995D-F03992B412F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd766d5adbec21ff5e00ea1cada60c4f11dd9f2a","datavalue":{"value":{"entity-type":"item","numeric-id":2547546,"id":"Q2547546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795505$1E4AA6FD-3142-4421-A28B-CFC2ECF4E381","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbb7b226741b3538c95c4a5b655167299b7dfd00","datavalue":{"value":{"entity-type":"item","numeric-id":3541950,"id":"Q3541950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b46916cc61beb9fadc24bd6e4035819fce5a7ba","datavalue":{"value":{"amount":"+0.8613211","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":"Q795505$D3658141-C8FF-4D6E-A8A1-7C930750430D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07dbdcd2d5768c6a929dbef733f7fb113cf5bde2","datavalue":{"value":{"entity-type":"item","numeric-id":3341920,"id":"Q3341920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"012499eb1e699867d76bebb360448eabca7f9532","datavalue":{"value":{"amount":"+0.8109547","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":"Q795505$DD35AAA3-8A96-4189-A52D-2EE63E5D436F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a15624e87c2a456fcf631800fcc42da6d848b086","datavalue":{"value":{"entity-type":"item","numeric-id":582042,"id":"Q582042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f1355e0a73e0b313e3a4f23b3d95bb3b8e89bad","datavalue":{"value":{"amount":"+0.8063147","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":"Q795505$DD1C326E-86CA-416E-8516-30214E99CACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58c3037f9f6dab17591c4dfdd9d7c2f5c3c007cc","datavalue":{"value":{"entity-type":"item","numeric-id":2397148,"id":"Q2397148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b27592005a52a6abffd88a99177e8c54d097dbcd","datavalue":{"value":{"amount":"+0.8031495","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":"Q795505$0504A0EE-6107-4177-B736-A78375ACE8E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e14129fbecc7edaf484af54eeb31a0ea3fd2b357","datavalue":{"value":{"entity-type":"item","numeric-id":4411356,"id":"Q4411356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fed8acd1ce422834553d3459405ebe9e4e85c59c","datavalue":{"value":{"amount":"+0.80293936","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":"Q795505$2EB70505-FDE5-41CB-A835-1B0E69C7266C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac5536f95145b302abcb64d394cb2596afb6295c","datavalue":{"value":{"entity-type":"item","numeric-id":3685210,"id":"Q3685210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3bf4610be6e68364e8b118ad8804d58cfdb6317","datavalue":{"value":{"amount":"+0.80158377","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":"Q795505$6B4DDD51-A21A-460A-A188-C159903A89A2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimizing access pointers into trees and arrays","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimizing_access_pointers_into_trees_and_arrays"}}}}}