{"entities":{"Q894455":{"pageid":896303,"ns":120,"title":"Item:Q894455","lastrevid":55893451,"modified":"2026-02-20T22:02:03Z","type":"item","id":"Q894455","labels":{"en":{"language":"en","value":"Weak containment for partial words is coNP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6515010"}},"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":"Q894455$85403749-DDA6-4E02-9EF4-B61A0C4B1780","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"41f4bbc2f70ac264dff2b76e6d52d991da6bdf18","datavalue":{"value":{"text":"Weak containment for partial words is coNP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q894455$8D17EAEC-C3B7-4871-B542-AA863F9EF2BD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b4a6f492b78fb3f8c7343b79dbd5854b126d21b2","datavalue":{"value":"1346.68104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q894455$CB004A3B-8866-48A1-A222-B68BD6B78CCA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"40f8cdd386691c1fea5e73df605fd6f51a4e84c6","datavalue":{"value":{"entity-type":"item","numeric-id":894454,"id":"Q894454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q894455$5C7B2CA5-C15E-4A3E-8E52-8C7D00566EEB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q894455$D357F0B9-B4D5-4D5C-AD3D-0111C00F7D08","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"da855e53f2567d39cf3030e0ffe950af64a120ed","datavalue":{"value":{"time":"+2015-12-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q894455$A72FBC53-F2B5-4EB8-BF5D-DCFA6C90B056","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q894455$569F161C-56D8-4B4E-A5F5-B46B420241CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q894455$320A14DC-2C44-44A0-8EAD-139CDC239E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q894455$D45A46C6-DD2E-43FF-840D-1B79727AE35E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7ec5d5f3638005278c8f7510667af39a82e13698","datavalue":{"value":"6515010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q894455$ED0F14C9-72A8-4FE3-A8ED-6149061447E1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q894455$3DAAEE17-79E3-414E-9768-5CB4EBE3BC30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b30b88dd7d8d4d3a542dd1829bf3206a53951e76","datavalue":{"value":"formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q894455$2F07B33A-4812-4448-B55F-8A0AAF2C2B89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q894455$83A2D9BF-9F42-4833-9742-1049CF40BFD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"665bb6b521670920ffccf875b8511ad8132838e1","datavalue":{"value":"partial words","type":"string"},"datatype":"string"},"type":"statement","id":"Q894455$2B651023-B826-4084-BABD-555A87B4947B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b35a6a24dd17ea6cf383183766c8907eb9f2ef44","datavalue":{"value":"language containment","type":"string"},"datatype":"string"},"type":"statement","id":"Q894455$694CB35A-F7FD-450A-943C-586C6B62E2FC","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":"Q894455$B339A027-3CD3-4A34-96AD-CCE9D18ABB26","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b4739bfe4a9f814444714f72dd6ae580c670e29a","datavalue":{"value":"https://doi.org/10.1016/j.ipl.2015.09.012","type":"string"},"datatype":"url"},"type":"statement","id":"Q894455$5C5CF1F6-335F-4D9A-9279-810BD7FF8F00","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d69d6e7113dc75e4f7811f159d35d8dddfd85be8","datavalue":{"value":"W1792989921","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q894455$27D39CBC-670C-44F9-911A-AF6A2B64C613","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"258bdba76977b3dec81e7e3a5e90f663de66a9f8","datavalue":{"value":{"entity-type":"item","numeric-id":5310364,"id":"Q5310364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q894455$FB77A81C-AA6A-4262-BCFF-15CDE0D8FD90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ba9214aaf197e0dad09c300c02fb1eacaa0c984","datavalue":{"value":{"entity-type":"item","numeric-id":4414544,"id":"Q4414544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q894455$2E444BC4-F091-4B44-B999-D139C0A743B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2ed9b1523dee5db6b9bf9bae8d86a503b2a11b7","datavalue":{"value":{"entity-type":"item","numeric-id":5310660,"id":"Q5310660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q894455$F569271C-F15E-4CBC-ABE3-A85982353874","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"179ad11066acb9c1a2e4a3d98d88eb4154a23def","datavalue":{"value":{"entity-type":"item","numeric-id":1006080,"id":"Q1006080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q894455$A873C4C1-817F-4061-9E46-DE479D70DC32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fc64030bccc14deb766230da3cd19b2bb422e01","datavalue":{"value":{"entity-type":"item","numeric-id":606993,"id":"Q606993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q894455$C51D08AA-20DF-47AC-9AC8-D4481A99BB2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d28381db0cc9171cd20e9cc271545db33fedd9c","datavalue":{"value":{"entity-type":"item","numeric-id":1936243,"id":"Q1936243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q894455$6F5C0D14-6467-400C-BA23-065F899B70E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q894455$8507437F-8EC6-47A4-B201-233E1A15BE32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"206ff31569177ea06a4e652d651723252dfe962c","datavalue":{"value":{"entity-type":"item","numeric-id":5501184,"id":"Q5501184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q894455$BC5A83CC-B9E3-4FD5-8BE0-2B50DE19F06A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3acf403ece7a1fc8dada298b063e044eae750dc3","datavalue":{"value":"10.1016/J.IPL.2015.09.012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q894455$CEED20FE-3A90-495A-99B9-8F10C5A747BD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25f798157d1a5c670d5ad528c22b8251f5bc98c1","datavalue":{"value":{"entity-type":"item","numeric-id":5958314,"id":"Q5958314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa70a5b7a2b9ac8300937d2e3c72e251faaca617","datavalue":{"value":{"amount":"+0.8440023","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q894455$8C9B0F4C-3018-44BD-BEED-37384F47FB9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7015766e2bd561c602c693a445068f0ea867003b","datavalue":{"value":{"entity-type":"item","numeric-id":3056274,"id":"Q3056274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e831dfa31e92e5a794e15a034b2d13041cacf67","datavalue":{"value":{"amount":"+0.83475536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q894455$6D49D320-59B1-4907-91A4-016AD453D4F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00d7abd43584a3ac46680ea1cedd5e2ee990cc5f","datavalue":{"value":{"entity-type":"item","numeric-id":6156535,"id":"Q6156535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdf6ec076896a2a861a0cba17fd43dc4354d7d41","datavalue":{"value":{"amount":"+0.83346635","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q894455$7AFDFB00-0701-46C0-88FD-D67C6666D83E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2b927e2b4469b0351786072e69a567c9a75b0cc","datavalue":{"value":{"entity-type":"item","numeric-id":1292487,"id":"Q1292487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c17e4aa78fca19228ec97a0b084f12df4c1b24a","datavalue":{"value":{"amount":"+0.83232","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q894455$9AF1EB7C-4B0A-469C-B2C9-C809E384A24A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46df79e7810c6a81b6018398d50e74d69c55edcb","datavalue":{"value":{"entity-type":"item","numeric-id":3637218,"id":"Q3637218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"849003b3e13b50df301a963f51f8036e177efad6","datavalue":{"value":{"amount":"+0.82697004","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q894455$3D01BD61-306E-4F1D-8580-E9AB2D26399F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0c2a02cc089c38ff0524f652f00da0dfa29077b","datavalue":{"value":{"entity-type":"item","numeric-id":606993,"id":"Q606993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"849003b3e13b50df301a963f51f8036e177efad6","datavalue":{"value":{"amount":"+0.82697004","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q894455$03BA3C05-0939-4D17-8289-32EA980B20BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0bf583cb97a6b3ecce9f4a1ab516cc100e91bd1","datavalue":{"value":{"entity-type":"item","numeric-id":664721,"id":"Q664721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"439ca0c4ddd0336da6c1a7bab8c8461419ff050a","datavalue":{"value":{"amount":"+0.8201806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q894455$C2E3366D-BB7C-426B-9388-6A44BCE65CAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26c6b403d3f7ba4f46c4229cf17611a85653cedd","datavalue":{"value":{"entity-type":"item","numeric-id":1936243,"id":"Q1936243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"343973a0009b459041557625894e56289d06391b","datavalue":{"value":{"amount":"+0.8163317","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q894455$FADF7DB5-B291-4ECF-9653-EAAD12D61730","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:894455","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:894455"}}}}}