A1 Journal article – refereed

On the domino problem of the Baumslag-Solitar groups

List of Authors: Aubrun Nathalie, Kari Jarkko

Publisher: Elsevier B.V.

Publication year: 2021

Journal: Theoretical Computer Science

Journal name in source: Theoretical Computer Science

ISSN: 0304-3975

eISSN: 1879-2294

DOI: http://dx.doi.org/10.1016/j.tcs.2021.09.002

URL: https://www.sciencedirect.com/science/article/pii/S030439752100517X


In [1] we construct aperiodic tile sets on the Baumslag-Solitar groups BS(m, n). Aperiodicity plays a central role in the undecidability of the classical domino problem on Z2, and analogously to this we state as a corollary of the main construction that the Domino problem is undecidable on all Baumslag-Solitar groups. In the present work we elaborate on the claim and provide a full proof of this fact. We also provide details of another result reported in [1]: there are tiles that tile the Baumslag-Solitar group BS(m, n)but none of the valid tilings is recursive. The proofs are based on simulating piecewise affine functions by tiles on BS(m, n).

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.

Last updated on 2021-18-10 at 11:51