A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Undecidable word problem in subshift automorphism groups
Tekijät: Guillon P., Jeandel E., Kari J., Vanier P.
Toimittaja: van Bevern R., Kucherov G.
Konferenssin vakiintunut nimi: International Computer Science Symposium in Russia
Kustantaja: Springer Verlag
Julkaisuvuosi: 2019
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Computer Science – Theory and Applications. CSR 2019
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 11532
Aloitussivu: 180
Lopetussivu: 190
ISBN: 978-3-030-19954-8
eISBN: 978-3-030-19955-5
DOI: https://doi.org/10.1007/978-3-030-19955-5_16
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/42007423
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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
