Monadic second-order logic and the domino problem on self-similar graphs

DOI10.4171/GGD/689MaRDI QIDQ2694796

Laurent Bartholdi

Publication date: 4 April 2023

Published in: Groups, Geometry, and Dynamics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.02735

zbMATH Keywords

monadic second-order logicWang tilesself-similar graphs

Mathematics Subject Classification ID

Geometric group theory (20F65) Undecidability and degrees of sets of sentences (03D35) Groups acting on trees (20E08) Infinite graphs (05C63)

Cites Work

• Unnamed Item
• Unnamed Item
• Growth of Schreier graphs of automaton groups.
• The structure of the models of decidable monadic theories of graphs
• The domino problem of the hyperbolic plane is undecidable
• Schreier graphs of the Basilica group.
• The theory of ends, pushdown automata, and second-order logic
• Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity.
• Amenability of linear-activity automaton groups
• Asymptotic aspects of Schreier graphs and Hanoi Towers groups.
• \(\omega\)-periodic graphs
• Simulations and the lamplighter group
• The Domino Problem for Self-similar Structures
• The Tiling Problem Revisited (Extended Abstract)
• Harmonic Calculus on P.C.F. Self-Similar Sets
• On the Undecidability of the Tiling Problem
• The undecidability of the domino problem

This page was built for publication: Monadic second-order logic and the domino problem on self-similar graphs