TOPICS
Search

Factor Complexity


The factor complexity p_w(n) of a finite or infinite word w, also called its subword complexity, is the number of distinct contiguous factors of length n occurring in w.

The Morse-Hedlund theorem states that a right-infinite word is ultimately periodic if and only if p_w(n)<=n for some positive integer n. Consequently, an aperiodic right-infinite word has factor complexity at least n+1 for every n. Sturmian sequences are precisely the aperiodic binary words attaining p_w(n)=n+1.

Among ternary words with factor complexity 2n+1, the minimum possible critical exponent is 2.4808726... (Currie 2026).


See also

Critical Exponent, Morse-Hedlund Theorem, Sturmian Sequence, Word

Explore with Wolfram|Alpha

References

Allouche, J.-P. and Shallit, J. Automatic Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge University Press, 2003.Currie, J. D. "Words with Factor Complexity 2n+1 and Minimal Critical Exponent." Elec. J. Combin. 33, No. 3, P3.31, 2026. https://doi.org/10.37236/14527.Morse, M. and Hedlund, G. A. "Symbolic Dynamics II. Sturmian Trajectories." Amer. J. Math. 62, 1-42, 1940. https://doi.org/10.2307/2371441.

Cite this as:

Weisstein, Eric W. "Factor Complexity." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FactorComplexity.html

Subject classifications