Abstract
The subword complexity function \(p_{w}\) of a finite word \(w\) over a finite alphabet A with card \(A=q\geq1\) is defined by \(p_{w}(n)=\)card \((F(w)\cap A^{n})\) for \(n\in 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. \newline \qquad The function h defined as \(h(n)=min\{q^{n},N-n+1\}forn\in \{0,1,…,N\}\) has values greater than or equal to those of the complexity function pw for any \(w\in A^{N}\) , i.e., \(pw(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 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 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.
Authors
Mira-Cristiana Anisiu
T. Popoviciu” Institute of Numerical Analysis, Romanian Academy, Romania
Julien Cassaigne
Institut de Mathematiques de Luminy, CNRS UPR 9016 / FRUMAM, Case 907, 13288 Marseille, France,
Keywords
Subword complexity function; finite words; de Bruijn graph.
Paper coordinates
M.-C. Anisiu, J. Cassaigne, Properties of the complexity function for finite words, Rev. Anal. Numér. Théor. Approx. 33 (2) (2004), 123-139 (pdf file here)
About this paper
Journal
Publisher Name
DOI
Print ISSN
Online ISSN
google scholar link
[1] Anisiu, M.-C., Blazsik, Z. and Kasa, Z., Maximal complexity of finite words, Pure Math. Appl., 13, pp. 39–48, 2002.
[2] de Bruijn, N. G., A combinatorial problem, Nederl. Akad. Wetensch. Proc., 49, pp. 758–764, 1946 = Indag. Math., 8, pp. 461–467, 1946.
[3] de Bruijn, N. G., Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n 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.
[4] Champernowne, D. G., The construction of decimals normal in the scale of ten, J. London Math. Soc., 8, pp. 254–260, 1933.
[5] 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.
[6] Ehrenfeucht, A., Lee, K. P. and Rozenberg, G., Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. Comput. Sci., 1, pp. 59–75, 1975.
[7] Flye Sainte-Marie, C., Solution to question nr. 48, l’ Intermediaire des Mathematiciens, 1, pp. 107–110, 1894.
[8] Fredericksen, H., A survey of full length nonlinear shift register cycle algorithms, SIAM Review, 24, pp. 195–221, 1982.
[9] Games, R. A., A generalized recursive construction for de Bruijn sequences, IEEE Trans. Inform. Theory, 29, pp. 843–850, 1983.
[10] Good, I. J., Normal recurring decimals, J. London Math. Soc., 21, pp. 167–169, 1946.
[11] Heinz, M., Zur Teilwortkomplexit¨at f¨ur W¨orter und Folgenuber einem endlichen Alphabet, EIK, 13, pp. 27–38, 1977.
[12] Hunyadvary, L. and Ivanyi, A., On some complexity measures of words, Dep. Math., Karl Marx Univ. Econ., Budapest 1984-2, pp. 67–82, 1984.
[13] Hunyadvary, L. and Ivanyi, A. , Construction of complex chains sequences and ring sequences, in Abstracts of Colloquium Theory of Algorithms, Pecs, p. 20, 1984.
[14] Leve, F. and Seebold, P. , Proof of a conjecture on word complexity, Journees Montoises d’Informatique Theorique (Marne-la-Vallee, 2000), Bull. Belg. Math. Soc. Simon Stevin, 8, pp. 277–291, 2001.
[15] de Luca, A., On the combinatorics of finite words, Theoret. Comput. Sci., 218, pp 13–39, 1999.
[16] Martin, M. H., A problem in arrangements, Bull. American Math. Soc., 40, pp. 859–864, 1934.
[17] Morse, M. and Hedlund, G. A., Symbolic dynamics, Amer. J. Math., 60, pp. 815–866, 1938.
[18] Ralston, A., A new memoryless algorithm for de Bruijn sequences, J. Algorithms, 2, pp. 50–62, 1981.
[19] Shallit, J., On the maximum number of distinct factors in a binary string, Graph Comb., 9, pp. 197–200, 1993.
[20] Voros, N. , On the complexity measures of symbol-sequences, in Proceedings of the Conference of Young Programmers and Mathematicians (ed. A. Iv´anyi), Eotvos Lorand University, Budapest, pp. 43–50, 1984.
I am raw html block.
Click edit button to change this html