Snakes can be fooled into thinking they live in a tree
<|reference_start|>Snakes can be fooled into thinking they live in a tree: 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).<|reference_end|>
@article{bartholdi2024snakes,
    title={Snakes can be fooled into thinking they live in a tree},
    author={Laurent Bartholdi, Ville Salo},
    journal={arXiv preprint arXiv:2409.14525},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.14525},
    primaryClass={math.GR cs.LO math.DS math.LO}
}