The domino problem is undecidable on surface groups

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.

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-11
Main Authors: Aubrun, Nathalie, Barbieri, Sebastián, Moutot, Etienne
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1811.08420