Complexity function: Difference between revisions

Revision as of 11:20, 16 December 2012

Revision as of 11:23, 16 December 2012

Line 1:

In [[computer science]], the '''complexity function''' of a string, a finite or infinite sequence ''u'' of letters from some alphabet, is the function ''p''_''u''(''n'') of a positive integer ''n'' that counts the number of different factors (consecutive substrings) of length ''n'' from the string&nbsp;''u''.<ref name=L7>Lothaire (2011) p.7</ref><ref name=L46/><ref name=PF3>Pytheas Fogg (2002) p.3</ref><ref name=BLRS82>Berstel et al (2009) p.82</ref><ref name=AS298>Allouche & Shallit (2003) p.298</ref>

For a string ''u'' of length at least ''n'' over an alphabet of size ''k'' we clearly have