{"entities":{"Q1960417":{"pageid":1971159,"ns":120,"title":"Item:Q1960417","lastrevid":72034233,"modified":"2026-04-14T02:13:28Z","type":"item","id":"Q1960417","labels":{"en":{"language":"en","value":"The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1387344"}},"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":"Q1960417$C4BBAB5A-B839-46D6-B13C-6923A4F49C0A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"86f13dccb77ae29975d8dc21c8936a77599a8e87","datavalue":{"value":{"text":"The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1960417$3860EF60-5868-41C6-BA42-E67F0FAE596C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c98f7544edfc514b66c0f061a47e7ed81c8ca18a","datavalue":{"value":"0938.03015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960417$F205FE12-D288-49EC-9623-4EC042472A76","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"48162302983ac71f3b6840d9789b68a401839310","datavalue":{"value":"10.1016/S0304-3975(98)00306-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960417$77DF7BEC-682E-4BF1-9361-DF428955D52C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$7E5A280C-6F6D-4C5B-BBC5-1D77AE9D7A62","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"195732dcabfbab6a027b397db48d9b246fab9fe7","datavalue":{"value":{"time":"+2000-01-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1960417$C0F7A7AB-3627-4D3B-8713-1B13C6D8114E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a0811775a9b2a273c37f9818f26dfa977c5a2677","datavalue":{"value":"[For the previous parts see Zbl 0877.68087, Zbl 0872.03026, and the citations given there.]   This is the eleventh paper in the author's extensive study of the expressive power of monadic second-order (MSO) logic in the realm of graph theory. Here he proves that the unique decompositions of connected graphs introduced by W. Tutte are definable by MSO-formulas. For obtaining this result it is first shown that every 2-dag has a unique canonical decomposition which is MSO-definable; a 2-dag is a (finite) directed acyclic graph in which every vertex lies on a path from a fixed source vertex to a fixed target vertex.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960417$93A5B29E-C8C9-4938-AAE5-D9B4CC3F12C5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd8503cb84d44ac2adb520ebbb11872e6dc1ec3b","datavalue":{"value":"03B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960417$03B596AF-1CB1-4292-812F-DF67F8805207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd1ebd9dd665e7350d17a40eafa30f7b99b8c1e0","datavalue":{"value":"03C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960417$081A7CDD-576F-4EDB-A28B-A84BC9414B44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960417$9350AF81-AE59-4EFB-9E97-2A8C53A2A4B5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"777b9439272e40d7f48f273a24ccf9d1545a0684","datavalue":{"value":"1387344","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1960417$1E469FB0-0C53-4E50-ABF0-CA5465A4A124","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5e0748da353cbaca68136c5462da6bce39666c","datavalue":{"value":"3-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960417$AF296CBF-BC03-4E0E-9564-FD16FD37CFD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dfd13b3fcafee84529913335756c3088d4e1f6c","datavalue":{"value":"block","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960417$1F1ABC1E-94C7-4587-866B-EF9D5E447352","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960417$CB08B647-4591-463E-82FE-7E5F84FF58C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"deacd87c364d2ca1a13d34cc0102be0f419790cc","datavalue":{"value":"expressive power of monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960417$43E11B9D-961A-4378-8553-50A1A01354FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960417$140FB37F-54A2-4A9A-9E99-1A0FD396C17A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ae338e3a0f7e4fc297d1a6b8b7128b58e68f29e","datavalue":{"value":"unique decompositions of connected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960417$EE608784-60F8-4C0B-BB29-DA2C900A3730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b30413bdc80736aeecdc7f80229ac89c0446304","datavalue":{"value":"directed acyclic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1960417$3E298AB0-1A90-4D14-8AF4-322C2A8504E1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6e07306c48ccd2e9c29ec0a26f6f3afb07223426","datavalue":{"value":{"entity-type":"item","numeric-id":591314,"id":"Q591314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$9E4BD7F8-32E1-4242-B48B-B78D40D5C4C6","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":"Q1960417$7B314658-EFAB-4D49-A37F-B727762B2862","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$EC977F28-E0A1-446D-ACEA-FC7FEF70EB9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1134f2341d7e5000fd707505605e06ca29388803","datavalue":{"value":{"entity-type":"item","numeric-id":2641288,"id":"Q2641288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$187FCB16-44FA-4842-B1F9-FCEF803FA93F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7b0768a48a3af6a2344c40720d67b58bb50a5bd","datavalue":{"value":{"entity-type":"item","numeric-id":1176232,"id":"Q1176232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$6F93292B-B198-4E97-9E4E-01680A9FDAD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b439d6b5ea1e767aee9f4d150fbcd4d20c87b7f4","datavalue":{"value":{"entity-type":"item","numeric-id":1336623,"id":"Q1336623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$51824E27-290A-4C3E-BD04-EAC36495A7B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e65180487d55de678beff9f15b2f64281465aaf","datavalue":{"value":{"entity-type":"item","numeric-id":1325847,"id":"Q1325847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$9DE7250A-3852-4BFF-B17F-1D75E4BD08A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d8ded06ea25487612e26a0a728cfa41b8d8f646","datavalue":{"value":{"entity-type":"item","numeric-id":1842126,"id":"Q1842126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$25613F34-B11E-41EF-97FB-C002B9C43B3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8aba5833662215ee6a49861d05418334754b27cf","datavalue":{"value":{"entity-type":"item","numeric-id":1366538,"id":"Q1366538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$3E66703F-49A1-45DE-8316-B0C7E68BA8F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03ed96b910c28b0a5b2e7f2a02d0a97eef2d58a5","datavalue":{"value":{"entity-type":"item","numeric-id":4379556,"id":"Q4379556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$E4ED439C-418E-48FC-B922-CC506A744D30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f7063d0442c53e72e4d7aa07ea9c08e9fcc430f","datavalue":{"value":{"entity-type":"item","numeric-id":685464,"id":"Q685464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$38224476-A704-40D6-A3EA-4195C98A4328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59f80f6e19275125de4f8e2f83f2df184481d4ef","datavalue":{"value":{"entity-type":"item","numeric-id":4342632,"id":"Q4342632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$3F58D348-9C1C-41F0-A191-91942ABB2583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b2807f3350c9e524cc27528b7acc65cf07c4cab","datavalue":{"value":{"entity-type":"item","numeric-id":685463,"id":"Q685463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$3A72E204-25F4-4D29-B28B-223B1C0482CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c928d38f2639cc55e403918c5e9fbda4efe730d","datavalue":{"value":{"entity-type":"item","numeric-id":4572008,"id":"Q4572008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$2C7FFBE4-3FC1-4BA4-8892-CB42BE187D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d946090f5d0e5a3462e6438442ed9f6fbab6769","datavalue":{"value":{"entity-type":"item","numeric-id":1578419,"id":"Q1578419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$9AD3C569-1F5A-4E0F-A894-5AC93F6EDC6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9949350a7a0f87e69f2ca613baf726246e7999aa","datavalue":{"value":{"entity-type":"item","numeric-id":4381404,"id":"Q4381404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$87281883-AFE1-4E65-B17F-C06A0E7639EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a6bb84ed63e3fc8fe28c0599a7a28ad0bb4690b","datavalue":{"value":{"entity-type":"item","numeric-id":3216652,"id":"Q3216652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1960417$020BE699-06D9-42EF-9713-280AB8CF2A29","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":"Q1960417$9928E308-F135-4E9B-8F56-67C15AC68904","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"803bd704197265c58460fa2f2f3d1eb786455d15","datavalue":{"value":{"entity-type":"item","numeric-id":5310655,"id":"Q5310655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85f1a02b7126b639134fa9d12c4f4862fb7126c3","datavalue":{"value":{"amount":"+0.8478295803070068","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":"Q1960417$8B169732-EE81-4EA2-B167-1CAACC0BBEDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58138ea89fab962108c1d2e2dc1943db1e339c19","datavalue":{"value":{"entity-type":"item","numeric-id":3439302,"id":"Q3439302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f59fb0ebadd17cbb9d15b6c6725b645f96f4905","datavalue":{"value":{"amount":"+0.8153823018074036","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":"Q1960417$A243CA80-872D-43AE-96DD-C7DD8075402C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9caeb8a5c29331a836ed19613c9fc87ba2a2e3d2","datavalue":{"value":{"entity-type":"item","numeric-id":4645296,"id":"Q4645296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da011118c0b7a04397dd9d123880d63f22c61974","datavalue":{"value":{"amount":"+0.7905721068382263","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":"Q1960417$3924D56D-FB12-488F-B573-E3876583EAC2","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":"d7d1077330cec14c6bc585b2a3ffb130c34133d7","datavalue":{"value":{"amount":"+0.7880445122718811","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":"Q1960417$28F26DDE-DA2A-475A-AC83-275B29746CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f0526c860b61012deb3c1fde89cd2359a844940","datavalue":{"value":{"entity-type":"item","numeric-id":4012672,"id":"Q4012672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ceda0688ba66f167876349f7aea72ee3f43bb2ab","datavalue":{"value":{"amount":"+0.7877185344696045","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":"Q1960417$9659B919-1A02-46A5-BB31-664DCE65BBF7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_monadic_second-order_logic_of_graphs._XI:_Hierarchical_decompositions_of_connected_graphs"}}}}}