2024/09/22 by Bartholdi, Laurent, Salo, Ville
#Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #Logic (math.LO) #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2409.14525
We construct a finitely generated group which is not virtually free, yet has decidable snake tiling problem. This shows that either a long-standing conjecture by Ballier and Stein (the characterization of groups with decidable domino problem as those virtually free ones) is false, or a question by Aubrun and Bitar has a positive answer (there exists a group for which the domino and snake problems are of different difficulty).