{"entities":{"Q617890":{"pageid":619666,"ns":120,"title":"Item:Q617890","lastrevid":63093543,"modified":"2026-04-11T10:32:53Z","type":"item","id":"Q617890","labels":{"en":{"language":"en","value":"On the expressive power of CNF formulas of bounded tree- and clique-width"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5836564"}},"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":"Q617890$14FB1117-6529-4CE7-BCC3-C79B89EA4339","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e9691a2900dd9ae85d9e1aae3736555d0ccb31f9","datavalue":{"value":{"text":"On the expressive power of CNF formulas of bounded tree- and clique-width","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q617890$09937865-886A-4C93-800F-D8F259F12CFE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"781257b1190702f22b0330ce13ffedb0e7afdd4a","datavalue":{"value":"1207.05093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617890$98DE6450-6F4F-47B4-B52B-12D8D130684F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03aad0d1a79d8c7d4865d4e5fdd30aadd4f645cc","datavalue":{"value":{"entity-type":"item","numeric-id":617889,"id":"Q617889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$4CA3E5B9-3F21-461F-B36A-A3F2EDE2753C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5c6184dbf168c93692fa6f8742ab0b2d67a8b9b","datavalue":{"value":{"entity-type":"item","numeric-id":287066,"id":"Q287066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$D72B868A-4D6B-48E0-8CAC-26A5E38D2078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a0f0e89347b9bacde32a7aebf7857ddc737a00ee","datavalue":{"value":{"entity-type":"item","numeric-id":418113,"id":"Q418113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$608FECBC-3B09-45E1-B9C8-AD43208704CF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$F4F9B639-F1EE-4A8C-ABCB-01E1414A2A74","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2d14a749cd124a799ecf622509edfb6062024c1c","datavalue":{"value":{"time":"+2011-01-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q617890$95369588-882E-4092-AA09-747CEA91A9B8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"26ba4f06ff5c7e92bd3a85f32aa625ae214ffe0f","datavalue":{"value":"05C31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617890$C25B5872-EE07-4227-AC8A-68C83CC6587D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3d537511be8ebec461662796ac8b3715bfcc44b6","datavalue":{"value":"5836564","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617890$11AE12A8-39C3-415F-AAC8-372625063F33","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74e70012f98cf3c13e5a4cd8b749868e51221c0b","datavalue":{"value":"expressive power of polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q617890$441BBB41-8A86-4A92-AA4C-560E1CDA27CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e642c816cf823f8e0089eddb709a0772377d8e46","datavalue":{"value":"permanent function","type":"string"},"datatype":"string"},"type":"statement","id":"Q617890$8AAFCEEA-E7E8-4838-8D07-49CB539417D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"980dd8e82587afc8004446f8efa326739241c0b4","datavalue":{"value":"conjunctive normal form formulas","type":"string"},"datatype":"string"},"type":"statement","id":"Q617890$1A6EC279-39E8-459F-8F86-EB879CDD35BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"394c52cd2d821f6c80b633082b3f7ccc847ef4a9","datavalue":{"value":"tree- and clique-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q617890$9945CF6A-3CF4-439A-8198-40379FF6095F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c5bc7a24ffdf32456386d55fdd2574c62d14834","datavalue":{"value":"Valiant's complexity theory for polynomial families","type":"string"},"datatype":"string"},"type":"statement","id":"Q617890$45EC7B60-7117-4F01-8CD1-184C833F1DAE","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":"Q617890$631E4E7B-8A5E-4483-8D52-614982B5CB20","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"83cf33dae27f89263164a9cd60b00eb5c73f2dc6","datavalue":{"value":"https://doi.org/10.1016/j.dam.2010.09.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q617890$331CDE96-A52D-4B7B-BBE7-0E2901D7C2CC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2445cb5b17350eb1b66f4ee7c0b709b67ab58c80","datavalue":{"value":"W2117939403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617890$768F3FD8-3996-498E-8732-990C9B2B945E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae867168c941791a545c80d9051c23a76351caec","datavalue":{"value":{"entity-type":"item","numeric-id":4210129,"id":"Q4210129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$6319932A-5B3C-4B26-BA49-F9FD154DAF36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daf3e133365d57dfbd2c07919f3093669a42c66e","datavalue":{"value":{"entity-type":"item","numeric-id":5928867,"id":"Q5928867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$0BC9A534-52B0-4C36-9B3C-6A2756B36AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1b1a3469bcf85c5bdc034429e87442cc51f8c4e","datavalue":{"value":{"entity-type":"item","numeric-id":2473047,"id":"Q2473047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$70EA53E6-1FF4-415F-99A6-F7A838D2A70B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d576f4ef5c450fbec728e8e86b748890a2489004","datavalue":{"value":{"entity-type":"item","numeric-id":5387751,"id":"Q5387751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$2B6E699F-4A75-4B92-94FB-524F96284D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a8c44dbfa488b5bd1e374fbb8b00fe1343e1c82","datavalue":{"value":{"entity-type":"item","numeric-id":2766682,"id":"Q2766682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$A0666D8C-A65F-4DE8-81C0-2A6EC6B9A8F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04f53a44e60807517a77c3256c6fa193f666dfdb","datavalue":{"value":{"entity-type":"item","numeric-id":3945585,"id":"Q3945585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$24DC0EF4-87DA-429B-A1D7-E3CE105D3469","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4aebd8b6bc375a45b9e29b9a9a0c1ed5dd6bf4a","datavalue":{"value":{"entity-type":"item","numeric-id":5302060,"id":"Q5302060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$C426B466-2402-49FB-9CE0-352336810BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55bdf4ec7260080ec2ace85e7db971d84eebc13f","datavalue":{"value":{"entity-type":"item","numeric-id":1801672,"id":"Q1801672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$BDF0170F-D268-4EBF-98C6-25A5EBE97879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ec4896edc35f1e12505542682c8c6b6145a21f0","datavalue":{"value":{"entity-type":"item","numeric-id":4875692,"id":"Q4875692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$95ABF471-A953-4D27-9B9D-334839D799DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8b0b134a45d8dd196d21d2898b46944cc170dbc","datavalue":{"value":{"entity-type":"item","numeric-id":5756717,"id":"Q5756717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$006CE104-4349-487E-817F-3AF32281282B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b399d8eafcdd5c70e0a548940189236fe91ec86d","datavalue":{"value":{"entity-type":"item","numeric-id":3498488,"id":"Q3498488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q617890$15AEC7C0-EA0C-4278-8090-5196BABDA72F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"163b38d83bd10815706e92a5559a0c089cc0e5ec","datavalue":{"value":"10.1016/J.DAM.2010.09.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q617890$28E1FC73-DACE-436E-BE9B-C62459FB9A16","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e56a7bc6eaa8e8a30a0bdf2a05064eecdd9cc342","datavalue":{"value":{"entity-type":"item","numeric-id":5302060,"id":"Q5302060"},"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":"Q617890$7FE034C9-91BE-448A-B455-8A794F8FB86A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"913fbd704632b6ed04868eaee2d449e815a8228b","datavalue":{"value":{"entity-type":"item","numeric-id":2473047,"id":"Q2473047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d59f02a56819498f590d78ae95236111fbce8ba","datavalue":{"value":{"amount":"+0.90490115","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":"Q617890$FA831779-B795-4B73-AB37-513E5C92FCCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2371f93b46006cf8b5540248b92ab0b244309f7","datavalue":{"value":{"entity-type":"item","numeric-id":5387797,"id":"Q5387797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3fe84e9523bf481ff737ffd6e9a75d0db61904a","datavalue":{"value":{"amount":"+0.90136087","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":"Q617890$CA3700D8-249F-4416-965B-984FFE343079","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b96d4f1b852b8a61374a47b0bc0dffbb64181dc0","datavalue":{"value":{"entity-type":"item","numeric-id":3524254,"id":"Q3524254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df4ff42d9cfa9b18aa0e3cf8b2898cac33986787","datavalue":{"value":{"amount":"+0.8979105","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":"Q617890$FC2AA1C2-8C1E-46F2-9BC8-5CE19AB4076B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d605e935525682481d2142667b748b34b5c3beee","datavalue":{"value":{"entity-type":"item","numeric-id":847262,"id":"Q847262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df4ff42d9cfa9b18aa0e3cf8b2898cac33986787","datavalue":{"value":{"amount":"+0.8979105","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":"Q617890$118E4777-4F1C-4620-BA29-F93516174A26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e86a356e7af129cb8494580f1044ca91d6232ad","datavalue":{"value":{"entity-type":"item","numeric-id":6483555,"id":"Q6483555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ef4372a90b8a88feb7757fa51604e99d9edf357","datavalue":{"value":{"amount":"+0.8935659","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":"Q617890$66ACD6AF-4C3C-4A1A-813F-F43F4C7C63C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64997c68df677988bffa8c9886ecb295e284d874","datavalue":{"value":{"entity-type":"item","numeric-id":907218,"id":"Q907218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e990ef8843c5b6b855d16c7b174ab8819efd1e4b","datavalue":{"value":{"amount":"+0.8917699","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":"Q617890$ACC7812F-5032-44F0-BA73-C5C332022A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05f44ea0b31d180cc11f05b91490967f905df661","datavalue":{"value":{"entity-type":"item","numeric-id":4778545,"id":"Q4778545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84ceee9628bd41ac65afbc6743081df11c9ebcdf","datavalue":{"value":{"amount":"+0.8857553","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":"Q617890$CF00B65D-9BE4-4682-B9FD-5BE2F53ED49C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f76a659032d2c9aed9def5a71522def7f13bfe3","datavalue":{"value":{"entity-type":"item","numeric-id":5405029,"id":"Q5405029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4efe22834ac08599fb9a52284ab0033f16f9aeca","datavalue":{"value":{"amount":"+0.8847084","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":"Q617890$35ED3865-6D7B-498B-A0EE-AE4BF5E01BCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"818312de47ed209980e429f75a71fe2e3f967122","datavalue":{"value":{"entity-type":"item","numeric-id":6184391,"id":"Q6184391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4c6f9db64b57c8c4935504e265683e810e2bea7","datavalue":{"value":{"amount":"+0.88081217","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":"Q617890$1684A7A4-DC34-46A8-9EAD-2224474A50A3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the expressive power of CNF formulas of bounded tree- and clique-width","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_expressive_power_of_CNF_formulas_of_bounded_tree-_and_clique-width"}}}}}