论文标题
自相似图上的Monadic二阶逻辑和Domino问题
Monadic second-order logic and the domino problem on self-similar graphs
论文作者
论文摘要
我们在自相似群体的Schreier图上以及更普遍的其Monadic二阶逻辑上考虑了多米诺骨牌问题。一方面，我们证明，如果组有界限，则该图的Monadic二阶逻辑是可决定的。例如，这涵盖了Sierpiński垫圈图和大教堂组的Schreier图。另一方面，对于一类自相似群体，我们已经证明了多米诺骨牌问题的不确定性，回答了Barbieri和Sablik的一个问题，以及包括线性增长之一在内的一些示例。
We consider the domino problem on Schreier graphs of self-similar groups, and more generally their monadic second-order logic. On the one hand, we prove that if the group is bounded then the graph's monadic second-order logic is decidable. This covers, for example, the Sierpiński gasket graphs and the Schreier graphs of the Basilica group. On the other hand, we already prove undecidability of the domino problem for a class of self-similar groups, answering a question by Barbieri and Sablik, and some examples including one of linear growth.
