Top

Published in:

2020 | OriginalPaper | Chapter

On Decision Problems for Substitutions in Symbolic Dynamics

Author : Valérie Berthé

Published in: Reachability Problems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this survey, we discuss decidability issues for symbolic dynamical systems generated by substitutions. Symbolic dynamical systems are discrete dynamical systems made of infinite sequences of symbols, with the shift acting on them. Substitutions are simple rules that replace letters by string of letters and allow the generation of infinite words. We focus here on symbolic dynamical systems that are generated by infinite compositions of substitutions, allowing to go beyond the case of the iteration of a single substitution. This is the so-called S-adic framework. Motivated by decidability and ergodic questions, we focus on questions dealing with the convergence of products of nonnegative matrices and associated Lyapunov exponents.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Games with Full, Longitudinal, and Transverse Observability

Here \(\mu \)-almost everywhere refers to directive sequences of substitutions chosen in D with respect to the measure \(\mu \).

Adamczewski, B.: Symbolic discrepancy and self-similar dynamics. Ann. Inst. Fourier (Grenoble) 54, 2201–2234 (2004)MathSciNetCrossRef

Akiyama, S., Barge, M., Berthé, V., Lee, J.-Y., Siegel, A.: On the Pisot substitution conjecture. In: Kellendonk, J., Lenz, D., Savinien, J. (eds.) Mathematics of Aperiodic Order. PM, vol. 309, pp. 33–72. Springer, Basel (2015). https://doi.org/10.1007/978-3-0348-0903-0_2CrossRef

Aubrun, N., Sablik, M.: Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta Applicandae Mathematicae 126, 35–63 (2013)MathSciNetCrossRef

Avila, A., Forni, G.: Weak mixing for interval exchange transformations and translation flows. Ann. Math. 165, 637–664 (2007)MathSciNetCrossRef

Baake, M., Grimm, U.: Aperiodic order. Volume 1: A Mathematical invitation. Cambridge University Press, Cambridge (2013)

Bell, J.P., Charlier, E., Fraenkel, A.S., Rigo, M.: A decision problem for ultimately periodic sets in non-standard numeration systems. Int. J. Algebra Comput. 9, 809–839 (2009)CrossRef

Berger, R: The undecidability of the domino problem. Mem. Am. Math. Soc. 66 (1966)

Berthé, V., Delecroix, V.: Beyond substitutive dynamical systems: S-adic expansions. RIMS Lecture note ‘Kokyuroku Bessatu’ B46, 81–123 (2004)

Berthé, V., Rigo, M. (eds.): Combinatorics, Automata and Number Theory. Encyclopedia of Mathematics and its Applications, vol. 135. Cambridge University Press, Cambridge (2010)

10.

Berthé, V., Rigo, M. (eds.): Combinatorics, Words and Symbolic dynamics. Encyclopedia of Mathematics and its Applications, vol. 159, Cambridge University Press (2016)

11.

Berthé, V., Fernique, T., Sablik, M.: Effective S-adic symbolic dynamical systems. In: Beckmann, A., Bienvenu, L., Jonoska, N. (eds.) CiE 2016. LNCS, vol. 9709, pp. 13–23. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40189-8_2CrossRef

12.

Berthé, V., Steiner, W., Thuswaldner, J.: Geometry, dynamics, and arithmetic of \(s\)-adic shifts. Annales de l’Institut Fourier 69, 1347–1409 (2019)MathSciNetCrossRef

13.

Berthé, V., Steiner, W., Thuswaldner, J.: On the strong convergence of higher-dimensional continuous fractions. Math. Comput. (to appear)

14.

Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and \(p\)-recognizable sets of integers. Bull. Belg. Math. Soc. Simon Stevin 1(2), 191–238 (1994)MathSciNetCrossRef

15.

Charlier, E., Rampersad, N., Shallit, J.: Enumeration and decidable properties of automatic sequences. Int. J. Found. Comput. Sci. 23, 1035–1066 (2012)MathSciNetCrossRef

16.

Durand, F.: Linearly recurrent subshifts have a finite number of non-periodic subshift factors. Ergod. Theory Dyn. Syst. 20, 1061–1078 (2000). Corrigendum and addendum. Ergodic Theory Dynam. Systems, 23 663–669 (2003)MathSciNetCrossRef

17.

Durand, F.: HD0L \(\omega \)-equivalence and periodicity problems in the primitive case. Unif. Distrib. Theory 7, 199–215 (2012)MathSciNetMATH

18.

Durand, F.: Decidability of the HD0L ultimate periodicity problem. RAIRO Theor. Inform. Appl. 47, 201–214 (2013)MathSciNetCrossRef

19.

Durand, F.: Decidability of uniform recurrence of morphic sequences. Int. J. Found. Comput. Sci. 24, 123–146 (2013)MathSciNetCrossRef

20.

Durand, F., Leroy. J.: Decidability of the isomorphism and the factorization between minimal substitution subshifts. https://arxiv.org/abs/1806.04891

21.

Durand, B., Romashchenko, A., Shen, A.: Effective closed subshifts in 1D can be implemented in 2D. In: Blass, A., Dershowitz, N., Reisig, W. (eds.) Fields of Logic and Computation. LNCS, vol. 6300, pp. 208–226. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15025-8_12CrossRef

22.

Fijalkow, N., Ohlmann, P., Ouaknine, J., Pouly, A., Worrell, J.: Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem. Theor. Comput. Sci. 63, 1027–1048 (2019)MathSciNetMATH

23.

Furstenberg, H.: Stationary Processes and Prediction Theory. Annals of Mathematics Studies, vol. 44, Princeton University Press, Princeton (1960)

24.

Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones Mathematicae 176, 131–167 (2009)MathSciNetCrossRef

25.

Hochman, M., Meyerovitch, T.: A characterization of the entropies of multidimensional shifts of finite type. Ann. Math. 171, 2011–2038 (2010)MathSciNetCrossRef

26.

Jeandel, E., Vanier, P.: A characterization of subshifts with computable language. In: STACS Art. No. 40, LIPIcs. Leibniz International Proceedings in Informatics, 126, Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern (2019)

27.

Kannan, R., Lipton, R.J.: Polynomial-time algorithm for the orbit problem. J. Assoc. Comput. Mach. 33(4), 808–821 (1986)MathSciNetCrossRef

28.

Keane, M.: Non-ergodic interval exchange transformations. Israel J. Math. 26, 188–196 (1977)MathSciNetCrossRef

29.

Lagarias, J.C.: The quality of the Diophantine approximations found by the Jacobi-Perron algorithm and related algorithms. Monatsh. Math. 115, 299–328 (1993)MathSciNetCrossRef

30.

Lhote, L.: Computation of a class of continued fraction constants. In: Analytic Algorithmic and Combinatorics ANALCO 2014, pp. 199–210. SIAM (2004)

31.

Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol. 90. Cambridge University Press, Cambridge (2002)CrossRef

32.

Morse, M., Hedlund, G.A.: Symbolic dynamics II. Sturmian Trajectories Am. J. Math. 62, 1–42 (1940)MathSciNetCrossRef

33.

Pollicott, M.: Maximal Lyapunov exponents for random matrix products. Invent. Math. 181, 209–226 (2010)MathSciNetCrossRef

34.

Priebe Frank, N., Sadun, L.: Fusion: a general framework for hierarchical tilings of \(\mathbb{R}^d\). Geometriae Dedicata 171, 149–186 (2014)MathSciNetCrossRef

35.

Pytheas, N.: Substitutions in dynamics, arithmetics and combinatorics. In: Berthé, V., Ferenczi, S., Mauduit, C., Siegel, A. (eds.) Lecture Notes in Mathematics, vol. 1794. Springer, Heidelberg (2002)

36.

Queffélec, M.: Substitution Dynamical Systems—Spectral Analysis. Lecture Notes in Mathematics, vol. 1294, 2nd edn. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-11212-6CrossRefMATH

37.

Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12, 177–209 (1971)MathSciNetCrossRef

38.

Schweiger, F.: Multidimensional Continued Fractions. Oxford Science Publications, Oxford University Press, Oxford (2000)MATH

39.

Seneta, E.: Non-Negative Matrices and Markov Chains. Springer Series in Statistics. Springer, New York (1981)CrossRef

40.

Siegel, A. Thuswaldner, J.M.: Topological properties of Rauzy fractals. Mém. Soc. Math. Fr. 118 (2009)

41.

Shallit, J.: Decidability and enumeration for automatic sequences: a survey. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 49–63. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38536-0_5CrossRefMATH

42.

Tsitsiklis, J.N., Blondel, J.N.: The Lyapunov exponent and joint spectral radius of pairs of matrices are hard—when not impossible—to compute and to approximate. Math. Control. Signals Syst. 10, 31–40 (1997)MathSciNetCrossRef

43.

Yoccoz, J.-C.: Continued fraction algorithms for interval exchange maps: an introduction. In: Frontiers in Number Theory, Physics, and Geometry I, pp. 401–435. Springer, Berlin (2006)

44.

Zorich, A.: Deviation for interval exchange transformations. Ergod. Theory Dyn. Syst. 17, 1477–1499 (1997)MathSciNetCrossRef

Title: On Decision Problems for Substitutions in Symbolic Dynamics
Author: Valérie Berthé
Publisher: Springer International Publishing
Book: Reachability Problems
Print ISBN: 978-3-030-61738-7

Electronic ISBN: 978-3-030-61739-4

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-61739-4_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner