×

Morphisms on infinite alphabets, countable states automata and regular sequences. (English) Zbl 1373.11025

Summary: In this paper, we prove that a class of regular sequences can be viewed as projections of fixed points of uniform morphisms on a countable alphabet, and also can be generated by countable states automata. Moreover, we prove that the regularity of some regular sequences is invariant under some codings.

MSC:

11B85 Automata sequences
68R15 Combinatorics on words
11B37 Recurrences
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allouche, J. P., Automates finis en théorie des nombres, Exposition Math, 5, 239-266 (1987) · Zbl 0641.10041
[2] Allouche, J. P.; Shallit, J., The ring of \(k\)-regular sequences, Theor Comput Sci, 98, 163-197 (1992) · Zbl 0774.68072
[3] Allouche, J. P.; Shallit, J., The ring of \(k\)-regular sequences, II, Theor Comput Sci, 307, 3-29 (2003) · Zbl 1058.68066
[4] Allouche, J. P.; Shallit, J., Automatic sequences. theory, applications, generalizations (2003), Cambridge University Press, Cambridge · Zbl 1086.11015
[5] Allouche, J. P.; Scheicher, K.; Tichy, R. F., Regular maps in generalized number systems, Math Slovaca, 50, 41-58 (2000) · Zbl 0957.11014
[6] Bell, J. P., A generalization of Cobhams theorem for regular sequences, Sém Lothar Combin (2006)
[7] Bell, J. P.; Coons, M.; Hare, K. G., The minimal growth of a \(k\)-regular sequence, Bull Aust Math Soc, 90, 195-203 (2014) · Zbl 1348.11023
[8] Berthé, V.; Rigo, M., Combinatorics, automata and number theory, Encyclopedia Math. Appl., vol. 135 (2010), Cambridge University Press, Cambridge · Zbl 1197.68006
[9] Cassaigne, J.; Gonidec, M. L., Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables, Journal de Théorie des Nombres de Bordeaux, 22, 307-338 (2010) · Zbl 1211.68231
[10] Charlier, E.; Rampersad, N.; Shallit, J., Enumeration and decidable properties of automatic sequences, Int J Found Comput Sci, 5, 1035-1066 (2012) · Zbl 1282.68186
[11] Christol, G.; Kamae, T.; France, M. M.; Rauzy, G., Suites algébriques, automates et substitutions, Bull Soc Math Fr., 108, 401-419 (1980) · Zbl 0472.10035
[12] Cobham, A., Uniform tag sequences, Math Syst Theory, 6, 164-192 (1972) · Zbl 0253.02029
[13] Everest, G.; van der Poorten, A.; Shparlinski, I.; Ward, T., Recurrence sequences, Math. Surveys Monogr. vol. 104 (2003), Amer. Math. Soc., Providence, RI · Zbl 1033.11006
[14] Ferenczi, S., Substitution dynamical systems on infinite alphabets, Ann Inst Fourier, Grenoble, 56, 7, 2315-2343 (2006) · Zbl 1147.37007
[15] Fogg, N. P., Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Math., vol. 1794 (2002), Springer-Verlag, Berlin · Zbl 1014.11015
[16] Paquet, M. G.; Shallit, J., Avoiding squares and overlaps over the natural numbers, Discrete Math, 309, 6245-6254 (2009) · Zbl 1215.68193
[17] Gonidec, M. L., Sur la complexité de mots infinis engendrés par des q-automates dénombrables, Ann Inst Fourier, Grenoble, 56, 7, 2463-2491 (2006) · Zbl 1121.68090
[18] Gonidec, M. L., Sur la complexité des mots \(q^∞\)-automatiques (2006), Universitáe AixMareseille II, Ph.D. thesis
[19] Gonidec, M. L., Drunken man infinite words complexity, Rairo-Theor Inf Appl, 42, 599-613 (2008) · Zbl 1188.68217
[20] Gonidec, M. L., On complexity functions of infinite words associated with generalized dyck languages, Theor Comput Sci, 407, 117-133 (2008) · Zbl 1152.68030
[21] Loxton, J. H.; van der Poorten, A. J., Arithmetic properties of automata: regular sequences, J Reine Angew Math, 392, 57-69 (1988) · Zbl 0656.10033
[22] Mauduit, C., Propriétés arithmétiques des substitutions et automates infinis, Ann Inst Fourier, Grenoble, 56, 7, 2525-2549 (2006) · Zbl 1147.11016
[23] Moshe, Y., On some questions regarding \(k\)-regular and \(k\)-context-free sequences, Theor Comput Sci, 400, 62-69 (2008) · Zbl 1143.68038
[24] Rowland, E., Non-regularity of \(\lfloor \alpha + \log_k n \rfloor \), Integers, 10, 1, 19-23 (2010) · Zbl 1193.11024
[25] Thomas, W., A short introduction to infinite automata, Proceedings of the 5th international conference ‘developments in language theory”, vol. 2295, 134-144 (2001), Springer LNCS · Zbl 1073.68671
[26] Wen, Z. X.; Zhang, J. M.; Wu, W., On the regular sum-free sets, Eur J Combin, 49, 42-56 (2015) · Zbl 1414.11030
[28] Zhang, S.; Yao, J. Y., Analytic functions over \(Z_p\) and \(p\)-regular sequences, C R Acad Sci Paris, Ser-I, 349, 947-952 (2011) · Zbl 1266.30035
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.