{"entities":{"Q839908":{"pageid":841756,"ns":120,"title":"Item:Q839908","lastrevid":64731603,"modified":"2026-04-11T21:51:17Z","type":"item","id":"Q839908","labels":{"en":{"language":"en","value":"Isomorphism of subshifts is a universal countable Borel equivalence relation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5601709"}},"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":"Q839908$067621D1-7157-4D4C-86C1-8D3DDD4384DC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0ed3d077f6581867250f72b7aa0ef755e486d6f5","datavalue":{"value":{"text":"Isomorphism of subshifts is a universal countable Borel equivalence relation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q839908$84A0D5B4-05C6-43DC-BFA5-D870CE1FD1AD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1ca61c12515397d88e333a5da462ffce17157640","datavalue":{"value":"1180.03043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q839908$22240C8B-0C7C-4911-8D47-1A1E24079C4C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f57e57c17143a07e7932f8a389a3da4d5b2e659c","datavalue":{"value":{"entity-type":"item","numeric-id":329486,"id":"Q329486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q839908$66FAC466-2FF3-4C8C-8F72-6216AEAF102F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1d50f9b953eac0b2404563f86ad398ee3823cb48","datavalue":{"value":{"entity-type":"item","numeric-id":173732,"id":"Q173732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q839908$F6DF9C17-A1B7-4D24-8201-A683D3BADF92","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ba55de1898b5b7ed159e3b67fd658ad04a96431f","datavalue":{"value":{"time":"+2009-09-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q839908$25535F13-D50F-4149-B089-56F51D0341CA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dd274cf1621b3f08769b4fd7ce358831c84bcbf2","datavalue":{"value":"Let \\(A\\) be a finite set of symbols. A one-dimensional subshift on \\(A\\) is a closed subset of \\(A^{\\mathbb Z}\\) which is invariant under the shift operator \\(S\\), where \\(S(x)(n) = x(n+1)\\). Two subshifts \\(X\\) on \\(A\\) and \\(Y\\) on \\(B\\) are isomorphic if there is a homeomorphism \\(\\varphi : X \\to Y\\) which commutes with \\(S\\). A Borel equivalence relation is an equivalence relation \\(E\\) on a Polish space \\(X\\) such that \\(E\\) is Borel as a subset of \\(X^2\\). An equivalence relation \\(E\\) on a space \\(X\\) is Borel reducible to an equivalence relation \\(F\\) on a space \\(Y\\), \\(E \\leq_{\\text B} F\\), if there is a Borel measurable function \\(f : X \\to Y\\) such that for all \\(x_1, x_2 \\in X\\), we have \\(x_1Ex_2\\) if and only if \\(f(x_1)Ef(x_2)\\). An equivalence relation \\(E\\) is countable if every equivalence class of \\(E\\) is countable. We say \\(E\\) is a universal countable Borel equivalence relation if \\(E\\) is a countable Borel equivalence relation and for every countable Borel equivalence relation \\(F\\), we have \\(F \\leq_{\\text B} E\\).   In this paper, the author proves that the isomorphism relation on one-dimensional subshifts is a universal countable Borel equivalence relation. It is also proved that the classification of higher-dimensional subshifts has, up to isomorphism, the same complexity as for the one-dimensional case. A couple of open problems, like finding the complexity of isomorphism of one-sided shifts on \\(2^{\\mathbb N}\\), are mentioned towards the end of the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q839908$D4A8B286-2F2E-4F6E-886A-FCD281D9C3B7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e51cf7a4c66e624e51b09a349d379328c590c18b","datavalue":{"value":{"entity-type":"item","numeric-id":592010,"id":"Q592010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q839908$050B3970-266F-4794-A0DB-0A4CA10F3419","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3636caf529c49b2a7d814c7a65de2b21aedf761","datavalue":{"value":"03E15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q839908$A7BA7571-F45C-4CA1-BD76-8D2054A7AB51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3933b21dbb425c0c8ed83b309b429364663b994","datavalue":{"value":"54H05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q839908$2B2729B3-CCB4-431E-80C7-D4E85D1CC926","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bca6bb0b6a8226a2455b8e92843f428977b490f8","datavalue":{"value":"5601709","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q839908$5F725D70-8F3F-49E9-94AC-C0A01B41760B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77cfba0bdc96149ac461d91f11f1240bf2a77282","datavalue":{"value":"subshift","type":"string"},"datatype":"string"},"type":"statement","id":"Q839908$9EABAB4F-497D-45C8-83DB-9E245E3BFBE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1afb0f0bcaf0e9dd05ae2cff2f0a02cd29931d0","datavalue":{"value":"Borel equivalence relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q839908$86EE0C9C-8BB7-4D79-8479-F2C346C1F3E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66519391ea9a1978cb8c59756587a65be2897a22","datavalue":{"value":"Polish space","type":"string"},"datatype":"string"},"type":"statement","id":"Q839908$0C4E7089-B149-47ED-80B6-493C5D642100","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":"Q839908$B0865E1C-4084-49C9-A76F-3784FE37B079","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"40f29ce06fabddf0a4090f962d856f92b412afd0","datavalue":{"value":"https://doi.org/10.1007/s11856-009-0022-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q839908$834ABDBA-DA8F-4CCC-90A9-A1D733263942","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f4e8f3a177b29a76cc68b71e480084b542a7f029","datavalue":{"value":"W2077516133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q839908$4A0FD979-B636-407D-97B4-4E12BF91B915","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"154794261cbaccaf4e5861b5399041bea8cb66f4","datavalue":{"value":{"entity-type":"item","numeric-id":4286439,"id":"Q4286439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q839908$B79B0E67-D29D-44CC-8EB7-3C83A66BA59F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4372fd42d55a6c484b385a2f8a72730dc0c7d8d8","datavalue":{"value":{"entity-type":"item","numeric-id":4551991,"id":"Q4551991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q839908$93330D1D-CD98-4B8B-A8D8-744CA8F69143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9f773300cd053ea51f6b2e01c0bd0b060f02131","datavalue":{"value":{"entity-type":"item","numeric-id":4323294,"id":"Q4323294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q839908$247524D5-160F-4969-A1E0-3F4C0CA5ECD6","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":"Q839908$63E270F4-6AFB-4432-96F3-D9703FE1F072","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9e18befb86e1d52dfbd7b3ee43197206a8d05c04","datavalue":{"value":"10.1007/S11856-009-0022-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q839908$27C02175-3568-4BEC-AEE0-BCD7CFA6F96C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91ec808ec020e74a6579ebaf2defbf509b36d792","datavalue":{"value":{"entity-type":"item","numeric-id":3299559,"id":"Q3299559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e332ae5944d20e4a3fd863c5fa354842cbc57a2a","datavalue":{"value":{"amount":"+0.7791204452514648","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":"Q839908$E4602CC3-64D7-47BF-90B9-5CD5A9F16CFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73fb6822a8883b4c2405bed64037a6a2d3dd53bd","datavalue":{"value":{"entity-type":"item","numeric-id":368692,"id":"Q368692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"316704b4876078bbce3af03a84030755eae1ed4f","datavalue":{"value":{"amount":"+0.7674657702445984","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":"Q839908$2C57E2EB-86C0-4878-AD80-51CE578E1795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afbda579d3a1d96fb815c1bd556d6e9156b085cd","datavalue":{"value":{"entity-type":"item","numeric-id":5444688,"id":"Q5444688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72e173ea30a7fa58bad2de8b4a6b21f696bed434","datavalue":{"value":{"amount":"+0.7631145715713501","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":"Q839908$7AC44CE3-EA87-4011-8157-46BE7F38AC68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25d7e020e51ac927427c8ae58488ec62db81cdc1","datavalue":{"value":{"entity-type":"item","numeric-id":1305085,"id":"Q1305085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"421555e4d582e9f08f14f30875557ac477d3b3ba","datavalue":{"value":{"amount":"+0.7597916126251221","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":"Q839908$066A23DD-0304-4220-8988-BC1F295FBD14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4be68a780d4a6e3f9c087ba9610c0f87fd56b2a9","datavalue":{"value":{"entity-type":"item","numeric-id":4286439,"id":"Q4286439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"421555e4d582e9f08f14f30875557ac477d3b3ba","datavalue":{"value":{"amount":"+0.7597916126251221","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":"Q839908$3F7ABE3E-5EBD-4B57-902D-F1CDCF028EE7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Isomorphism of subshifts is a universal countable Borel equivalence relation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Isomorphism_of_subshifts_is_a_universal_countable_Borel_equivalence_relation"}}}}}