{"entities":{"Q2694797":{"pageid":2705541,"ns":120,"title":"Item:Q2694797","lastrevid":55442935,"modified":"2026-02-17T16:28:36Z","type":"item","id":"Q2694797","labels":{"en":{"language":"en","value":"Simulations and the lamplighter group"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7672035"}},"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":"Q2694797$0BDFF27C-78A1-46CF-8A0A-BE9503D20C48","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f30b46a7245dacc2ecea416cc17b2ab485580cbc","datavalue":{"value":{"text":"Simulations and the lamplighter group","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2694797$AA6D8B0C-EB1E-475D-A5C8-9DE48EC024F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e06e143fb5d5968140eb0cfa753d1c830dce44f","datavalue":{"value":"10.4171/GGD/692","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2694797$A0BAA0E1-D76B-4570-AEA2-99D58F1F6917","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$2A254B39-AFCB-488C-BE52-513D60C63699","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"12e3e9652f934c7e19471889c1a9038496516295","datavalue":{"value":{"entity-type":"item","numeric-id":260093,"id":"Q260093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$6D0CC356-8778-4083-A94F-4F948031F06B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3231911715c88eeda68ab5624fcc2c3ec367b8db","datavalue":{"value":{"time":"+2023-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2694797$98F0C64C-85C7-4C0A-9C1F-345430B4F6F5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"757e2948ea42f28a5b97065e4b8a3f92f5c8b6d2","datavalue":{"value":"https://arxiv.org/abs/2010.14299","type":"string"},"datatype":"url"},"type":"statement","id":"Q2694797$F7EAE3F6-2908-4B31-B6CC-3E8F55628F86","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2107f1e3ce7f2e0bf2a5d5cd7b67d6ddfd17d500","datavalue":{"value":"Summary: We introduce a notion of ``simulation'' for labelled graphs, in which edges of the simulated graph are realized by regular expressions in the simulating graph, and we prove that the tiling problem (a.k.a. the ``domino problem'') for the simulating graph is at least as difficult as that for the simulated graph. We apply this to the Cayley graph of the ``lamplighter group'' \\(L = \\mathbb{Z}/2 \\wr \\mathbb{Z}\\), and more generally to ``Diestel-Leader graphs''. We prove that these graphs simulate the plane, and thus deduce that the seeded tiling problem is unsolvable on the group \\(L\\). We note that \\(L\\) does not contain any plane in its Cayley graph, so our undecidability criterion by simulation covers cases not addressed by Jeandel's criterion based on translation-like action of a product of finitely generated infinite groups. Our approach to tiling problems is strongly based on categorical constructions in graph theory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2694797$895F72F1-4A6E-44CD-9509-8865D9AA636D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2694797$2319B351-46FF-4FA7-8D98-40EF74471068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2694797$CD0975D9-8601-41DD-B775-83D6227FB220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5320e9cecd9885a74d1f4cf20dd5b5397119f97a","datavalue":{"value":"20E22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2694797$E6CC31BF-A5F8-43C1-A8E5-A4153FBCAA6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"639e35a4d8066ba3b320b7c5998ad4d73a0cf431","datavalue":{"value":"20F65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2694797$78E390D4-CB4E-435E-9CA2-F93B67E187B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2694797$EA8C96A0-C0E5-433F-B71B-7CE096EC0A72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b559307b5b2969939e6945d65ee127220f8f6f4b","datavalue":{"value":"37B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2694797$D01E9639-7C56-4812-B83B-29F2BD2AF545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b9ca13b65dfaefefd0c02f3f6d7e1635431e9adc","datavalue":{"value":"37B50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2694797$5215154F-FBC7-42CB-AF1B-E9E11EB41143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2694797$FEC4A069-6F71-4803-891E-7CF4E80B8FFA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"84c9cf95dbd21298af2f3c080ac259d5cbddc157","datavalue":{"value":"7672035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2694797$6511665F-EAA7-4245-8F05-336B165A7C1A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"911096fc9b6d2408f27103b92b0fe8478008234f","datavalue":{"value":"lamplighter group","type":"string"},"datatype":"string"},"type":"statement","id":"Q2694797$D802452A-E539-461C-AF66-924167A6ED63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd11f43a07ad6333062fb5e371fa8685b96ae634","datavalue":{"value":"domino problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2694797$CC508305-41CA-4203-8095-3DC10D0E7277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bbf3dc675054850e9b5be83de978bdb3d3a0880","datavalue":{"value":"tiling problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2694797$4FEB7B35-5F5C-439E-A34A-87E3584BFD2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88131009e873277adebb4917fd6a91e2a43129ad","datavalue":{"value":"decision problems in group theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2694797$8E7FD4CA-395B-427C-AF47-0A547B19954F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8c8c8c4fdc9f91696962efc35a08827e231ad2b","datavalue":{"value":"wreath products","type":"string"},"datatype":"string"},"type":"statement","id":"Q2694797$F6327EA1-433D-437D-B581-682BE0759F00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef6bf87b39f48d6cf1f44860586c865978f7e54c","datavalue":{"value":"Diestel-Leader graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2694797$568D2593-14A8-4FE7-9FAC-987B18DEA6A5","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":"Q2694797$D3069B31-165A-4D7F-8B98-4437BFC0CD86","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2de11bb6b5c823ab19660a3e7685047e6a06e2d8","datavalue":{"value":{"entity-type":"item","numeric-id":4613553,"id":"Q4613553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$79178EF7-4946-45B9-8BBD-42FF0AE2A1E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1039ed762b1e92b791727152d2c81108254b3d93","datavalue":{"value":{"entity-type":"item","numeric-id":4992867,"id":"Q4992867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$79E706C0-17DB-4275-A650-171C0B0BDBBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e0183548b1bfe24b832b7686cf371fa6076466c","datavalue":{"value":{"entity-type":"item","numeric-id":1747808,"id":"Q1747808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$03BF7836-3031-4A63-AB48-58B3763874B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30c80746d51a17423200ea591c81b1b5b61e37cf","datavalue":{"value":{"entity-type":"item","numeric-id":936156,"id":"Q936156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$819AB2C8-5455-426E-9C5F-07621B77CD9D","rank":"normal"},{"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":"Q2694797$1606F048-870E-4769-B0A7-B0F27CE2C29D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7ff5cc1912f9ac83edc03a1abbb362742172ac2","datavalue":{"value":{"entity-type":"item","numeric-id":507216,"id":"Q507216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$6C428CCB-DF72-46B3-9099-5B1E087E4B77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d2f58bdfcefb97fd1756212d70ec568d829078c","datavalue":{"value":{"entity-type":"item","numeric-id":2035054,"id":"Q2035054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$B354F870-8B1C-41C7-B921-5B2FE7C9B8D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"947b9cde96c8544b72be5369514550c2b38207b1","datavalue":{"value":{"entity-type":"item","numeric-id":931861,"id":"Q931861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$F0320EE5-BD14-442D-8907-25FDA00FED8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f66a7fa980a7c5e67408cd5c4bddf13120002ed1","datavalue":{"value":{"entity-type":"item","numeric-id":5949012,"id":"Q5949012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$9B9FE375-17C4-4E18-99E2-0A8F8FE8C786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eda2db14c950cfacb2d9bab387b35d1aadfc67b0","datavalue":{"value":{"entity-type":"item","numeric-id":3284606,"id":"Q3284606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$90AAA441-99A2-4527-AD60-C2DCC772B7C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"280ade1b32e8c60a5983b1b9f0f1049f9968f47e","datavalue":{"value":{"entity-type":"item","numeric-id":1593473,"id":"Q1593473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$3215B1D2-46E6-4897-9860-4191B93DC88C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43536a0761a838d5cfd1688d59e4abc698504b50","datavalue":{"value":{"entity-type":"item","numeric-id":3942944,"id":"Q3942944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$193E865D-F23E-4F4A-B455-E143FF358424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8375e11ce45f9ec75069670248a6039513460faf","datavalue":{"value":{"entity-type":"item","numeric-id":2540183,"id":"Q2540183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$85BF4C1C-D2D6-4C90-A083-624BA0CE5357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d829593f64cbfedea58d5c79d1625f1c573dec1a","datavalue":{"value":{"entity-type":"item","numeric-id":2636582,"id":"Q2636582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$9F5B3A96-3614-40C9-94A0-0727E41B4F45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e647c4171c921616759b6afa736c0a4bf8d4f0ac","datavalue":{"value":{"entity-type":"item","numeric-id":1974941,"id":"Q1974941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$6DDFBC8D-5C10-495B-88AC-DE1D4712A3BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2dbfd91a2ebf5470f3a3e291171115d85e77c87","datavalue":{"value":{"entity-type":"item","numeric-id":4680575,"id":"Q4680575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2694797$E894341D-833D-4F10-9616-1641D536A1DE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0afb2554a7e6840db28a1c62f79e50f3268a2fec","datavalue":{"value":{"entity-type":"item","numeric-id":1960656,"id":"Q1960656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6adf1b74e19d0e7af9e5778a89360fcb53f7492c","datavalue":{"value":{"amount":"+0.7593107223510742","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":"Q2694797$1914860E-8E60-4E8B-8C84-066F6CA319DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd6a8ada25376c8c105cb6387016c098e2c8574c","datavalue":{"value":{"entity-type":"item","numeric-id":2243576,"id":"Q2243576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2694bfcad60d4809249053b8ac66ed9cc11c59bb","datavalue":{"value":{"amount":"+0.7275835871696472","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":"Q2694797$1A8FC53D-4D72-47A3-BC33-26A4D18BDD4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95006a3ee518d093132f294b0f7f9b1ece331f65","datavalue":{"value":{"entity-type":"item","numeric-id":4992867,"id":"Q4992867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b89afd88857a91bfa667df6f7543a7b1caad27a9","datavalue":{"value":{"amount":"+0.7264068126678467","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":"Q2694797$96C8FF99-E06E-473C-905A-73223BF95A86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"474e8c8ead90e75b1737af99b979ce3a870e04e7","datavalue":{"value":{"entity-type":"item","numeric-id":633769,"id":"Q633769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fadd93862506d3d7699355aba33c6e7c88fb9983","datavalue":{"value":{"amount":"+0.7246450185775757","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":"Q2694797$C1CB75E4-C604-4FD2-A35F-253EFB90307A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74477fbc8d19307e34a8a465d8dda6ade76bcc5a","datavalue":{"value":{"entity-type":"item","numeric-id":1603686,"id":"Q1603686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce41c6e8e6eeba10889b0cd1a558c0c2e46b3912","datavalue":{"value":{"amount":"+0.7206544280052185","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":"Q2694797$2C346C33-EB39-4B46-8D6C-A29248A4BACE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2694797","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2694797"}}}}}