Complexity function

Complexity function

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 + 1. An example is the Fibonacci word.[1]

References

  1. ^ de Luca, Aldo (1995). "A division property of the Fibonacci word". Information Processing Letters 54 (6): 307–312. doi:10.1016/0020-0190(95)00067-M. 
  • Fogg, N. Pytheas; Berthé, Valérie, eds (2002). Substitutions in dynamics, arithmetics, and combinatorics. Lecture notes in mathematics. 1794. Springer. ISBN 3540441417. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Proper complexity function — A proper complexity function is a function f mapping a natural number to a natural number such that: * f is nondecreasing; * there exists a k string Turing machine M such that on any input of length n , M halts after O( n + f ( n )) steps, uses… …   Wikipedia

  • Complexity — For other uses, see Complexity (disambiguation). In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In… …   Wikipedia

  • Complexity index — Besides complexity intended as a difficulty to compute a function (see computational complexity), in modern computer science and in statistics another complexity index of a function stands for denoting its information content, in turn affecting… …   Wikipedia

  • Function point — A function point is a unit of measurement to express the amount of business functionality an information system provides to a user. Function points are the units of measure used by the IFPUG Functional Size Measurement Method. The IFPUG FSM… …   Wikipedia

  • Complexity of constraint satisfaction — The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction… …   Wikipedia

  • Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… …   Wikipedia

  • Function problem — In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO.Notable examples include the travelling salesman problem, which asks for the …   Wikipedia

  • complexity — /keuhm plek si tee/, n., pl. complexities for 2. 1. the state or quality of being complex; intricacy: the complexity of urban life. 2. something complex: the complexities of foreign policy. [1715 25; COMPLEX + ITY] * * * ▪ scientific theory… …   Universalium

  • Irreducible complexity — This article covers irreducible complexity as used by those who argue for intelligent design. For information on irreducible complexity as used in Systems Theory, see Irreducible complexity (Emergence). Irreducible complexity (IC) is an argument… …   Wikipedia

  • Kolmogorov complexity — In algorithmic information theory (a subfield of computer science), the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. It is named after Soviet Russian… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”