TOPICS
Search

Sturmian Sequence


A Sturmian sequence is a right-infinite aperiodic binary sequence whose factor complexity is p(n)=n+1 for every positive integer n. By the Morse-Hedlund theorem, this is the smallest possible factor complexity for an aperiodic infinite word.

An example is the sequence arising from the substitution system

0->01
(1)
1->0,
(2)

yielding 0->01->010->01001->01001010->..., which gives the Sturmian sequence 01001010....

Sturm functions are sometimes also said to form a Sturmian sequence.


See also

Factor Complexity, Morse-Hedlund Theorem, Sequence, Sturm Function, Sturm Theorem, Substitution System

Explore with Wolfram|Alpha

References

Morse, M. and Hedlund, G. A. "Symbolic Dynamics II. Sturmian Trajectories." Amer. J. Math. 62, 1-42, 1940. https://doi.org/10.2307/2371441.

Referenced on Wolfram|Alpha

Sturmian Sequence

Cite this as:

Weisstein, Eric W. "Sturmian Sequence." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SturmianSequence.html

Subject classifications