{"entities":{"Q4353558":{"pageid":6383157,"ns":120,"title":"Item:Q4353558","lastrevid":108272546,"modified":"2026-11-05T17:27:36Z","type":"item","id":"Q4353558","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1059243"}},"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":"Q4353558$73F3D45B-A2BF-4A28-BC61-A36873FF122E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4b8c0545754e2e5dbb0d2c52f74da752671d09d9","datavalue":{"value":"0883.03004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4353558$C95DB59A-B5DB-4200-ADA5-CA690A4963D9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"20d9699532b3f4e30cf94a2814dc68ff83c6f6ad","datavalue":{"value":{"time":"+1998-03-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4353558$2F76E1B4-C183-4C4F-968E-38F09E297E20","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd8503cb84d44ac2adb520ebbb11872e6dc1ec3b","datavalue":{"value":"03B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4353558$C6E9643D-492C-4B45-92A3-B4A11567032B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4353558$5E6E2B44-8914-4E3A-999D-63F751985672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd1ebd9dd665e7350d17a40eafa30f7b99b8c1e0","datavalue":{"value":"03C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4353558$AEF73FE3-5B6B-4C80-9884-961B81C87694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4353558$050CBE63-4BAC-452B-B165-A77D9D7C24DA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e2b6f78a0bea05519f41dae78a7c94e352a0aeee","datavalue":{"value":"1059243","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4353558$8E7CCC49-E5FD-45E3-904A-4F425CBAC7BB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6b3ac5948a51082073fe08b55937180405a1900","datavalue":{"value":"descriptional complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4353558$4FED9F02-BB38-4371-BFFD-89A4F3BD54D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e4048fb3bfeb12f1e8c632141b78129e67aee7a","datavalue":{"value":"graph properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q4353558$2015FA77-B782-4250-9AF8-635E7F96EB8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdcd619818ac44f3af3c94d9917c9a45f28bb74b","datavalue":{"value":"fragments of monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q4353558$C4138BA9-DAD6-4CA8-B617-F4C791D0150D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e16fdb519452f3bafdb17bd5ad06b8194f047110","datavalue":{"value":"expressive power","type":"string"},"datatype":"string"},"type":"statement","id":"Q4353558$EEB3D24E-6542-4F46-8968-6F2DC7A065CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9b8892fbe18b1921b609db96440dc9340d1a2b1","datavalue":{"value":"forbidden configurations","type":"string"},"datatype":"string"},"type":"statement","id":"Q4353558$5FE34F14-2841-41A0-B6A2-D0998C29BBF2","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":"Q4353558$5846CF5A-86FF-4362-A993-26AAA8F823F1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"084bbbb4df82d594477fd68358151d484447708c","datavalue":{"value":{"entity-type":"item","numeric-id":6482121,"id":"Q6482121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4353558$85B7D302-3523-4E7F-97B9-002F942B2389","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0874f4d378d1f6c708033223e30b475e8fd431b3","datavalue":{"value":{"entity-type":"item","numeric-id":1336623,"id":"Q1336623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15be495448d17010a1e8457852dec5c2476bb46f","datavalue":{"value":{"amount":"+0.8392714858055115","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":"Q4353558$2BB4A131-8E8D-4642-8155-1573FDE93228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66eda1faa6f9a14688d141a7261ebe70747818e8","datavalue":{"value":{"entity-type":"item","numeric-id":3613359,"id":"Q3613359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"629abe6a47c4325aa57879c98ca1a886beaf0a76","datavalue":{"value":{"amount":"+0.8347001075744629","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":"Q4353558$5DE188C8-E6AA-479C-A5E8-F79A3A9B00C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"783f27f37c37842ac75d95f3270bc9bb2865bf1d","datavalue":{"value":{"entity-type":"item","numeric-id":3615812,"id":"Q3615812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"546972a60db2914a226e40f216ccbd98283d03df","datavalue":{"value":{"amount":"+0.8012480139732361","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":"Q4353558$2A39C7FC-FCAC-4419-B71E-36012F56BC3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba33f73f8cf3e949aa159d68bc3cd85503d95314","datavalue":{"value":{"entity-type":"item","numeric-id":3086932,"id":"Q3086932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef7d2340d4560838690edb6c9deae91f2f4313b1","datavalue":{"value":{"amount":"+0.7986918091773987","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":"Q4353558$6D697170-AB13-410B-8E84-F9F77A0358EC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bd40ce768b5da1c0677d6e8e894ac45e760832af","datavalue":{"value":"Monadic second-order logic is powerful enough for expressing many nonelementary properties of graphs, such as connectivity or planarity, for example, but still it is algorithmically tractable. In this paper, the author surveys the descriptional complexity of some graph properties in terms of various fragments of monadic second-order logic. Special attention is paid to the question whether a property and its negation are expressible in the same fragments. It is also shown that in some cases quantifications over sets of edges increase the expressive power while in others they can be eliminated. Furthermore, it is shown that some properties have negative definitions in terms of forbidden configurations which are simpler than any positive definitions. Finally, some related topics are dicussed and several conjectures are presented. For the entire collection see [Zbl 0865.00055].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4353558$D24F92A0-D688-4966-A2A6-D01C0E0B4EC2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4353558","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4353558"}}}}}