{"entities":{"Q2955035":{"pageid":2965755,"ns":120,"title":"Item:Q2955035","lastrevid":85408742,"modified":"2026-06-03T07:57:47Z","type":"item","id":"Q2955035","labels":{"en":{"language":"en","value":"Existential second-order logic over graphs: a complete complexity-theoretic classification"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6677433"}},"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":"Q2955035$8E3710C1-4CF6-4667-809A-D51405F839B8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0103ffc409caf5656c69261aa8981288be3a1f0a","datavalue":{"value":"1356.68084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2955035$6DE7BE4D-86F1-45AB-9F39-CA09759D35E6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b2b224aab66ffb4af458805268689af05df667de","datavalue":{"value":{"entity-type":"item","numeric-id":418169,"id":"Q418169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2955035$68431DCC-BB95-4D93-94DB-EBEB4AB9FA6C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"39f74c103b9f673f455dbf7eb78fc5dbb359512b","datavalue":{"value":{"time":"+2017-01-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2955035$CA5A6648-64D0-4B8D-A841-9D74E236816E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"46e872086a7fc3d41f28249b529d803597ab7255","datavalue":{"value":"https://arxiv.org/abs/1412.6396","type":"string"},"datatype":"url"},"type":"statement","id":"Q2955035$788D4868-09B2-4AEA-87F8-D1968A58F0DE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2955035$477CB246-6E43-41F3-8521-B51A702232E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd8503cb84d44ac2adb520ebbb11872e6dc1ec3b","datavalue":{"value":"03B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2955035$7786D0B4-3087-481D-9D70-1FB4C379BBF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2955035$FF384912-783D-4AF8-8112-0D1C0AE3BE14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b0f166240d9dc937c89dbc2241079deae14191f","datavalue":{"value":"68Q19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2955035$33BF8750-E13D-478E-A6FA-FD57E2BCF8C2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d907da77959318bdc8272917b2e33ee79bba6f07","datavalue":{"value":"6677433","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2955035$69A51F6E-9600-41D0-B9E6-BA5D4E2A476A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8fc29fb6866ff15dbc5079f8d12fecff6f66005b","datavalue":{"value":"existential second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2955035$D0292B05-F8A4-4D48-9085-F9B56DB49977","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"420132b0a86bb9bedd0eeeab0b7b74055a6e96fb","datavalue":{"value":"descriptive complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2955035$D5B5DC65-4BC8-4E16-A2CB-1AC60DADD668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f18bc21d823222e01f5a88a6fb3d1663d7daa25","datavalue":{"value":"logarithmic space","type":"string"},"datatype":"string"},"type":"statement","id":"Q2955035$7616F87D-FD1F-4C20-A3AC-57FD379D40A4","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":"Q2955035$CC0AA765-CFD1-4471-97E8-E41A88143924","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"76a4c9bccfc54d3f2d5a22c6f1ba3c133a54dba9","datavalue":{"value":"W2963635167","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2955035$C0734646-01E5-40B5-9281-5CF9EAA96FFF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bd8dabc187db8ad5d1ac851b5a3f4d7929f2eb97","datavalue":{"value":{"text":"Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2955035$E592ED5D-4F53-4D0D-8520-BC250D2CF10D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a4ad90f19743ee2fec04e3c4a03fc0a4541228d3","datavalue":{"value":"10.4230/LIPICS.STACS.2015.703","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2955035$BA863F39-6EAA-4407-8B32-8D6457EC7CD8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3abc3481eef841dc417a6d0f4ea43f8f19ada8dc","datavalue":{"value":{"entity-type":"item","numeric-id":5501192,"id":"Q5501192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b161b7b9de58414b3af39d98a9b45b363143190e","datavalue":{"value":{"amount":"+0.9013864994049072","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":"Q2955035$40989A8C-9171-4E59-8E82-BF27DBFD0EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e9b81cf1901c48d711554662ba0c0cd454599a1","datavalue":{"value":{"entity-type":"item","numeric-id":4406309,"id":"Q4406309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9230ddef5953572373dd5fe7bb5b47833557d7d6","datavalue":{"value":{"amount":"+0.8188177943229675","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":"Q2955035$5E2D8F0F-E43A-4D74-9637-1371D16B0746","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25eaa9d75ec8a7847e2dd2867044402f08e24b8b","datavalue":{"value":{"entity-type":"item","numeric-id":4519749,"id":"Q4519749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5051343ed8cbf04fee5ed8657be6940b749e1a5","datavalue":{"value":{"amount":"+0.7646325826644897","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":"Q2955035$09C63112-085D-4139-9DB2-97A7508C5C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bcd5027a71ded3df63407d455b4c25b2572bc1a","datavalue":{"value":{"entity-type":"item","numeric-id":4227581,"id":"Q4227581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5051343ed8cbf04fee5ed8657be6940b749e1a5","datavalue":{"value":{"amount":"+0.7646325826644897","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":"Q2955035$DC5F443B-9CBE-44B6-8E59-F0E375BA9ECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e246c9a4e0f2fb2c0e72d282c9a7abd54cf351d","datavalue":{"value":{"entity-type":"item","numeric-id":1577017,"id":"Q1577017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b2591b9c911091a6b49993bf8d392b734a21383","datavalue":{"value":{"amount":"+0.757801353931427","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":"Q2955035$665F86CD-400E-4EFD-8714-CED5E57C2035","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Existential second-order logic over graphs: a complete complexity-theoretic classification","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Existential_second-order_logic_over_graphs:_a_complete_complexity-theoretic_classification"}}}}}