Properties of the complexity function for finite words
DOI:
https://doi.org/10.33993/jnaat332-767Keywords:
subword complexity function, finite words, de Bruijn graphAbstract
The subword complexity function \(p_{w}\) of a finite word \(w\) over a finite alphabet \(A\) with \(\operatorname*{card}A=q\geq1\) is defined by \(p_{w}(n)=\operatorname*{card}(F(w)\cap A^{n})\) for \(n\in\mathbb{N},\) where \(F(w)\) represents the set of all the subwords or factors of \(w\). The shape of the complexity function, especially its piecewise monotonicity, is studied in detail.The function \(h\) defined as \(h(n)=\min\left\{ q^{n},N-n+1\right\} \) for \(n\in\{0,1,\) \(...,N\}\) has values greater than or equal to those of the complexity function \(p_{w}\) for any \(w\in A^{N}\), i.e., \(p_{w}(n)\leq h(n)\) for all \(n\in\{0,1,...,N\}\). As a first result regarding \(h\), it is proved that for each \(N\in\mathbb{N}\) there exist words of length \(N\) for which the maximum of their complexity function is equal to the maximum of the function \(h\); a way to construct such words is described. This result gives rise to a further question: for a given \(N\), is there a word of length \(N\) whose complexity function coincides with \(h\) for each \(n\in\{0,1,...,N\}?\) The problem is answered in affirmative, with different constructive proofs for binary alphabets (\(q=2\)) and for those with \(q>2.\) This means that for each \(N\in\mathbb{N},\) there exist words \(w\) of length \(N\) whose complexity function is equal to the function \(h\). Such words are constructed using the de Bruijn graphs.Downloads
References
Anisiu, M.-C., Blázsik, Z. and Kása, Z., Maximal complexity of finite words, Pure Math. Appl., 13, pp. 39-48, 2002.
de Bruijn, N. G., A combinatorial problem, Nederl. Akad. Wetensch. Proc., 49, pp. 758--764, 1946 = Indag. Math., 8, pp. 461-467, 1946.
de Bruijn, N. G., Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2ⁿ zeros and ones that show each n-letter word exactly once, T. H. -Report 75-WSK-06, Technological University Eindhoven, the Netherlands, pp. 1-14, 1975.
Champernowne, D. G., The construction of decimals normal in the scale of ten, J. London Math. Soc., 8, pp. 254-260, 1933, https://doi.org/10.1112/jlms/s1-8.4.254. DOI: https://doi.org/10.1112/jlms/s1-8.4.254
Cummings, L. J. and Wiedemann, D., Embedded de Bruijn sequences, Proceedings of the 7th Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Florida, 1986), Congr. Numer., 53, pp. 155-160, 1986.
Ehrenfeucht, A., Lee, K. P. and Rozenberg, G., Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. Comput. Sci., 4, pp. 219-236, 1975, https://doi.org/10.1007/BF01007760. DOI: https://doi.org/10.1007/BF01007760
Flye Sainte-Marie, C., Solution to question nr. 48, l'Intermédiaire des Mathématiciens, 1, pp. 107-110, 1894.
Fredericksen, H., A survey of full length nonlinear shift register cycle algorithms, SIAM Review, 24, pp. 195-221, 1982, https://doi.org/10.1137/1024041. DOI: https://doi.org/10.1137/1024041
Games, R. A., A generalized recursive construction for de Bruijn sequences, IEEE Trans. Inform. Theory, 29, pp. 843-850, 1983, https://doi.org/10.1109/TIT.1983.1056764. DOI: https://doi.org/10.1109/TIT.1983.1056764
Good, I. J., Normal recurring decimals, J. London Math. Soc., 21, pp. 167-169, 1946, https://doi.org/10.1112/jlms/s1-21.3.167. DOI: https://doi.org/10.1112/jlms/s1-21.3.167
Heinz, M., Zur Teilwortkomplexität für Wörter und Folgen über einem endlichen Alphabet, EIK, 13, pp. 27-38, 1977. DOI: https://doi.org/10.1515/9783112484845-003
Hunyadváry, L. and Iványi, A., On some complexity measures of words, Dep. Math., Karl Marx Univ. Econ., Budapest 1984-2, pp. 67-82, 1984.
Hunyadváry, L. and Iványi, A., Construction of complex chains sequences and ring sequences, in Abstracts of Colloquium Theory of Algorithms, Pécs, p. 20, 1984.
Levé, F. and Séébold, P., Proof of a conjecture on word complexity, Journées Montoises d'Informatique Théorique (Marne-la-Vallée, 2000), Bull. Belg. Math. Soc. Simon Stevin, 8, pp. 277-291, 2001. DOI: https://doi.org/10.36045/bbms/1102714173
de Luca, A., On the combinatorics of finite words, Theoret. Comput. Sci., 218, pp. 13--39, 1999, https://doi.org/10.1016/S0304-3975(98)00248-5. DOI: https://doi.org/10.1016/S0304-3975(98)00248-5
Martin, M. H., A problem in arrangements, Bull. American Math. Soc., 40, pp. 859-864, 1934, https://doi.org/10.1090/S0002-9904-1934-05988-3. DOI: https://doi.org/10.1090/S0002-9904-1934-05988-3
Morse, M. and Hedlund, G. A., Symbolic dynamics, Amer. J. Math., 60, pp. 815-866, 1938, https://doi.org/10.2307/2371264. DOI: https://doi.org/10.2307/2371264
Ralston, A., A new memoryless algorithm for de Bruijn sequences, J. Algorithms, 2, pp. 50--62, 1981, https://doi.org/10.1016/0196-6774(81)90007-9. DOI: https://doi.org/10.1016/0196-6774(81)90007-9
Shallit, J., On the maximum number of distinct factors in a binary string, Graph Comb., 9, pp. 197-200, 1993, https://doi.org/10.1007/BF02988306. DOI: https://doi.org/10.1007/BF02988306
Vörös, N., On the complexity measures of symbol-sequences, in Proceedings of the Conference of Young Programmers and Mathematicians (ed. A. Iványi), Eötvös Loránd University, Budapest, pp. 43-50, 1984.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2015 Journal of Numerical Analysis and Approximation Theory
This work is licensed under a Creative Commons Attribution 4.0 International License.
Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
