Complexity function: Difference between revisions

Revision as of 12:36, 19 May 2011

Revision as of 06:04, 21 December 2011

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 substrings of ''n'' consecutive elements from the string ''u''.

A [[Sturmian word]] is one of minimal complexity function ''n''&nbsp;+&nbsp;1. An example is the [[Fibonacci word]].<ref name=deluca1995>{{cite journal | journal=Information Processing Letters | year=1995 | pages=307–312 | doi=10.1016/0020-0190(95)00067-M | title=A division property of the Fibonacci word | first=Aldo | last=de Luca | volume=54 | issue=6 }}</ref>

Line 9:

[[Category:Theoretical computer science]]

{{mathcomp-sci-theory-stub}}