Undecidable word problem in subshift automorphism groups

DOI10.1007/978-3-030-19955-5_16MaRDI QIDQ6305892arXivFDO

Authors Pierre Guillon, Emmanuel Jeandel, Jarkko Kari, Pascal Vanier

Publication date 28 August 2018

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-19955-5_16

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

arXiv classification

cs.CCmath.DSmath.GR

Abstract: This article studies the complexity of the word problem in groups of automorphisms of subshifts. We show in particular that for any Turing degree, there exists a subshift whose automorphism group contains a subgroup whose word problem has exactly this degree.

This page was built for publication: Undecidable word problem in subshift automorphism groups

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