Allouche, Jean-Paul; Rampersad, Narad; Shallit, Jeffrey Periodicity, repetitions, and orbits of an automatic sequence. (English) Zbl 1173.68044 Theor. Comput. Sci. 410, No. 30-32, 2795-2803 (2009). Summary: We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidable whether a given \(k\)-automatic sequence is ultimately periodic. We prove that it is decidable whether a given \(k\)-automatic sequence is overlap-free (or squarefree, or cubefree, etc.). We prove that the lexicographically least sequence in the orbit closure of a \(k\)-automatic sequence is \(k\)-automatic, and use this last result to show that several related quantities, such as the critical exponent, irrationality measure, and recurrence quotient for Sturmian words with slope \(\alpha \), have automatic continued fraction expansions if \(\alpha \) does. Cited in 2 ReviewsCited in 24 Documents MSC: 68R15 Combinatorics on words 11A55 Continued fractions 11B85 Automata sequences 11U05 Decidability (number-theoretic aspects) Keywords:automatic sequence; squarefree; overlap-free; Thue-Morse sequence; Rudin-Shapiro sequence; decidability; periodicity; orbit; orbit closure; continued fraction Software:Grail PDFBibTeX XMLCite \textit{J.-P. Allouche} et al., Theor. Comput. Sci. 410, No. 30--32, 2795--2803 (2009; Zbl 1173.68044) Full Text: DOI References: [1] Adamczewski, B.; Allouche, J.-P., Reversals and palindromes in continued fractions, Theoret. Comput. Sci., 380, 220-237 (2007) · Zbl 1118.68110 [2] J.-P. Allouche, Théorie des Nombres et Automates, Thèse d’État, 1983. Text available electronically at http://tel.archives-ouvertes.fr/tel-00343206/fr/; J.-P. Allouche, Théorie des Nombres et Automates, Thèse d’État, 1983. Text available electronically at http://tel.archives-ouvertes.fr/tel-00343206/fr/ [3] Allouche, J.-P.; Cosnard, M., Itérations de fonctions unimodales et suites engendrées par automates, C. R. Acad. Sci. Paris, 296, 159-162 (1983) · Zbl 0547.58027 [4] Allouche, J.-P.; Cosnard, M., Non-integer bases, iteration of continuous real maps, and an arithmetic self-similar set, Acta Math. Hungar., 91, 325-332 (2001) · Zbl 1012.11007 [5] Allouche, J.-P.; Currie, J.; Shallit, J., Extremal infinite overlap-free binary words, Electron. J. Combin., 5, 1 (1998), #R27 (electronic). http://www.combinatorics.org/Volume_5/Abstracts/v5i1r27.html · Zbl 0890.68107 [6] J.-P. Allouche, C. Frougny, Univoque numbers and an avatar of Thue-Morse. Preprint, http://arxiv.org/abs/0712.0102; J.-P. Allouche, C. Frougny, Univoque numbers and an avatar of Thue-Morse. Preprint, http://arxiv.org/abs/0712.0102 · Zbl 1168.11002 [7] J.-P. Allouche, A. Glen, Extremal properties of (epi)sturmian sequences and distribution modulo 1, 2008 (in preparation); J.-P. Allouche, A. Glen, Extremal properties of (epi)sturmian sequences and distribution modulo 1, 2008 (in preparation) · Zbl 1254.68192 [8] Allouche, J.-P.; Shallit, J. O., The ubiquitous Prouhet-Thue-Morse sequence, (Ding, C.; Helleseth, T.; Niederreiter, H., Sequences and Their Applications, Proceedings of SETA ’98 (1999), Springer-Verlag), 1-16 · Zbl 1005.11005 [9] Allouche, J.-P.; Shallit, J., Automatic Sequences: Theory, Applications, Generalizations (2003), Cambridge University Press · Zbl 1086.11015 [10] Berstel, J., Sur la construction de mots sans carré, Sém. Théor. Nombres Bordeaux, Exposé 18, 18.01-18.15 (1978-79) [11] Berstel, J., Sur les mots sans carré définis par un morphisme, (Maurer, H. A., Proc. 6th Int’l Conf. on Automata, Languages, and Programming, ICALP ’79. Proc. 6th Int’l Conf. on Automata, Languages, and Programming, ICALP ’79, Lecture Notes in Comp. Sci., vol. 71 (1979), Springer-Verlag), 16-25 · Zbl 0425.20046 [12] Cao, W.-T.; Wen, Z.-Y., Some properties of the factors of Sturmian sequences, Theoret. Comput. Sci., 304, 365-385 (2003) · Zbl 1045.68109 [13] Cassaigne, J., An algorithm to test if a given circular HD0L-language avoids a pattern, (Information Processing ’94, vol. I, (Hamburg, 1994). Information Processing ’94, vol. I, (Hamburg, 1994), IFIP Trans. A Comput. Sci. Tech., A-51 (1994), North-Holland: North-Holland Amsterdam), 459-464, 10.1.1.9.2125 [14] Cassaigne, J., Limit values of the recurrence quotient of Sturmian sequences, Theoret. Comput. Sci., 218, 3-12 (1999) · Zbl 0916.68115 [15] Crochemore, M., Sharp characterizations of squarefree morphisms, Theoret. Comput. Sci., 18, 221-226 (1982) · Zbl 0482.68085 [16] Damanik, D.; Lenz, D., The index of Sturmian sequences, European J. Combin., 23, 23-29 (2002) · Zbl 1002.11020 [17] Erdős, P.; Joó, I.; Komornik, V., Characterization of the unique expansions \(1 = \sum_{i = 1}^\infty q^{- n_i}\), and related problems, Bull. Soc. Math. France, 118, 377-390 (1990) · Zbl 0721.11005 [18] Galois, E., Démonstration d’un théorème sur les fractions continues périodiques, Ann. Math. Pures et Appl., 19, 294-301 (1828-1829) [19] Grillenberger, C., Construction of strictly ergodic systems, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 25, 323-334 (1973) · Zbl 0253.28004 [20] Honkala, J., A decision method for the recognizability of sets defined by number systems, RAIRO Inform. Théor. Appl., 20, 395-403 (1986) · Zbl 0639.68074 [21] Karhumäki, J., On cube-free \(\omega \)-words generated by binary morphisms, Discrete Appl. Math., 5, 279-297 (1983) · Zbl 0505.03022 [22] Komornik, V.; Loreti, P., Unique developments in non-integer bases, Amer. Math. Monthly, 105, 636-639 (1998) · Zbl 0918.11006 [23] Komornik, V.; Loreti, P., Subexpansions, superexpansions and uniqueness properties in non-integer bases, Period. Math. Hungar., 44, 197-218 (2002) · Zbl 1017.11008 [24] Komornik, V.; Loreti, P., On the topological structure of univoque sets, J. Number Theory, 122, 157-183 (2007) · Zbl 1111.11005 [25] Krieger, D., On critical exponents in fixed points of \(k\)-uniform binary morphisms, RAIRO-Theor. Inf. Appl., 43, 41-68 (2009), Corrigenda available at http://www.wisdom.weizmann.ac.il/ daliak/papers/UniformBinaryThesis.pdf · Zbl 1170.68034 [26] Krieger, D., On critical exponents in fixed points of non-erasing morphisms, Theoret. Comput. Sci., 376, 70-88 (2007) · Zbl 1111.68058 [27] Leconte, M., A characterization of power-free morphisms, Theoret. Comput. Sci., 38, 117-122 (1985) · Zbl 0572.68066 [28] Lehr, S., Sums and rational multiples of \(q\)-automatic sequences are \(q\)-automatic, Theoret. Comput. Sci., 108, 385-391 (1993) · Zbl 0768.11013 [29] Loftus, J.; Shallit, J.; Wang, M.-w., New problems of pattern avoidance, (Developments in Language Theory (DLT’99) (2000), World Scientific), 185-199 · Zbl 1013.68103 [30] Lothaire, M., Algebraic Combinatorics on Words (2002), Cambridge University Press · Zbl 1001.68093 [31] Mignosi, F.; Séébold, P., If a D0L language is \(k\)-power free then it is circular, (Lingas, A.; Karlsson, R.; Carlsson, S., Proc. 20th Int’l Conf. on Automata, Languages, and Programming, ICALP’93. Proc. 20th Int’l Conf. on Automata, Languages, and Programming, ICALP’93, Lect. Notes. in Comp. Sci., vol. 700 (1993), Springer-Verlag), 507-518 · Zbl 1422.68157 [32] Niu, M.; Wen, Z.-x., A property of \(m\)-tuplings Morse sequence, Wuhan Univ. J. Nat. Sci., 11, 473-476 (2006) · Zbl 1155.11311 [33] Rampersad, N.; Shallit, J., Words avoiding reversed subwords, J. Combin. Math. Combin. Comput., 54, 157-164 (2005) · Zbl 1081.68076 [34] Raymond, D.; Wood, D., Grail: A C++ library for automata and expressions, J. Symbolic Comput., 17, 341-350 (1994) · Zbl 0942.68803 [35] Richomme, G.; Wlazinski, F., Existence of finite test-sets for \(k\)-power-freeness of uniform morphisms, Disc. Appl. Math., 155, 2001-2016 (2007) · Zbl 1129.68053 [36] Shallit, J. O., Simple continued fractions for some irrational numbers, J. Number Theory, 11, 209-217 (1979) · Zbl 0404.10003 [37] Thue, A., Über unendliche Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl., 7, 1-22 (1906), Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 139-158 · JFM 39.0283.01 [38] Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl., 1, 1-67 (1912), Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 413-478 · JFM 44.0462.01 [39] van der Poorten, A. J.; Shallit, J. O., Folded continued fractions, J. Number Theory, 40, 237-250 (1992) · Zbl 0753.11005 [40] M. de Vries, V. Komornik, Unique expansions of real numbers. Preprint, http://arxiv.org/abs/math/0609708v3; M. de Vries, V. Komornik, Unique expansions of real numbers. Preprint, http://arxiv.org/abs/math/0609708v3 · Zbl 1166.11007 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.