{"entities":{"Q2219057":{"pageid":2229800,"ns":120,"title":"Item:Q2219057","lastrevid":82660946,"modified":"2026-05-06T21:26:29Z","type":"item","id":"Q2219057","labels":{"en":{"language":"en","value":"Computational complexity of \\(k\\)-block conjugacy"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7297776"}},"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":"Q2219057$384514F0-B051-4368-A916-80B458C842C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"484a2485ef78572c465e841ddc676566f02e24ba","datavalue":{"value":{"text":"Computational complexity of \\(k\\)-block conjugacy","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2219057$6E58ACEA-415F-4EBA-B41A-007F4D868E5F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50ecae2a80fcb8733e62264d2810c46729201348","datavalue":{"value":"1477.37023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219057$9177E047-E3A6-4DBF-8DF0-99701AB39E56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"13ed67ba3c244ef0a7510fdc9710aeead9886f2f","datavalue":{"value":{"entity-type":"item","numeric-id":2219056,"id":"Q2219056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$A06C2AFE-2118-4072-8309-37EF0F54AAB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"99442f66939e315e7ccd2754c0403bbae45d3979","datavalue":{"value":{"entity-type":"item","numeric-id":2023450,"id":"Q2023450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$C53B0426-2C17-4AA2-B337-47A5F76D1B91","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":"Q2219057$07DC7794-4144-4CBB-B78A-FFF8C6E08BA1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a1a70f16fd8e81a4c35439aeec3d3645cd1e55e6","datavalue":{"value":{"time":"+2021-01-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2219057$50F75F1D-9D0F-417F-8598-C04CE6FDD9D6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d1b67c16e252100c0a0693816a3a2be5b009cbff","datavalue":{"value":"https://arxiv.org/abs/1909.02627","type":"string"},"datatype":"url"},"type":"statement","id":"Q2219057$75ECD272-7BAD-45C3-9090-006EA7650C23","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5d10f435b31bc668ae5e223e57b519545d8d1a96","datavalue":{"value":"The authors study the problem of deciding whether two given shifts of finite type are conjugate. They show that it can be decided in \\(O(|V|^{4k})\\) time if a \\(k\\)-block code from a vertex shift on \\(V\\) vertices to another vertex shift is a conjugacy, and a similar result holds for edge shifts. They provide a polynomial-time reduction from the 1-Block Conjugacy problem to the \\(k\\)-Block Conjugacy problem, and show that these problems are GI-hard (both for vertex shifts and edge shifts), which means that they have polynomial-time Turing reductions to the Graph Isomorphism problem. Moreover, the \\(k\\)-Block Reduction problem, which consists in finding a conjugacy to a vertex shift with smaller vertex set (by a fixed integer), is shown to be NP-complete for \\(k=1\\). The corresponding questions for edge shifts as well as for \\(k > 1\\) are open.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219057$6DFFC99A-8447-4822-8167-F4296B3C9C3F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"85b74d523e7b21c11d971d93961ac7603c62289f","datavalue":{"value":{"entity-type":"item","numeric-id":281755,"id":"Q281755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$40789AB9-138B-490B-B512-2D53EF791124","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b559307b5b2969939e6945d65ee127220f8f6f4b","datavalue":{"value":"37B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219057$5E732F19-E327-41FB-9718-7F26702B89F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219057$D5C1696C-2EFD-471A-85F2-41A49F46606B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"34c9981031b4050d34fd5486f5e15e98964980d3","datavalue":{"value":"37B51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219057$844D2708-566A-43F9-9D3F-E997267243E7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c0b69534ec7eb89edb8d9900cac904862660de66","datavalue":{"value":"7297776","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219057$56B1D580-3A4F-4823-866A-07A7020018AC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fc27f13195d7d8cb048669ac88dc081dcb2f69c","datavalue":{"value":"symbolic dynamics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219057$69BD5114-3FE7-497D-820C-19AAEAD8C84A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219057$26241852-0BC3-4FBF-B949-EAA1E0391B87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"001761d70988821ac402d2bf60499c84214e22b7","datavalue":{"value":"subshifts of finite type","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219057$B41D7A26-6813-4664-A780-FA40F8C0346F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad2e0ba7afa00100b055821b5da95179d8963eb5","datavalue":{"value":"topological conjugacy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219057$F2ECEC7B-56DB-424C-8D7D-B101E0DF6AA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf16bbd4a05fdbd1b003839acc80b324384294c1","datavalue":{"value":"graph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219057$EB6AEAFC-B412-466E-BAE7-5E97B0C6EE15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08fa0ef25ab39fb5e9452012b4bac27f24e77721","datavalue":{"value":"vertex shifts","type":"string"},"datatype":"string"},"type":"statement","id":"Q2219057$1E3654A0-D15C-43E1-88D4-3ECCDAFA4927","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":"Q2219057$77837574-CB78-4182-BF6C-9700084C09A0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"638e419736dd7208b6777aad31140d182354b031","datavalue":{"value":"W3112913557","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219057$0B0BB5EE-3BC8-4C98-868E-466D35BEA9F9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd3e0bf6d66ae7c4b6b46e88d6d5b96072d8e8fa","datavalue":{"value":{"entity-type":"item","numeric-id":5597521,"id":"Q5597521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$DB1152CD-0475-4DB2-B990-CCEEB6BD03BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b5cf6d7042df59e37c64b58e88c8552d3c4308d","datavalue":{"value":{"entity-type":"item","numeric-id":2435411,"id":"Q2435411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$E4456191-CA4F-42B6-A232-4D1206AB2718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd1ef054357be7c4ac9bd2d51fbdb2af2b2b7722","datavalue":{"value":{"entity-type":"item","numeric-id":5262755,"id":"Q5262755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$60BF562A-82B4-4B41-9DC0-06C518377872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d569e8caeb8c5d8f9cd4ae001b6508b7afc084e9","datavalue":{"value":{"entity-type":"item","numeric-id":4968744,"id":"Q4968744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$EC227122-1DFF-4815-A508-99E409875A91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f3a5177383e59c4e5db15c202df627ff35a7dae","datavalue":{"value":{"entity-type":"item","numeric-id":1051772,"id":"Q1051772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$BFE34F47-C00A-49B7-9923-575AED96EBAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ba6262c247b0eefb5f0793844714a87aab33088","datavalue":{"value":{"entity-type":"item","numeric-id":494068,"id":"Q494068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$CABF9ECD-6DFD-4E42-A305-582FE3B43B1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33bc8328c0e7b9a05dbd6858f99412be5208fd3c","datavalue":{"value":{"entity-type":"item","numeric-id":4850282,"id":"Q4850282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$E4E9590C-261E-4871-946A-9A9DBE7450C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"847f43a12784abd824ccccc602688df087916fcc","datavalue":{"value":{"entity-type":"item","numeric-id":3565237,"id":"Q3565237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$1ACF296F-5035-4F81-96C6-939836EF5BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1be0c1c70685859b86dd63059ad8e7789e233b68","datavalue":{"value":{"entity-type":"item","numeric-id":1058849,"id":"Q1058849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$7538041D-D786-45D7-B3B8-29BF7D92B9D4","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":"Q2219057$E8820D97-2326-4F1F-B168-9073DA1B7BE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93c253900e4829cb5d0d6d60e214b68399dc4e6c","datavalue":{"value":{"entity-type":"item","numeric-id":4856597,"id":"Q4856597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$7A917FD2-ADEF-429A-98A3-D9CCD5166BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5b2c0439f4bc61c9ce93f1e6d2e54fc0056bf9b","datavalue":{"value":{"entity-type":"item","numeric-id":4474938,"id":"Q4474938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$4255F889-58F8-4679-9001-6B9A99C78AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd79a1de38c165d0ca1355e68556bf899b647fc7","datavalue":{"value":{"entity-type":"item","numeric-id":703578,"id":"Q703578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$B7280C3C-179B-4F21-B04D-89C511EFCD1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61f949aa0c3b714e9ee0f674a951c14129697240","datavalue":{"value":{"entity-type":"item","numeric-id":5501618,"id":"Q5501618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$CD48018F-3963-4185-95D0-BF0E2E44BE60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b50bad9b5e66b2da9e23a06d8d2e993a52d5f6b","datavalue":{"value":{"entity-type":"item","numeric-id":1056237,"id":"Q1056237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$A58C8914-2907-4CC7-91D7-2F60A7B1021C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$934B0301-8C6B-4C7C-8D9F-8F8ADBCA6105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"003961228078b0c11edfaf7a8dc0ec4da8ff739f","datavalue":{"value":{"entity-type":"item","numeric-id":1844005,"id":"Q1844005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$E6A2DDE3-D198-4A0D-93AE-B88A52B92767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bab70f1165ff344dafeeace2ccd1e5107d4b8761","datavalue":{"value":{"entity-type":"item","numeric-id":2799188,"id":"Q2799188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2219057$9274BF77-2ED5-4384-8694-A9FB7E15F0B1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b9dd1c7792acc4aa6013bab6eaa028a2d244c631","datavalue":{"value":"10.1016/J.TCS.2020.12.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2219057$8E05B00F-0596-4FD9-8669-861A09544E5D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c905ceea9e2dd811c428fb9f7cbbbc96a886f61b","datavalue":{"value":{"entity-type":"item","numeric-id":494068,"id":"Q494068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a5f6cb94a5a06e3e261179dace7f5742b93e1d7","datavalue":{"value":{"amount":"+0.7873867750167847","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":"Q2219057$B1B1B63B-9890-4EF5-BA62-202DE712094A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9b0a892ffee3bbecc2e84d389ebcb706d2d0cc5","datavalue":{"value":{"entity-type":"item","numeric-id":2957910,"id":"Q2957910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4899af37c7045ed593a6e76c23ab112ebd254c71","datavalue":{"value":{"amount":"+0.7760844230651855","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":"Q2219057$DBB8D2E7-BFB5-431E-9D3A-58269AAB86E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fcbd2ade026e7c48ff0b8ce0ad07ba558bca1ee","datavalue":{"value":{"entity-type":"item","numeric-id":5501618,"id":"Q5501618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fc0d899dd5691fab4334db27ef6c399e8931fad","datavalue":{"value":{"amount":"+0.7751774191856384","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":"Q2219057$1856F0F6-B6E3-49C7-85B3-60F23CC01546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8a3c3f72b28123a6cba4c90b169665c0fa82370","datavalue":{"value":{"entity-type":"item","numeric-id":2201790,"id":"Q2201790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a93c9b5fe3ca8dd04763ca46a496fbebf623720","datavalue":{"value":{"amount":"+0.732538104057312","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":"Q2219057$86AE3D01-53DE-47BA-BA36-A386EC7B0FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"218b3213901d48c1a551093786ac3d9eea5de764","datavalue":{"value":{"entity-type":"item","numeric-id":4601028,"id":"Q4601028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"187f5b802ac2358a22ff8de670cb572022707003","datavalue":{"value":{"amount":"+0.7257716059684753","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":"Q2219057$1FD748E6-A433-40EA-9F4A-5A07BF96F6A4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computational complexity of \\(k\\)-block conjugacy","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computational_complexity_of_%5C(k%5C)-block_conjugacy"}}}}}