Jump to content

Complexity function

Edit links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Zarboublian (talk | contribs) at 17:01, 23 September 2010 (New article - initially a stub). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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 which counts the number of different substrings of n consecutive elements from the string u.

A Sturmian sequence is one of minimal complexity function n+1. An example is the Fibonacci word.

References

  • N. Pytheas Fogg; Valérie Berthé, eds. (2002). Substitutions in dynamics, arithmetics, and combinatorics. Lecture notes in mathematics. Vol. 1794. Springer. ISBN 3540441417.

This article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Complexity_function&oldid=386572260"