The domino problem is undecidable on surface groups

DOI10.4230/LIPICS.MFCS.2019.46MaRDI QIDQ5092408zbMATH OpenFDO

Authors Nathalie Aubrun, Sebastián Barbieri, Etienne Moutot

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1811.08420

zbMATH Keywords

decidabilitydomino problemSFTssubstitutionstilings

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Groups and tilings
• The domino problem on groups of polynomial growth
• The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane
• The undecidability of the domino problem
• On the domino problem of the Baumslag-Solitar groups

Cites work

• A hierarchical strongly aperiodic set of tiles in the hyperbolic plane
• An Introduction to Symbolic Dynamics and Coding
• Cut points and canonical splittings of hyperbolic groups
• Finite and infinite cyclic extensions of free groups
• From Groups to Geometry and Back
• Logical aspects of Cayley-graphs: the group case
• On the Undecidability of the Tiling Problem
• Sequences, groups, and number theory
• Strongly aperiodic subshifts on surface groups
• The accessibility of finitely presented groups
• The domino problem for self-similar structures
• The domino problem of the hyperbolic plane is undecidable
• The domino problem on groups of polynomial growth
• The large scale geometry of strongly aperiodic subshifts of finite type
• The theory of ends, pushdown automata, and second-order logic
• The undecidability of the domino problem
• Tiling problems on Baumslag-Solitar groups.
• Tilings robust to errors
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(13)

• Necessary conditions for tiling finitely generated amenable groups
• Aperiodic SFTs on Baumslag-Solitar groups
• Decidability of irreducible tree shifts of finite type
• Monadic second-order logic and the domino problem on self-similar graphs
• Strongly aperiodic subshifts of finite type on hyperbolic groups
• Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type
• The domino problem is undecidable on surface groups
• The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem
• FO logic on cellular automata orbits equals MSO logic
• On a Rice theorem for dynamical properties of SFTs on groups
• The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem (extended abstract)
• A general framework for quasi-isometries in symbolic dynamics beyond groups
• The domino problem of the hyperbolic plane is undecidable

This page was built for publication: The domino problem is undecidable on surface groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092408)