Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.46
URN: urn:nbn:de:0030-drops-109900
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10990/
Aubrun, Nathalie ; Barbieri, Sebastián ; Moutot, Etienne
The Domino Problem is Undecidable on Surface Groups
| pdf-format: |
|
Abstract
We show that the domino problem is undecidable on orbit graphs of non-deterministic substitutions which satisfy a technical property. As an application, we prove that the domino problem is undecidable for the fundamental group of any closed orientable surface of genus at least 2.
BibTeX - Entry
@InProceedings{aubrun_et_al:LIPIcs:2019:10990,
author = {Nathalie Aubrun and Sebasti{\'a}n Barbieri and Etienne Moutot},
title = {{The Domino Problem is Undecidable on Surface Groups}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {46:1--46:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-117-7},
ISSN = {1868-8969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10990},
URN = {urn:nbn:de:0030-drops-109900},
doi = {10.4230/LIPIcs.MFCS.2019.46},
annote = {Keywords: tilings, substitutions, SFTs, decidability, domino problem}
}
| Keywords: | tilings, substitutions, SFTs, decidability, domino problem | |
| Seminar: | 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 20.08.2019 |
