{"entities":{"Q4607965":{"pageid":6637548,"ns":120,"title":"Item:Q4607965","lastrevid":58291728,"modified":"2026-04-04T14:33:02Z","type":"item","id":"Q4607965","labels":{"en":{"language":"en","value":"Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6850386"}},"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":"Q4607965$4263648D-7417-493B-B8B4-57F0F00F1FFD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9c7c062ac3c4888164ffff3dd1372f62ee3cb7e9","datavalue":{"value":"1403.68368","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4607965$C7C0CB34-8E38-426D-969C-54F29F41AB69","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"55509bc7648eb9a23c34bdf1c4bb7b9957b48fa8","datavalue":{"value":{"entity-type":"item","numeric-id":295633,"id":"Q295633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4607965$2AADEB22-6C2D-4700-A962-DCB37E0230BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c0f29833bf40fff5fa7dc4e5775a8ea015827ff","datavalue":{"value":{"entity-type":"item","numeric-id":294944,"id":"Q294944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4607965$46090212-6731-49F6-98B4-9F447AB45FBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d61782a95632e98d240bf9637674286c161805c8","datavalue":{"value":{"entity-type":"item","numeric-id":732017,"id":"Q732017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4607965$66C10CCF-D268-435E-AA8D-D4B72C621DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"38eeb75c561343f28dd804447793068849465589","datavalue":{"value":{"entity-type":"item","numeric-id":294946,"id":"Q294946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4607965$EEFAF9F8-D28F-4CF6-99AF-B6692704FA68","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"23489e2614c55bc752f5452ec03daadfbea28359","datavalue":{"value":{"time":"+2018-03-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4607965$65FFFF6E-A323-40C8-AA6D-8F6F82B13F7C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e0f3dba57ec158969c4ebf5c415bac4065c06842","datavalue":{"value":"https://arxiv.org/abs/1703.08940","type":"string"},"datatype":"url"},"type":"statement","id":"Q4607965$FA86B990-A0A3-4F26-BFB7-8B708AA3FE4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"1ce505e7e96fc30351e111dad9da9652685aaba1","datavalue":{"value":"http://dl.acm.org/citation.cfm?id=3175347","type":"string"},"datatype":"url"},"type":"statement","id":"Q4607965$657BF696-2282-4819-9071-D9602CD61002","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4607965$8A621471-E625-4615-BA1F-B62BA959B021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4607965$76D8F093-557D-4D33-A2B4-B9257A9EE23B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4607965$F6DECB59-596A-4EB9-864B-961687DA0FA0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e991fd575931d9b84ec97cc23657c23aab05648c","datavalue":{"value":"6850386","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4607965$9DFCB66B-605E-4CB8-B459-45F4B14D8D93","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":"Q4607965$9C876B3B-F50E-43E0-8C0B-26EB472C36A2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba1f63ec9a82ad5b3fd036721488918e76e15563","datavalue":{"value":{"entity-type":"item","numeric-id":5002720,"id":"Q5002720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8f48ed3c6841e87e6c7b6a545cd2416f1f8410a","datavalue":{"value":{"amount":"+0.8692405819892883","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":"Q4607965$468A682C-901E-4FE0-8933-7F11CF815E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6bf3abfe45cce7af7dd671a2ecca607d72a8e91","datavalue":{"value":{"entity-type":"item","numeric-id":5428805,"id":"Q5428805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff6b1fd93314215788c716af11b5292366db82e1","datavalue":{"value":{"amount":"+0.8681610822677612","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":"Q4607965$78E5BF22-8498-417A-81BA-BE1297E34AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8994ce14b61312737965e47656bd7f906fad3615","datavalue":{"value":{"entity-type":"item","numeric-id":2930275,"id":"Q2930275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc66d1f41b6751dca2608b60e2a4cf5a7bf35db4","datavalue":{"value":{"amount":"+0.8615567088127136","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":"Q4607965$8C69AC48-7293-4578-9AA9-6CEAB496CEAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0483ddebe956cddcc4a3e6adba090fa14b3b207e","datavalue":{"value":{"entity-type":"item","numeric-id":5212811,"id":"Q5212811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0739d29af6989f97c5dae3d574345d7fcff3e34","datavalue":{"value":{"amount":"+0.8586385846138","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":"Q4607965$A38566CE-2353-4F28-AE3D-77981214231C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"506518b93edd4c873756ebf9e444fa5bbc4237c7","datavalue":{"value":{"entity-type":"item","numeric-id":3034830,"id":"Q3034830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"349474d8fe39b31f8a9f052265f3d9355b218846","datavalue":{"value":{"amount":"+0.8329825401306152","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":"Q4607965$A4074117-0A38-4262-BCC8-E88DBA9DA077","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4607965","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4607965"}}}}}