{"entities":{"Q3182953":{"pageid":3193661,"ns":120,"title":"Item:Q3182953","lastrevid":80187854,"modified":"2026-05-06T15:37:41Z","type":"item","id":"Q3182953","labels":{"en":{"language":"en","value":"The Isomorphism Problem for k-Trees Is Complete for Logspace"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5617295"}},"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":"Q3182953$9764DBE5-D527-44A2-9CE4-F4D43D88B3DF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"008ccdfaf6af27b5eaa0fc9072fae6a3e0fdcf5d","datavalue":{"value":{"text":"The Isomorphism Problem for k-Trees Is Complete for Logspace","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3182953$92338E58-79FF-4287-8926-7F0337827013","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"64607fa334b20a540f48208e8859612bb9415dcc","datavalue":{"value":"1250.68120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3182953$59D54F7F-5D03-4902-A3B5-2A497E2A80A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9b9f823e67265d9d38e2ebc62956d2b5e7ae890b","datavalue":{"value":"10.1007/978-3-642-03816-7_46","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3182953$A172767C-56FF-4692-985A-85441AF310DB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"05b58b5fcbd3391c826171bcdef83e0b12458e93","datavalue":{"value":{"entity-type":"item","numeric-id":259079,"id":"Q259079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$5A6CE05C-AC38-4886-8858-C0FB9B203CC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ccdbbd400f0c973fa2e979fe6e13986f59d9284","datavalue":{"value":{"entity-type":"item","numeric-id":259078,"id":"Q259078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$22337403-F30E-4E8D-98CB-6F1F6753C160","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b977ff8abcaaabbfd6e648af0f03d12bead6fd5c","datavalue":{"value":{"entity-type":"item","numeric-id":3182909,"id":"Q3182909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$769BEE22-2531-497C-89F6-D352B8A77B61","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2a6aa0081561418a11d17268add21f5937b0595c","datavalue":{"value":{"time":"+2009-10-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3182953$B07E73C1-2BF7-4DDA-9FE2-9FA4AD52CDF0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3182953$D109314A-6472-496E-9175-3D1328AE3D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3182953$0EAC8459-53F3-4796-85C7-95C4265726B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3182953$5441E945-EA85-45FE-B8AF-5F35BF3BFAFB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8d7e4a1f3175fb2a4b63c6782a6a3f18ea6f031c","datavalue":{"value":"5617295","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3182953$2582FB77-09EF-4064-AB6A-DA26551BC43D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf16bbd4a05fdbd1b003839acc80b324384294c1","datavalue":{"value":"graph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q3182953$8262BDBC-81B4-4EF1-A5DE-833D79CA558A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04d37ac76710ef76d7ff0aacc8f88ac700ca5b46","datavalue":{"value":"graph canonization","type":"string"},"datatype":"string"},"type":"statement","id":"Q3182953$B5890CC3-7DB9-4CAA-9DEB-BBFF54952E82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ed4725d47dfe790698b61f83244da63193f579f","datavalue":{"value":"\\(k\\)-trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q3182953$6125A270-2CAD-4908-90B4-CB4464096C78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fc59007b2b1960a263350309435ca1e06e896b5","datavalue":{"value":"space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q3182953$BC91C9EB-B185-46DA-B9F4-6900736BDEA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7661ffe88b240e627ef2e1d1929126c4ff5f3ae","datavalue":{"value":"logspace completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3182953$5147C111-7528-493C-9F5B-65B8D5CAE4BA","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":"Q3182953$083F1006-FA97-485B-8026-A14423BD57EB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e6c2710b563ac13e8bb2a9546b291a4e54ceec6e","datavalue":{"value":"https://doi.org/10.1007/978-3-642-03816-7_46","type":"string"},"datatype":"url"},"type":"statement","id":"Q3182953$E2085AEA-9E79-41AF-A4B9-09DC9C66A017","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8727fa772317f00d9dc36d8d3ea4cdab36b36fa6","datavalue":{"value":"W2155065925","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3182953$5E1838CB-FDAF-411B-BD74-B601B7EAB1EB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"73d7378d5c69ed19a9f647ea155dbe65e0703f6b","datavalue":{"value":{"entity-type":"item","numeric-id":5387816,"id":"Q5387816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$B0E74388-7D0F-409D-B1F6-207A02E5CA45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b094945b4b9e1e66a77bd784987a181155b84a7","datavalue":{"value":{"entity-type":"item","numeric-id":3503623,"id":"Q3503623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$9CF8BF6B-AA56-40C2-A6FC-E9433E096B0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$C3052282-FEAB-4A33-BA04-673493860E89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aed3243c6b21e043dc5a853f5918981fadd596b8","datavalue":{"value":{"entity-type":"item","numeric-id":1208403,"id":"Q1208403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$F6452558-4DBE-4653-A639-3B2587A79EAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f9f1e15e11b50f8d9fa30cf9aca94793308bb4c","datavalue":{"value":{"entity-type":"item","numeric-id":2495656,"id":"Q2495656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$B0273C5E-ED07-41BA-A0BA-F29377496024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f023620fbd9dbbb2fbdfd658726a0e0b293398c","datavalue":{"value":{"entity-type":"item","numeric-id":1887150,"id":"Q1887150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$5A7A32A2-1423-4879-9AD0-3A4D8CAE2CD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d89cb1e49464867528aeaacc74a6f0e58536d96","datavalue":{"value":{"entity-type":"item","numeric-id":4009813,"id":"Q4009813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$175A73CE-9761-44F2-8CDD-423037E44FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$6CAF9A2C-F0A1-404A-8B5D-B2B412141A5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5224136359b3dd7d2e222d49c123234f333b6dd9","datavalue":{"value":{"entity-type":"item","numeric-id":1362332,"id":"Q1362332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$A03CE2FC-F0E8-498D-B7D2-C309E227D51A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04735a02f456edbbe4d7cf2675ed40c79c6425ed","datavalue":{"value":{"entity-type":"item","numeric-id":5956832,"id":"Q5956832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$A2833215-8018-4B77-B24D-FE953EBAAA7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c435d235f5dd5d88317484b4ce4d5923395e2745","datavalue":{"value":{"entity-type":"item","numeric-id":1165581,"id":"Q1165581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$3C79CA71-FC35-4371-AE09-6248F1835F35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b01c8492a26375f82e4c7323260eb30bcd276fb6","datavalue":{"value":{"entity-type":"item","numeric-id":1401960,"id":"Q1401960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$1832A377-3C3C-40D4-B4FE-D0F5F6B87E29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e949581f9a41496e8de1a3bd3bd76059b39a1777","datavalue":{"value":{"entity-type":"item","numeric-id":3968949,"id":"Q3968949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$590259B5-4A3B-4BC1-823E-D7E5B033F9AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aff365d8186cc4c7ca2a8c01bb1842652c3c232d","datavalue":{"value":{"entity-type":"item","numeric-id":4273947,"id":"Q4273947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$9D4C5A0A-C189-432F-BD1D-78FCE3485EBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c23c4b8fb48d64858f3187ab071964f8455cea5","datavalue":{"value":{"entity-type":"item","numeric-id":3985812,"id":"Q3985812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$36395989-6A58-4D1B-B82B-6AED066B441F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cabcc6c33339345a4333f2979adeb19662b919a","datavalue":{"value":{"entity-type":"item","numeric-id":3581436,"id":"Q3581436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$A2BF5D40-069E-411F-AA1A-755AD8DA13C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dd8100d1525f7a28bc1ae7f41159ad59bc1903b","datavalue":{"value":{"entity-type":"item","numeric-id":1116696,"id":"Q1116696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$8A74C812-2BB2-4FD0-99E5-9A209E0E2902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d35e35315e9697fb8e3043167394b9b7d8ecb78d","datavalue":{"value":{"entity-type":"item","numeric-id":4651507,"id":"Q4651507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3182953$41F322DC-6AF7-4253-9052-B174C1EB5322","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dccc5fc4d61545887efe9be4bd6d15d51c5e3633","datavalue":{"value":{"entity-type":"item","numeric-id":714733,"id":"Q714733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"785896fc27a09bd50a39a3707a076274ed0d9d71","datavalue":{"value":{"amount":"+0.9745684266090392","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":"Q3182953$260DB4A9-B170-44C3-AD7E-0C04EE5A0FE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf4d4a6352b53c5f34e78edea2e8e898e842116c","datavalue":{"value":{"entity-type":"item","numeric-id":5387816,"id":"Q5387816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66c608a7186d92f17dfcff26edbd8c7adf2c6875","datavalue":{"value":{"amount":"+0.8981288075447083","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":"Q3182953$54CD06F3-4065-4A35-8BE3-B4E068D43C0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af37f60cace22d9e1556cd4250b5c9d1089f0962","datavalue":{"value":{"entity-type":"item","numeric-id":4973889,"id":"Q4973889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"692b5b38b73ab2d88871431e9e2476d7ec3af99c","datavalue":{"value":{"amount":"+0.8167567849159241","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":"Q3182953$86BFC46E-5A6D-4DA0-99CA-BCBA8858159D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a6ef1d6b2d412f708331e07706f8273bf0e0a07","datavalue":{"value":{"entity-type":"item","numeric-id":4601884,"id":"Q4601884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ff75cbe5e0a6ce3c6dce4cd8588908659c4bce4","datavalue":{"value":{"amount":"+0.8146554231643677","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":"Q3182953$B62F4DE8-3804-49FC-ACE8-0704FEBC26D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94db5b87116d6b05c6f39574b9d5a5285c13f632","datavalue":{"value":{"entity-type":"item","numeric-id":3503623,"id":"Q3503623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8c0d13187d5327515fac5aea47bc9c1c75133b7","datavalue":{"value":{"amount":"+0.8016319870948792","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":"Q3182953$079284F0-0FAC-4C8F-89F5-ECEA3B61A52B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Isomorphism Problem for k-Trees Is Complete for Logspace","badges":[]}}}}}