{"entities":{"Q5892435":{"pageid":7930299,"ns":120,"title":"Item:Q5892435","lastrevid":93305417,"modified":"2026-06-05T04:10:36Z","type":"item","id":"Q5892435","labels":{"en":{"language":"en","value":"The HOM Problem is EXPTIME-Complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6718085"}},"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":"Q5892435$4F875C31-AE3D-43F0-B36F-A58C7AA1F6E5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"87df31660e1e3eb1140d5c4d156ba96f36488d89","datavalue":{"value":{"text":"The HOM Problem is EXPTIME-Complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5892435$BF3F7DB5-F953-421F-9C53-7177ACB6DF43","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0bbacfe235bf683d0f9444aed75807c4be1d91c4","datavalue":{"value":"1360.68551","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5892435$207C9FD8-BAB1-4082-B0A6-05D4D195A272","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0da45e4d2d5726d981c5b9b92117804159507774","datavalue":{"value":"10.1109/LICS.2012.36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5892435$5CA1826C-83BD-405D-B39C-4173BFC52489","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa8f70552d1b31441d1cb7c4310ca4b03021147d","datavalue":{"value":{"entity-type":"item","numeric-id":2351262,"id":"Q2351262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5892435$B9062186-C0B9-4E30-9B94-B155F53BFB04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2fa382e71217a50c0f4fe1ba1af2f57a2bcb70d","datavalue":{"value":{"entity-type":"item","numeric-id":1041588,"id":"Q1041588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5892435$FBE3B48D-03E2-470F-8770-D6B75783E9B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"957322e0e65309e69a1881e776e7b58b540ff033","datavalue":{"value":{"entity-type":"item","numeric-id":734040,"id":"Q734040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5892435$C9D1B5A0-A65C-473D-8EEA-C2409EB9D5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5835bf4f92acf53bba03fe7a638dce870632b3ef","datavalue":{"value":{"entity-type":"item","numeric-id":1991411,"id":"Q1991411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5892435$85FEC3BD-646A-4A67-87AA-9E33BC8139E7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"582a6c5adc14cfa6944ab3a3a801ae6337273c99","datavalue":{"value":{"entity-type":"item","numeric-id":2986776,"id":"Q2986776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5892435$DD0D52DE-5061-48B2-8BBC-EE3D589CF35C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"daa85c3fca52a36a5bd491b86ad0a10dbad35089","datavalue":{"value":{"time":"+2017-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5892435$A5C795DF-3F90-4E5D-96F5-CA0C8347F1C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5892435$F0BDEDA6-2C70-4E62-BEEF-CFCEAD9F0B5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5892435$475E5A0A-5300-4704-A073-4F4FF2E92445","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f87ee2d272ef0fc6c99a6367f9200286b6110176","datavalue":{"value":"6718085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5892435$05F18A27-A175-4FB5-955F-ACE80C3E1BB1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7fe2f2415709197ca17d2732570ef76c1e4f0b0","datavalue":{"value":"tree automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q5892435$8B9D55EB-1544-483C-80DA-C25605A9C82F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c23a41d647ddb7046931530bc06b6d3eba244c15","datavalue":{"value":"tree homomorphisms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5892435$28ED0B6C-6977-4F29-A0F4-E205CB3144E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q5892435$461465A8-4C0D-47B6-8B35-9118CF001814","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":"Q5892435$D58230C1-2087-4752-9554-E503BA6FEF3D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"621cbcb4e66fbbc50a657dcf7ab6be2003484939","datavalue":{"value":"https://doi.org/10.1109/lics.2012.36","type":"string"},"datatype":"url"},"type":"statement","id":"Q5892435$57CA18BE-1260-4D01-9603-9A4518D330B8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"71ce897b46011576eb4b933e9bdc85543388192e","datavalue":{"value":"W2059186017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5892435$FE56D32E-B5F0-468F-9097-C114146FF639","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a9a8279b9103af4054cc62513f18c2caf94b539","datavalue":{"value":{"entity-type":"item","numeric-id":5895159,"id":"Q5895159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q5892435$A00425ED-51E9-4302-A75D-984E1CD364ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a8d699eefc25e0fa73f059bdd92cb39ceae0956","datavalue":{"value":{"entity-type":"item","numeric-id":2875176,"id":"Q2875176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19aa7894556a02f331b376a15bef8d6b0154cbdc","datavalue":{"value":{"amount":"+0.90123636","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":"Q5892435$2818DE3D-5E14-4D4F-A05B-2D7F3AEBA0C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f932e55330495773c97a0a3bc091381ccbd5cefc","datavalue":{"value":{"entity-type":"item","numeric-id":5395720,"id":"Q5395720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"093c179d9900cbeacf1e986261f156d0821e408d","datavalue":{"value":{"amount":"+0.9012363","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":"Q5892435$C2FA9C3D-FFC4-406D-A3D3-A47799448020","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cfef51d841649aa9b787ebdf3c89716aaaa8867","datavalue":{"value":{"entity-type":"item","numeric-id":5092416,"id":"Q5092416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57e602092791ba0c5845443e001a327f20ece708","datavalue":{"value":{"amount":"+0.8319598","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":"Q5892435$8C517601-29B6-4B18-8CB8-AAA05B99100C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"caaa91657808ff12b21053f63d83932c478f04d0","datavalue":{"value":{"entity-type":"item","numeric-id":5414628,"id":"Q5414628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"360d445cf0c89107126033aea4279fbe220fb247","datavalue":{"value":{"amount":"+0.827865","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":"Q5892435$5B08EAF4-21C3-4EE4-BA19-1F465BD7D922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af997b1ce1d14533e9566f689db18ee8b858d118","datavalue":{"value":{"entity-type":"item","numeric-id":3546332,"id":"Q3546332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"851931ad8e6d2941fce2d1f932c37184c9f8c0c6","datavalue":{"value":{"amount":"+0.8258936","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":"Q5892435$86A91F03-8D6A-4745-B7CD-BD329DCFE824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5df965925776ea8807a5d68129b4147a9d5497b8","datavalue":{"value":{"entity-type":"item","numeric-id":4993599,"id":"Q4993599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68d15e36235404fe1f3a180eab06b6d554e1f823","datavalue":{"value":{"amount":"+0.82512945","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":"Q5892435$4356ED1C-AE56-4CA3-9379-8BC3716C70CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b77ed480a859406f75e9ac04f85561c3ce32911a","datavalue":{"value":{"entity-type":"item","numeric-id":5146921,"id":"Q5146921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"030011605e58a1feb2f1bbf6aa0674923fab1237","datavalue":{"value":{"amount":"+0.8230938","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":"Q5892435$BF72B20F-5A6E-40A6-B7E3-55150F3CBDCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41739a3052c341a0309e28bbab58f093469b5f95","datavalue":{"value":{"entity-type":"item","numeric-id":1887142,"id":"Q1887142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48e9b6a0f4d12e1ebbe7e77d4f6aac9fc74d8e7c","datavalue":{"value":{"amount":"+0.8180901","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":"Q5892435$4EA4F2D8-E19F-4F73-95E0-553E3941B6BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cbefd8a6a41e178d60063974c8632afd310b965","datavalue":{"value":{"entity-type":"item","numeric-id":5425438,"id":"Q5425438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"101ba8319745144743a53d5ec40b15a53d0d3455","datavalue":{"value":{"amount":"+0.81652385","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":"Q5892435$09E269FA-D582-44D3-8FCC-AB5D0ACE0CF9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The HOM Problem is EXPTIME-Complete","badges":[]}}}}}