{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:43:21Z","timestamp":1760237001718,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T00:00:00Z","timestamp":1581465600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100011929","name":"Foundation for Food and Agriculture Research","doi-asserted-by":"publisher","award":["534662"],"award-info":[{"award-number":["534662"]}],"id":[{"id":"10.13039\/100011929","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF Science &amp; Technology Center for Science of Information Grant","award":["CCF-0939370"],"award-info":[{"award-number":["CCF-0939370"]}]},{"DOI":"10.13039\/501100000930","name":"NSF","doi-asserted-by":"publisher","award":["DMS-1246818"],"award-info":[{"award-number":["DMS-1246818"]}],"id":[{"id":"10.13039\/501100000930","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Patterns within strings enable us to extract vital information regarding a string\u2019s randomness. Understanding whether a string is random (Showing no to little repetition in patterns) or periodic (showing repetitions in patterns) are described by a value that is called the kth Subword Complexity of the character string. By definition, the kth Subword Complexity is the number of distinct substrings of length k that appear in a given string. In this paper, we evaluate the expected value and the second factorial moment (followed by a corollary on the second moment) of the kth Subword Complexity for the binary strings over memory-less sources. We first take a combinatorial approach to derive a probability generating function for the number of occurrences of patterns in strings of finite length. This enables us to have an exact expression for the two moments in terms of patterns\u2019 auto-correlation and correlation polynomials. We then investigate the asymptotic behavior for values of     k = \u0398 ( log n )    . In the proof, we compare the distribution of the kth Subword Complexity of binary strings to the distribution of distinct prefixes of independent strings stored in a trie. The methodology that we use involves complex analysis, analytical poissonization and depoissonization, the Mellin transform, and saddle point analysis.<\/jats:p>","DOI":"10.3390\/e22020207","type":"journal-article","created":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T10:09:57Z","timestamp":1581674997000},"page":"207","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Asymptotic Analysis of the kth Subword Complexity"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9017-4359","authenticated-orcid":false,"given":"Lida","family":"Ahmadi","sequence":"first","affiliation":[{"name":"Department of Mathematics, Purdue University, West Lafayette, IN 47907, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark Daniel","family":"Ward","sequence":"additional","affiliation":[{"name":"Department of Statistics, Purdue University, West Lafayette, IN 47907, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,2,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0304-3975(75)90012-2","article-title":"Subword complexities of various classes of deterministic developmental languages without interactions","volume":"1","author":"Ehrenfeucht","year":"1975","journal-title":"Theor. Comput. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"815","DOI":"10.2307\/2371264","article-title":"Symbolic Dynamics","volume":"60","author":"Morse","year":"1938","journal-title":"Am. J. Math."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Jacquet, P., and Szpankowski, W. (2015). Analytic Pattern Matching: From DNA to Twitter, Cambridge University Press.","DOI":"10.1017\/CBO9780511843204"},{"key":"ref_4","unstructured":"Bell, T.C., Cleary, J.G., and Witten, I.H. (1990). Text Compression, Prentice-Hall."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1358","DOI":"10.1073\/pnas.89.4.1358","article-title":"Over-and under-representation of short oligonucleotides in DNA sequences","volume":"89","author":"Burge","year":"1992","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1056","DOI":"10.1016\/0888-7543(92)90019-O","article-title":"Base compositional structure of genomes","volume":"13","author":"Fickett","year":"1992","journal-title":"Genomics"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1363","DOI":"10.1093\/nar\/20.6.1363","article-title":"Statistical analyses of counts and distributions of restriction sites in DNA sequences","volume":"20","author":"Karlin","year":"1992","journal-title":"Nucleic Acids Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"4263","DOI":"10.1093\/nar\/24.21.4263","article-title":"Frequent Oligonucleotides and Peptides of the Haemophilus Influenzae Genome","volume":"24","author":"Karlin","year":"1996","journal-title":"Nucleic Acids Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1080\/07391102.1989.10506529","article-title":"Linguistics of Nucleotide Sequences II: Stationary Words in Genetic Texts and the Zonal Structure of DNA","volume":"6","author":"Pevzner","year":"1989","journal-title":"J. Biomol. Struct. Dyn."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1545","DOI":"10.1109\/TIT.2004.830793","article-title":"Shared information and program plagiarism detection","volume":"50","author":"Chen","year":"2004","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"R108","DOI":"10.1186\/gb-2009-10-10-r108","article-title":"Genomic DNA k-mer spectra: models and modalities","volume":"10","author":"Chor","year":"2009","journal-title":"Genome Biol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"i351","DOI":"10.1093\/bioinformatics\/bti1018","article-title":"De novo identification of repeat families in large genomes","volume":"21","author":"Price","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Janson, S., Lonardi, S., and Szpankowski, W. (2004). On the Average Sequence Complexity. Annual Symposium on Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/978-3-540-27801-6_6"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0097-3165(94)90065-5","article-title":"Autocorrelation on words and its applications: Analysis of suffix trees by string-ruler approach","volume":"66","author":"Jacquet","year":"1994","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_15","unstructured":"Liang, F.M. (1983). Word Hy-phen-a-tion by Com-put-er, Technical Report; Stanford University."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Weiner, P. (1973, January 15\u201317). Linear pattern matching algorithms. Proceedings of the 14th Annual Symposium on Switching and Automata Theory (swat 1973), Iowa City, IA, USA.","DOI":"10.1109\/SWAT.1973.13"},{"key":"ref_17","first-page":"1","article-title":"On correlation Polynomials and Subword Complexity","volume":"7","author":"Gheorghiciuc","year":"2007","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/2229163.2229175","article-title":"Counting occurrences for a finite set of words: Combinatorial methods","volume":"8","author":"Bassino","year":"2012","journal-title":"ACM Trans. Algorithms"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Park, G., Hwang, H.K., Nicod\u00e8me, P., and Szpankowski, W. (2008). Profile of Tries. Latin American Symposium on Theoretical Informatics, Springer.","DOI":"10.1007\/978-3-540-78773-0_1"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Flajolet, P., and Sedgewick, R. (2009). Analytic Combinatorics, Cambridge University Press.","DOI":"10.1017\/CBO9780511801655"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Lothaire, M. (2005). Applied Combinatorics on Words, Cambridge University Press.","DOI":"10.1017\/CBO9781107341005"},{"key":"ref_22","unstructured":"Szpankowski, W. (2011). Average Case Analysis of Algorithms on Sequences, John Wiley & Sons."},{"key":"ref_23","unstructured":"Widder, D.V. (2015). The Laplace Transform (PMS-6), Princeton University Press."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF02919754","article-title":"On the method of saddle points","volume":"2","year":"1952","journal-title":"Appl. Sci. Res."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/2\/207\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:57:04Z","timestamp":1760173024000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/2\/207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,12]]},"references-count":24,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,2]]}},"alternative-id":["e22020207"],"URL":"https:\/\/doi.org\/10.3390\/e22020207","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,2,12]]}}}