@inproceedings{7c2730128e9e446598fff1d1ec39f44e,
title = "Undecidable word problem in subshift automorphism groups",
abstract = "This article studies the complexity of the word problem in groups of automorphisms (or reversible cellular automata) of subshifts. We show in particular that for any computably enumerable Turing degree, there exists a (two-dimensional) subshift of finite type whose automorphism group contains a subgroup whose word problem has exactly this degree. In particular, there are such subshifts of finite type where this problem is uncomputable. This remains true in a large setting of subshifts over groups.",
author = "Pierre Guillon and Emmanuel Jeandel and Jarkko Kari and Pascal Vanier",
note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 14th International Computer Science Symposium in Russia, CSR 2019 ; Conference date: 01-07-2019 Through 05-07-2019",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-19955-5\_16",
language = "English",
isbn = "9783030199548",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "180--190",
editor = "\{van Bevern\}, Ren{\'e} and Gregory Kucherov",
booktitle = "Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings",
}