论文标题
模拟和灯塔组
Simulations and the Lamplighter group
论文作者
论文摘要
我们为标记的图引入了一个“模拟”概念，其中模拟图中的正则表达式实现了模拟图的边缘，并证明模拟图的平铺问题（又称“ domino问题”）至少与模拟图一样困难。 我们将其应用于“ Lamplighter Group”的Cayley图，$ L = \ Mathbb Z/2 \ WR \ Mathbb Z $，更普遍地用于“ Diestel-Leader Graphs”。我们证明这些图形模拟了飞机，因此推断出种子铺平的问题在组$ l $上是无法解决的。 我们注意到，$ L $在其Cayley图中不包含任何平面，因此我们的模拟不确定性标准涵盖了Jeandel标准未涵盖的案例，基于有限生成的无限基团的类似于翻译的动作。 我们解决问题问题的方法基于图理论中的分类结构。
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 prove that the tiling problem (aka "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 covered 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.
