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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We could deal in the same way with semigroups, by prohibiting the empty word.
References
Aubrun, N., Béal, M.-P.: Decidability of conjugacy of tree-shifts of finite type. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 132–143. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02927-1_13
Comon, H., et al.: Tree automata techniques and applications (2007). http://www.grappa.univ-lille3.fr/tata. Accessed 12 Oct 2007
Thomas, W.: Automata on infinite objects. In: van Leeuwen, J. (ed.) Formal Models and Semantics, Handbook of Theoretical Computer Science, pp. 133–191. Elsevier, Amsterdam (1990)
Boyle, M., Lind, D.A., Rudolph, D.J.: The automorphism group of a shift of finite type. Trans. Am. Math. Soc. 306(1), 71–114 (1988)
Kari, J., Ollinger, N.: Periodicity and immortality in reversible computing. In: Ochmański, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 419–430. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85238-4_34
Coven, E., Yassawi, R.: Endomorphisms and automorphisms of minimal symbolic systems with sublinear complexity (2014)
Cyr, V., Kra, B.: The automorphism group of a shift of linear growth: beyond transitivity (2014)
Donoso, S., Durand, F., Maass, A., Petite, S.: On automorphism groups of low complexity subshifts (2015)
Hochman, M.: Groups of automorphisms of SFTs. Open problems (2017). http://math.huji.ac.il/~mhochman/problems/automorphisms.pdf
Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987)
Rabin, M.O.: Computable algebra, general theory and theory of computable fields. Trans. Am. Math. Soc. 95, 341–360 (1960)
Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory 3, 320–375 (1969)
Kari, J.: Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48(1), 149–182 (1994)
Aubrun, N., Barbieri, S., Sablik, M.: A notion of effectiveness for subshifts on finitely generated groups. Theor. Comput. Sci. 661, 35–55 (2017)
Boykett, T., Kari, J., Salo, V.: Finite generating sets for reversible gate sets under general conservation laws. Theor. Comput. Sci. 701, 27–39 (2017)
Simpson, S.G.: Medvedev degrees of 2-dimensional subshifts of finite type. Ergodic Theory Dyn. Syst. 34(November 2012), 665–674 (2014)
Hanf, W., Myers, D.: Non recursive tilings of the plane II. J. Symbolic Logic 39(2), 286–294 (1974)
Acknowledgements
This research was supported by the Academy of Finland grant 296018.
We thank Ville Salo for some discussions on commutators, on the open questions, and for a careful reading of this preprint.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Guillon, P., Jeandel, E., Kari, J., Vanier, P. (2019). Undecidable Word Problem in Subshift Automorphism Groups. In: van Bevern, R., Kucherov, G. (eds) Computer Science – Theory and Applications. CSR 2019. Lecture Notes in Computer Science(), vol 11532. Springer, Cham. https://doi.org/10.1007/978-3-030-19955-5_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-19955-5_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-19954-8
Online ISBN: 978-3-030-19955-5
eBook Packages: Computer ScienceComputer Science (R0)