Hostname: page-component-669899f699-7tmb6 Total loading time: 0 Render date: 2025-04-25T12:55:16.666Z Has data issue: false hasContentIssue false
  • English
  • Français

Decidability of the isomorphism problem between multidimensional substitutive subshifts

Part of: Discrete mathematics in relation to computer science Topological dynamics Ergodic theory

Published online by Cambridge University Press:  19 November 2024

CHRISTOPHER CABEZAS Open the ORCID record for CHRISTOPHER CABEZAS [Opens in a new window]  and
JULIEN LEROY Open the ORCID record for JULIEN LEROY [Opens in a new window]
CHRISTOPHER CABEZAS*
Affiliation:
Department of Mathematics, University of Liège, Allée de la découverte 12 (B37), B-4000 Liège, Belgium (e-mail: [email protected])
JULIEN LEROY
Affiliation:
Department of Mathematics, University of Liège, Allée de la découverte 12 (B37), B-4000 Liège, Belgium (e-mail: [email protected])
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

An important question in dynamical systems is the classification problem, that is, the ability to distinguish between two isomorphic systems. In this work, we study the topological factors between a family of multidimensional substitutive subshifts generated by morphisms with uniform support. We prove that it is decidable to check whether two minimal aperiodic substitutive subshifts are isomorphic. The strategy followed in this work consists of giving a complete description of the factor maps between these subshifts. Then, we deduce some interesting consequences on coalescence, automorphism groups, and the number of aperiodic symbolic factors of substitutive subshifts. We also prove other combinatorial results on these substitutions, such as the decidability of defining a subshift, the computability of the constant of recognizability, and the conjugacy between substitutions with different supports.

Keywords

substitutive subshiftsautomomorphism groupsdecidabilitycomputabilityconjugaciesfactor mapsrecognizabilityFølner sequences

MSC classification

Primary: 37B10: Symbolic dynamics
Secondary: 37A35: Entropy and other invariants, isomorphism, classification 68R15: Combinatorics on words
Type
Original Article
Information
Ergodic Theory and Dynamical Systems , First View , pp. 1 - 41
Check for updates
Copyright
© The Author(s), 2024. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Adamczewski, B. and Bugeaud, Y.. On the complexity of algebraic numbers. I. Expansions in integer bases. Ann. of Math. (2) 165(2) (2007), 547–565.CrossRefGoogle Scholar
Allouche, J.-P. and Shallit, J.. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003.CrossRefGoogle Scholar
Baake, M. and Grimm, U.. Aperiodic Order: A Mathematical Invitation. Volume 1 (Encyclopedia of Mathematics and its Applications, 149). Cambridge University Press, Cambridge, 2013; with a foreword by R. Penrose.CrossRefGoogle Scholar
Béal, M.-P., Perrin, D. and Restivo, A.. Recognizability of morphisms. Ergod. Th. & Dynam. Sys. 43(11) (2023), 3578–3602.CrossRefGoogle Scholar
Bezuglyi, S., Kwiatkowski, J. and Medynets, K.. Aperiodic substitution systems and their Bratteli diagrams. Ergod. Th. & Dynam. Sys. 29(1) (2009), 37–72.CrossRefGoogle Scholar
Blanchard, F., Durand, F. and Maass, A.. Constant-length substitutions and countable scrambled sets. Nonlinearity 17(3) (2004), 817–833.CrossRefGoogle Scholar
Büchi, J. R.. Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6 (1960), 66–92.CrossRefGoogle Scholar
Cabezas, C.. Homomorphisms between multidimensional constant-shape substitutions. Groups Geom. Dyn. 17(4) (2023), 1259–1323.CrossRefGoogle Scholar
Cobham, A.. On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3 (1969), 186–192.CrossRefGoogle Scholar
Cobham, A.. Uniform tag sequences. Math. Systems Theory 6 (1972), 164–192.CrossRefGoogle Scholar
Cortez, M. I., Durand, F. and Petite, S.. Linearly repetitive Delone systems have a finite number of nonperiodic Delone system factors. Proc. Amer. Math. Soc. 138(3) (2010), 1033–1046.CrossRefGoogle Scholar
Coven, E. M., Quas, A. and Yassawi, R.. Computing automorphism groups of shifts using atypical equivalence classes. Discrete Anal. 2016(3) (2016), Paper no. 3.Google Scholar
Cyr, V. and Kra, B.. The automorphism group of a shift of linear growth: beyond transitivity. Forum Math. Sigma 3 (2015), Paper no. e5.CrossRefGoogle Scholar
Dekking, F. M.. The spectrum of dynamical systems arising from substitutions of constant length. Z. Wahrscheinlichkeitstheorie Verw. Gebiete 41(3) (1977/78), 221–239.CrossRefGoogle Scholar
Donoso, S., Durand, F., Maass, A. and Petite, S.. On automorphism groups of low complexity subshifts. Ergod. Th. & Dynam. Sys. 36(1) (2016), 64–95.CrossRefGoogle Scholar
Durand, F.. Linearly recurrent subshifts have a finite number of non-periodic subshift factors. Ergod. Th. & Dynam. Sys. 20(4) (2000), 1061–1078.CrossRefGoogle Scholar
Durand, F.. Cobham–Semenov theorem and ${\mathbb{N}}^d$ -subshifts. Theoret. Comput. Sci. 391(1–2) (2008), 20–38.CrossRefGoogle Scholar
Durand, F., Host, B. and Skau, C.. Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergod. Th. & Dynam. Sys. 19(4) (1999), 953–993.CrossRefGoogle Scholar
Durand, F. and Leroy, J.. The constant of recognizability is computable for primitive morphisms. J. Integer Seq. 20(4) (2017), Article no. 17.4.5.Google Scholar
Durand, F. and Leroy, J.. Decidability of isomorphism and factorization between minimal substitution subshifts. Discrete Anal. 7 (2022), 65pp.Google Scholar
Ehrenfeucht, A. and Rozenberg, G.. Simplifications of homomorphisms. Inform. Control 38(3) (1978), 298–309.CrossRefGoogle Scholar
Fagnot, I.. Sur les facteurs des mots automatiques. Theoret. Comput. Sci. 172(1–2) (1997), 67–89.CrossRefGoogle Scholar
Fogg, N. P.. Substitutions in Dynamics, Arithmetics and Combinatorics (Lecture Notes in Mathematics, 1794). Ed. V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. Springer-Verlag, Berlin, 2002.CrossRefGoogle Scholar
Fogg, N. P.. Substitutions par des motifs en dimension 1. Theor. Inform. Appl. 41(3) (2007), 267–284.CrossRefGoogle Scholar
Frank, N. P. and Mañibo, N.. Spectral theory of spin substitutions. Discrete Contin. Dyn. Syst. 42(11) (2022), 5399–5435.CrossRefGoogle Scholar
Frankl, P.. An extremal problem for two families of sets. European J. Combin. 3(2) (1982), 125–127.CrossRefGoogle Scholar
Gottschalk, W. H.. Substitution minimal sets. Trans. Amer. Math. Soc. 109 (1963), 467–491.CrossRefGoogle Scholar
Hansen, C. W.. Dynamics of multidimensional substitutions. PhD Thesis, The George Washington University, ProQuest LLC, Ann Arbor, MI, 2000.Google Scholar
Hedlund, G. A.. Endomorphisms and automorphisms of the shift dynamical system. Math. Systems Theory 3 (1969), 320–375.CrossRefGoogle Scholar
Host, B. and Parreau, F.. Homomorphismes entre systèmes dynamiques définis par substitutions. Ergod. Th. & Dynam. Sys. 9(3) (1989), 469–477.CrossRefGoogle Scholar
Kim, K. H. and Roush, F. W.. The Williams conjecture is false for irreducible subshifts. Ann. of Math. (2) 149(2) (1999), 545–558.CrossRefGoogle Scholar
Lee, J.-Y., Moody, R. V. and Solomyak, B.. Consequences of pure point diffraction spectra for multiset substitution systems. Discrete Comput. Geom. 29(4) (2003), 525–560.CrossRefGoogle Scholar
Lemańczyk, M. and Mentzen, M. K.. On metric properties of substitutions. Compos. Math. 65(3) (1988), 241–263.Google Scholar
Mossé, B.. Puissances de mots et reconnaissabilité des points fixes d’une substitution. Theoret. Comput. Sci. 99(2) (1992), 327–334.CrossRefGoogle Scholar
Mozes, S.. Tilings, substitution systems and dynamical systems generated by them. J. Anal. Math. 53 (1989), 139–186.CrossRefGoogle Scholar
Nekrashevych, V.. Palindromic subshifts and simple periodic groups of intermediate growth. Ann. of Math. (2) 187(3) (2018), 667–719.CrossRefGoogle Scholar
Penrose, R.. The role of aesthetics in pure and applied mathematical research. Bull. Inst. Math. Appl. 10 (1974), 266–271.Google Scholar
Pin, J.-E.. On two combinatorial problems arising from automata theory. Combinatorial Mathematics (Marseille-Luminy, 1981) (North-Holland Mathematics Studies, 75). Ed. Berge, C. et al. North-Holland, Amsterdam, 1983, pp. 535–548.Google Scholar
Queffélec, M.. Substitution Dynamical Systems—Spectral Analysis (Lecture Notes in Mathematics, 1294), 2nd edn. Springer-Verlag, Berlin, 2010.CrossRefGoogle Scholar
Robinson, E. A. Jr. Symbolic dynamics and tilings of ${\mathbb{R}}^d$ . Symbolic Dynamics and its Applications (Proceedings of Symposia in Applied Mathematics, 60). American Mathematical Society, Providence, RI, 2004, pp. 81–119.CrossRefGoogle Scholar
Salo, V. and Törmä, I.. Block maps between primitive uniform and Pisot substitutions. Ergod. Th. & Dynam. Sys. 35(7) (2015), 2292–2310.CrossRefGoogle Scholar
Siegel, A.. Spectral theory for dynamical systems arising from substitutions. European Women in Mathematics—Marseille 2003 (CWI Tract, 135). Centrum Wiskunde & Informatica, Amsterdam, 2005, pp. 11–26.Google Scholar
Solomyak, B.. Nonperiodicity implies unique composition for self-similar translationally finite tilings. Discrete Comput. Geom. 20(2) (1998), 265–279.CrossRefGoogle Scholar
Volkov, M. V.. Synchronizing automata and the Černý conjecture. Language and Automata Theory and Applications. Ed. Martín-Vide, C., Otto, F. and Fernau, H.. Springer, Berlin, 2008, pp. 11–27.CrossRefGoogle Scholar
Weiss, B.. Monotileable amenable groups. Topology, Ergodic Theory, Real Algebraic Geometry (AMS American Mathematical Society Translations: Series 2, 202). American Mathematical Society, Providence, RI, 2001, pp. 257–262.Google Scholar
Wielandt, H.. Unzerlegbare, nicht negative Matrizen. Math. Z. 52 (1950), 642–648.CrossRefGoogle Scholar
Williams, R. F.. Classification of subshifts of finite type. Ann. of Math. (2) 98 (1973), 120–153; errata, ibid. 99(2) (1974), 380–381.CrossRefGoogle Scholar