Complexity function: Difference between revisions

Revision as of 17:27, 23 October 2012

Revision as of 18:19, 23 October 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 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/>

An '''aperiodic sequence''' is one which does not consist of a finite sequence followed by a finite cycle. An aperiodic sequence has complexity function at least ''n''+1.<ref name=L22>Lothaire (2011) p.22</ref>