Sturmian Subshifts

Sturmian subshift

This modules contains few methods to enumerate of language of factors of length n within a Sturmian subshift.

EXAMPLES:

sage: from slabbe import SturmianSubshift
sage: s = SturmianSubshift(.35355)
sage: s
Sturmian subshift of slope 0.353550000000000
sage: s.characteristic_word()
word: abaabaabaabaababaabaabaabaabaababaabaaba...
sage: sorted(s.language(4))
[word: aaba, word: abaa, word: abab, word: baab, word: baba]
sage: s.random_factor(4)               # random
word: baba
sage: s.random_factor(4)               # random
word: abaa
sage: s.lexicographically_minimal_factor(10)
word: aabaabaaba
sage: s.lexicographically_maximal_factor(10)
word: babaabaaba

Providing other type of inputs works including the continued fraction expansion of a real number:

sage: slope = continued_fraction(([0,1,2,3], [3,4,5]))
sage: S = SturmianSubshift(slope); S
Sturmian subshift of slope [0; 1, 2, 3, (3, 4, 5)*]
sage: slope.n()
0.697174148591765
sage: sorted(S.language(5))
[word: abbab, word: abbba, word: babba, word: babbb, word: bbabb, word: bbbab]

Providing a rational number as input also works and its language still has complexity n+1 because we consider the language of the two sided characteristic sequence:

sage: S = SturmianSubshift(1/3); S
Sturmian subshift of slope 1/3
sage: S.characteristic_word()
word: aabaabaabaabaabaabaabaabaabaabaabaabaaba...
sage: sorted(S.language(3))
[word: aaa, word: aab, word: aba, word: baa]
sage: sorted(S.language(4))
[word: aaab, word: aaba, word: abaa, word: baaa, word: baab]

AUTHORS:

    1. Labbé, initial version, 2021

class slabbe.sturmian_subshift.SturmianSubshift(slope)

Bases: object

INPUT:

  • slope – real number in the interval [0,1]

EXAMPLES:

sage: from slabbe import SturmianSubshift
sage: s = SturmianSubshift(.35355)
characteristic_word()

Return the characteristic Sturmian word of given slope

EXAMPLES:

sage: from slabbe import SturmianSubshift
sage: s = SturmianSubshift(.35355)
sage: s.characteristic_word()
word: abaabaabaabaababaabaabaabaabaababaabaaba...

Rational slope:

sage: s = SturmianSubshift(1/4)
sage: s.characteristic_word()
word: aaabaaabaaabaaabaaabaaabaaabaaabaaabaaab...
language(n)

Return the set of factors of size n in that sturmian word of rational or irrational slope.

EXAMPLES:

sage: from slabbe import SturmianSubshift
sage: s = SturmianSubshift(.35355)
sage: sorted(s.language(5))
[word: aabaa, word: aabab, word: abaab, word: ababa, word: baaba, word: babaa]
sage: len(_)
6
sage: s = SturmianSubshift(1/golden_ratio^2)
sage: sorted(s.language(0))
[word: ]
sage: sorted(s.language(1))
[word: a, word: b]
sage: sorted(s.language(2))
[word: aa, word: ab, word: ba]

Rational slope:

sage: s = SturmianSubshift(1/4)
sage: sorted(s.language(10))
[word: aaaabaaaba, word: aaabaaaaba, word: aaabaaabaa, word: aabaaaabaa, 
 word: aabaaabaaa, word: abaaaabaaa, word: abaaabaaaa, word: abaaabaaab,
 word: baaaabaaab, word: baaabaaaab, word: baaabaaaba]
sage: len(_)
11
lexicographically_maximal_factor(n, check=False)

EXAMPLES:

sage: from slabbe import SturmianSubshift
sage: s = SturmianSubshift(.35355)
sage: s.lexicographically_maximal_factor(10)
word: babaabaaba
sage: s.lexicographically_maximal_factor(10, check=True)
word: babaabaaba
sage: s.lexicographically_maximal_factor(100, check=True)
word: babaabaabaabaababaabaabaabaabaababaabaab...
lexicographically_minimal_factor(n, check=False)

EXAMPLES:

sage: from slabbe import SturmianSubshift
sage: s = SturmianSubshift(.35355)
sage: s.lexicographically_minimal_factor(10)
word: aabaabaaba
sage: s.lexicographically_minimal_factor(10, check=True)
word: aabaabaaba
sage: s.lexicographically_minimal_factor(100, check=True)
word: aabaabaabaabaababaabaabaabaabaababaabaab...
random_factor(n)

EXAMPLES:

sage: from slabbe import SturmianSubshift
sage: s = SturmianSubshift(.35355)
sage: s.random_factor(5) # random
word: babaa
sage: s.random_factor(5) # random
word: aabab