Sturmian word: Difference between revisions
Undid revision 472557142 by 122.163.196.136 (talk) (vandalism) |
Gareth Jones (talk | contribs) including billiard sequence in article lead |
||
Line 1: | Line 1: | ||
In [[mathematics]], a '''Sturmian word''' (or '''billiard sequence'''<ref>{{cite doi|10.1007/3-540-45535-3_19}}</ref>), named after [[Jacques Charles François Sturm]], is a certain kind of infinitely long [[string (computer science)|sequence of characters]]. Such a sequence can be generated by considering a game of [[English billiards]] on a square table. The struck ball will successively hit the vertical and horizontal edges, generating a sequence of letters ''h'' and ''v''.<ref>{{cite book|page=117|title=Recent Trends in Combinatorics: The Legacy of Paul Erdős|year=2009|first1=Ervin|last1=Győri|first2=Vera|last2=Sós|publisher=Cambridge University Press|isbn=0521120047}}</ref> This sequence is a Sturmian word. |
|||
In [[mathematics]], a '''Sturmian word''', named after [[Jacques Charles François Sturm]], is a certain kind of [[infinity|infinite]] [[String (computer science)|word]]. |
|||
== Definition == |
== Definition == |
Revision as of 18:16, 8 March 2012
In mathematics, a Sturmian word (or billiard sequence[1]), named after Jacques Charles François Sturm, is a certain kind of infinitely long sequence of characters. Such a sequence can be generated by considering a game of English billiards on a square table. The struck ball will successively hit the vertical and horizontal edges, generating a sequence of letters h and v.[2] This sequence is a Sturmian word.
Definition
A word is a (potentially) infinite sequence of symbols drawn from a finite alphabet. Call any finite contiguous subsequence of a word a factor. Then, a word w is Sturmian if, for all natural numbers n, w has exactly n + 1 distinct factors of length n: that is, the complexity function of w is n + 1.
Note that there must then be two distinct factors of length 1, implying that word uses exactly 2 symbols from the alphabet (without loss of generality we can call these 0 and 1). Also, a Sturmian word is necessarily infinite.
Discussion
A sequence over {0,1} is a Sturmian word if and only if there exist two real numbers and , with irrational, such that
for all . Thus a Sturmian word provides a discretization of the straight line with slope and intercept ρ. Without loss of generality, we can always assume , because for any integer k we have
All the Sturmian words corresponding to the same slope have the same set of factors; the word corresponding to the intercept is the standard word or characteristic word of slope . Hence, if , the characteristic word is the first difference of the Beatty sequence corresponding to the irrational number .
The standard word is also the limit of a sequence of words defined recursively as follows:
Let be the continued fraction expansion of , and define
where the product between words is just their concatenation. Every word in the sequence is a prefix of the next ones, so that the sequence itself converges to an infinite word, which is .
The infinite sequence of words defined by the above recursion is called the standard sequence for the standard word , and the infinite sequence d = (d1, d2, d3, ...) of nonnegative integers, with d1 ≥ 0 and dn > 0 (n ≥ 2), is called its directive sequence.
A famous example of (standard) Sturmian word is the Fibonacci word;[3] its slope is , where is the golden ratio.
History
Although the study of Sturmian words dates back to Johann III Bernoulli (1772), the first comprehensive study of them was by Gustav A. Hedlund and Marston Morse in 1940. They introduced the term Sturmian, in honor of the mathematician Jacques Charles François Sturm.
References
- ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/3-540-45535-3_19, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1007/3-540-45535-3_19
instead. - ^ Győri, Ervin; Sós, Vera (2009). Recent Trends in Combinatorics: The Legacy of Paul Erdős. Cambridge University Press. p. 117. ISBN 0521120047.
- ^ 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.
- Lothaire, M. (2002). "Sturmian Words". Algebraic Combinatorics on Words. Cambridge UK: Cambridge University Press. ISBN 0521812208. Retrieved 2007-02-25.
{{cite book}}
: External link in
(help); Unknown parameter|chapterurl=
|chapterurl=
ignored (|chapter-url=
suggested) (help)