Snakes can be fooled into thinking they live in a tree
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916406181756928 |
|---|---|
| author | Bartholdi, Laurent Salo, Ville |
| author_facet | Bartholdi, Laurent Salo, Ville |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14525 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Snakes can be fooled into thinking they live in a tree Bartholdi, Laurent Salo, Ville Group Theory Logic in Computer Science Dynamical Systems Logic 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). |
| title | Snakes can be fooled into thinking they live in a tree |
| topic | Group Theory Logic in Computer Science Dynamical Systems Logic |
| url | https://arxiv.org/abs/2409.14525 |