×

Asymptotic subword complexity of fixed points of group substitutions. (English) Zbl 1168.68025

Summary: The subword complexity of fixed points of some types of substitutions was studied by various authors. Here we introduce a family of substitutions, arising from multiplication tables of finite groups and other similar structures, and analyze their subword complexity.

MSC:

68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J.-P., Sur la complexité des suites infinies, Bull. Belg. Math. Soc., 1, 133-143 (1994) · Zbl 0803.68094
[2] Allouche, J.-P.; Berthé, V., Pascal’s triangle complexity automata, Bull. Belg. Math. Soc., 4, 1-23 (1997) · Zbl 0922.11012
[3] Berend, D.; Harmse, J. E., On some arithmetical properties of middle binomial coefficients, Acta Arith., 84, 31-41 (1998) · Zbl 0903.11004
[4] Astudillo, R., On a class of Thue-Morse type sequences, J. Integer. Seq., 6 (2003), Article 03.4.2 · Zbl 1074.11016
[5] Ehrenfeucht, A.; Rozenberg, G., On the subword complexity of D0L-languages with a constant distribution, Inform. Process. Lett., 13, 108-113 (1981) · Zbl 0546.68062
[6] Ehrenfeucht, A.; Rozenberg, G., On the subword complexity of square-free D0L-languages, Theoret. Comput. Sci., 16, 25-32 (1981) · Zbl 0481.68073
[7] Ehrenfeucht, A.; Rozenberg, G., On the subword complexity of locally catenative D0L-languages, Inform. Process. Lett., 16, 7-9 (1983) · Zbl 0501.68038
[8] Ehrenfeucht, A.; Rozenberg, G., On the subword complexity of \(m\)-free D0L-languages, Inform. Process. Lett., 17, 121-124 (1983) · Zbl 0526.68067
[9] Ehrenfeucht, A.; Rozenberg, G., On the size of the alphabet and the subword complexity of square-free D0L languages, Semigroup Forum, 26, 215-223 (1983) · Zbl 0512.68058
[10] Ferenczi, S., Complexity of sequences and dynamical systems, Discrete Math., 206 (1999) · Zbl 0936.37008
[11] Ferenczi, S.; Kása, Z., Complexity for finite factors of inifite sequences, Theoret. Comput. Sci., 218, 177-195 (1999) · Zbl 0916.68112
[12] Frid, A., Arithmetical complexity of symmetric D0L words, Theoret. Comput. Sci., 306, 535-542 (2003) · Zbl 1070.68068
[13] A. Frid, On uniform DOL words, STACS 1998, pp. 544-554; A. Frid, On uniform DOL words, STACS 1998, pp. 544-554
[14] Frid, A., On the frequency of factors in a D0L word, J. Autom. Lang. Comb., 3, 1, 29-41 (1998) · Zbl 0912.68116
[15] Morse, M., Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22, 84-100 (1921) · JFM 48.0786.06
[16] Mossé, B., Reconnaissabilité des substitutions et complixité des suites automatices, Bull. Soc. Math. France, 124, 329-346 (1996) · Zbl 0855.68072
[17] J.-J. Pansiot, Complexité des Facteurs des Mots Infinis Engendrés par Morphimes Itérés, ICALP 1984, pp. 380-389; J.-J. Pansiot, Complexité des Facteurs des Mots Infinis Engendrés par Morphimes Itérés, ICALP 1984, pp. 380-389
[18] Tapsoba, T., Automates calculant la complexité des suits automatiques, J. Théor. Nombres Bordeaux, 6, 124-134 (1994) · Zbl 0815.11015
[19] Thue, A., Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. Mat. Nat. Kl., 7, 1-22 (1906), Reprinted in Selected mathematical papers of Alex Thue, T. Nagell (Ed.), Universitetsforlaget, Oslo, 1977, pp. 139-158 · JFM 39.0283.01
[20] 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 Alex Thue, T. Nagell (Ed.), Universitetsforlaget, Oslo, 1977, pp. 413-418 · JFM 44.0462.01
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.