@inproceedings{10af132ed5a44b99b43a40c4ddb3e426,
title = "Domino Snake Problems on Groups",
abstract = "In this article we study domino snake problems on finitely generated groups. We provide general properties of these problems and introduce new tools for their study. The first is the use of symbolic dynamics to understand the set of all possible snakes. Using this approach we solve many variations of the infinite snake problem including the geodesic snake problem for certain classes of groups. Next, we introduce a notion of embedding that allows us to reduce the decidability of snake problems from one group to another. This notion enable us to establish the undecidability of the infinite snake and ouroboros problems on nilpotent groups for any generating set, given that we add a well-chosen element. Finally, we make use of monadic second order logic to prove that domino snake problems are decidable on virtually free groups for all generating sets.",
keywords = "Combinatorial Group Theory, Computability Theory, Domino Snake Problems, MSO logic, Symbolic Dynamics",
author = "Nathalie Aubrun and Nicolas Bitar",
note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 24th International Symposium on Fundamentals of Computation Theory, FCT 2023 ; Conference date: 18-09-2023 Through 21-09-2023",
year = "2023",
month = jan,
day = "1",
doi = "10.1007/978-3-031-43587-4\_4",
language = "English",
isbn = "9783031435867",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "46--59",
editor = "Henning Fernau and Klaus Jansen",
booktitle = "Fundamentals of Computation Theory - 24th International Symposium, FCT 2023, Proceedings",
}