Common words#
AUTHORS:
Franco Saliola (2008-12-17): merged into sage
Sébastien Labbé (2008-12-17): merged into sage
Arnaud Bergeron (2008-12-17): merged into sage
Amy Glen (2008-12-17): merged into sage
Sébastien Labbé (2009-12-19): Added S-adic words (github issue #7543)
USE:
To see a list of all word constructors, type words.
and then press
the Tab key. The documentation for each constructor includes
information about each word, which provides a useful reference.
REFERENCES:
B. Adamczewski, J. Cassaigne, On the transcendence of real numbers with a regular expansion, J. Number Theory 103 (2003) 27–37.
A. Blondin-Massé, S. Brlek, A. Glen, and S. Labbé. On the critical exponent of generalized Thue-Morse words. Discrete Math. Theor. Comput. Sci. 9 (1):293–304, 2007.
A. Blondin-Massé, S. Brlek, A. Garon, and S. Labbé. Christoffel and Fibonacci Tiles, DGCI 2009, Montreal, to appear in LNCS.
M. Lothaire, Algebraic Combinatorics On Words, vol. 90 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, U.K., 2002.
Pytheas Fogg, https://www.lirmm.fr/arith/wiki/PytheasFogg/S-adiques.
EXAMPLES:
sage: t = words.ThueMorseWord(); t
word: 0110100110010110100101100110100110010110...
- class sage.combinat.words.word_generators.LowerChristoffelWord(p, q, alphabet=(0, 1), algorithm='cf')#
Bases:
FiniteWord_list
Returns the lower Christoffel word of slope \(p/q\), where \(p\) and \(q\) are relatively prime non-negative integers, over the given two-letter alphabet.
The Christoffel word of slope `p/q` is obtained from the Cayley graph of \(\ZZ/(p+q)\ZZ\) with generator \(q\) as follows. If \(u \rightarrow v\) is an edge in the Cayley graph, then \(v = u + p \mod{p+q}\). Label the edge \(u \rightarrow v\) by
alphabet[1]
if \(u < v\) andalphabet[0]
otherwise. The Christoffel word is the word obtained by reading the edge labels along the cycle beginning from 0.EXAMPLES:
sage: words.LowerChristoffelWord(4,7) word: 00100100101
sage: words.LowerChristoffelWord(4,7,alphabet='ab') word: aabaabaabab
- markoff_number()#
Return the Markoff number associated to the Christoffel word
self
.The Markoff number of a Christoffel word \(w\) is \(trace(M(w))/3\), where \(M(w)\) is the \(2\times 2\) matrix obtained by applying the morphism: 0 -> matrix(2,[2,1,1,1]) 1 -> matrix(2,[5,2,2,1])
EXAMPLES:
sage: w0 = words.LowerChristoffelWord(4,7) sage: w1, w2 = w0.standard_factorization() sage: (m0,m1,m2) = (w.markoff_number() for w in (w0,w1,w2)) # optional - sage.modules sage: (m0,m1,m2) # optional - sage.modules (294685, 13, 7561) sage: m0**2 + m1**2 + m2**2 == 3*m0*m1*m2 # optional - sage.modules True
- standard_factorization()#
Returns the standard factorization of the Christoffel word
self
.The standard factorization of a Christoffel word \(w\) is the unique factorization of \(w\) into two Christoffel words.
EXAMPLES:
sage: w = words.LowerChristoffelWord(5,9) sage: w word: 00100100100101 sage: w1, w2 = w.standard_factorization() sage: w1 word: 001 sage: w2 word: 00100100101
sage: w = words.LowerChristoffelWord(51,37) sage: w1, w2 = w.standard_factorization() sage: w1 word: 0101011010101101011 sage: w2 word: 0101011010101101011010101101010110101101... sage: w1 * w2 == w True
- class sage.combinat.words.word_generators.WordGenerator#
Bases:
object
Constructor of several famous words.
EXAMPLES:
sage: words.ThueMorseWord() word: 0110100110010110100101100110100110010110...
sage: words.FibonacciWord() word: 0100101001001010010100100101001001010010...
sage: words.ChristoffelWord(5, 8) word: 0010010100101
sage: words.RandomWord(10, 4) # not tested random word: 1311131221
sage: words.CodingOfRotationWord(alpha=0.618, beta=0.618) word: 1010110101101101011010110110101101101011...
sage: tm = WordMorphism('a->ab,b->ba') sage: fib = WordMorphism('a->ab,b->a') sage: tmword = words.ThueMorseWord([0, 1]) sage: from itertools import repeat sage: words.s_adic(tmword, repeat('a'), {0:tm, 1:fib}) word: abbaababbaabbaabbaababbaababbaabbaababba...
Note
To see a list of all word constructors, type
words.
and then hit the Tab key. The documentation for each constructor includes information about each word, which provides a useful reference.- BaumSweetWord()#
Returns the Baum-Sweet Word.
The Baum-Sweet Sequence is an infinite word over the alphabet \(\{0,1\}\) defined by the following string substitution rules:
\(00 \rightarrow 0000\)
\(01 \rightarrow 1001\)
\(10 \rightarrow 0100\)
\(11 \rightarrow 1101\)
The substitution rule above can be considered as a morphism on the submonoid of \(\{0,1\}\) generated by \(\{00,01,10,11\}\) (which is a free monoid on these generators).
It is also defined as the concatenation of the terms from the Baum-Sweet Sequence:
\[\begin{split}b_n = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } m \text{ is even} \\ b_{\frac{m-1}{2}}, & \text{if } m \text{ is odd} \end{cases}\end{split}\]where \(n=m4^k\) and \(m\) is not divisible by 4 if \(m \neq 0\).
The individual terms of the Baum-Sweet Sequence are also given by:
\[\begin{split}b_n = \begin{cases} 1, & \text{if the binary representation of} n \text{ contains no block of consecutive 0's of odd length}\\ 0, & \text{otherwise}\\ \end{cases}\\\end{split}\]for \(n > 0\) with \(b_0 = 1\).
For more information see: Wikipedia article Baum-Sweet_sequence.
EXAMPLES:
Baum-Sweet Word:
sage: w = words.BaumSweetWord(); w word: 1101100101001001100100000100100101001001...
Block Definition:
sage: w = words.BaumSweetWord() sage: f = lambda n: '1' if all(len(x)%2==0 for x in bin(n)[2:].split('1')) else '0' sage: all(f(i) == w[i] for i in range(1,100)) True
- CharacteristicSturmianWord(slope, alphabet=(0, 1), bits=None)#
Returns the characteristic Sturmian word (also called standard Sturmian word) of given slope.
Over a binary alphabet \(\{a,b\}\), the characteristic Sturmian word \(c_\alpha\) of irrational slope \(\alpha\) is the infinite word satisfying \(s_{\alpha,0} = ac_\alpha\) and \(s'_{\alpha,0} = bc_\alpha\), where \(s_{\alpha,0}\) and \(s'_{\alpha,0}\) are respectively the lower and upper mechanical words with slope \(\alpha\) and intercept \(0\). Equivalently, for irrational \(\alpha\), \(c_\alpha = s_{\alpha,\alpha} = s'_{\alpha,\alpha}\).
Let \(\alpha = [0, d_1 + 1, d_2, d_3, \ldots]\) be the continued fraction expansion of \(\alpha\). It has been shown that the characteristic Sturmian word of slope \(\alpha\) is also the limit of the sequence: \(s_0 = b, s_1 = a, \ldots, s_{n+1} = s_n^{d_n} s_{n-1}\) for \(n > 0\).
See Section 2.1 of [Loth02] for more details.
INPUT:
slope
– the slope of the word. It can be one of the following:real number in \(]0, 1[\)
iterable over the continued fraction expansion of a real number in \(]0, 1[\)
alphabet
– any container of length two that is suitable to build an instance of OrderedAlphabet (list, tuple, str, …)bits
– integer (optional and considered only ifslope
is a real number) the number of bits to consider when computing the continued fraction.
OUTPUT:
word
ALGORITHM:
Let \([0, d_1 + 1, d_2, d_3, \ldots]\) be the continued fraction expansion of \(\alpha\). Then, the characteristic Sturmian word of slope \(\alpha\) is the limit of the sequence: \(s_0 = b\), \(s_1 = a\) and \(s_{n+1} = s_n^{d_n} s_{n-1}\) for \(n > 0\).
EXAMPLES:
From real slope:
sage: words.CharacteristicSturmianWord(1/golden_ratio^2) # optional - sage.symbolic word: 0100101001001010010100100101001001010010... sage: words.CharacteristicSturmianWord(4/5) word: 11110 sage: words.CharacteristicSturmianWord(5/14) word: 01001001001001 sage: words.CharacteristicSturmianWord(pi - 3) # optional - sage.symbolic word: 0000001000000100000010000001000000100000...
From an iterator of the continued fraction expansion of a real:
sage: def cf(): ....: yield 0 ....: yield 2 ....: while True: yield 1 sage: F = words.CharacteristicSturmianWord(cf()); F word: 0100101001001010010100100101001001010010... sage: Fib = words.FibonacciWord(); Fib word: 0100101001001010010100100101001001010010... sage: F[:10000] == Fib[:10000] True
The alphabet may be specified:
sage: words.CharacteristicSturmianWord(cf(), 'rs') word: rsrrsrsrrsrrsrsrrsrsrrsrrsrsrrsrrsrsrrsr...
The characteristic sturmian word of slope \((\sqrt{3}-1)/2\):
sage: words.CharacteristicSturmianWord((sqrt(3)-1)/2) # optional - sage.symbolic word: 0100100101001001001010010010010100100101...
The same word defined from the continued fraction expansion of \((\sqrt{3}-1)/2\):
sage: from itertools import cycle, chain sage: it = chain([0], cycle([2, 1])) sage: words.CharacteristicSturmianWord(it) word: 0100100101001001001010010010010100100101...
The first terms of the standard sequence of the characteristic sturmian word of slope \((\sqrt{3}-1)/2\):
sage: words.CharacteristicSturmianWord([0,2]) word: 01 sage: words.CharacteristicSturmianWord([0,2,1]) word: 010 sage: words.CharacteristicSturmianWord([0,2,1,2]) word: 01001001 sage: words.CharacteristicSturmianWord([0,2,1,2,1]) word: 01001001010 sage: words.CharacteristicSturmianWord([0,2,1,2,1,2]) word: 010010010100100100101001001001 sage: words.CharacteristicSturmianWord([0,2,1,2,1,2,1]) word: 0100100101001001001010010010010100100101...
- ChristoffelWord#
alias of
LowerChristoffelWord
- CodingOfRotationWord(alpha, beta, x=0, alphabet=(0, 1))#
Returns the infinite word obtained from the coding of rotation of parameters \((\alpha,\beta, x)\) over the given two-letter alphabet.
The coding of rotation corresponding to the parameters \((\alpha,\beta, x)\) is the symbolic sequence \(u = (u_n)_{n\geq 0}\) defined over the binary alphabet \(\{0, 1\}\) by \(u_n = 1\) if \(x+n\alpha\in[0, \beta[\) and \(u_n = 0\) otherwise. See [AC03].
EXAMPLES:
sage: alpha = 0.45 sage: beta = 0.48 sage: words.CodingOfRotationWord(0.45, 0.48) word: 1101010101001010101011010101010010101010...
sage: words.CodingOfRotationWord(0.45, 0.48, alphabet='xy') word: yyxyxyxyxyxxyxyxyxyxyyxyxyxyxyxxyxyxyxyx...
- FibonacciWord(alphabet=(0, 1), construction_method='recursive')#
Returns the Fibonacci word on the given two-letter alphabet.
INPUT:
alphabet
– any container of length two that is suitable to build an instance of OrderedAlphabet (list, tuple, str, …)construction_method
– can be any of the following: “recursive”, “fixed point”, “function” (see below for definitions).
Recursive construction: the Fibonacci word is the limit of the following sequence of words: \(S_0 = 0\), \(S_1 = 01\), \(S_n = S_{n-1} S_{n-2}\) for \(n \geq 2\).
Fixed point construction: the Fibonacci word is the fixed point of the morphism: \(0 \mapsto 01\) and \(1 \mapsto 0\). Hence, it can be constructed by the following read-write process:
beginning at the first letter of \(01\),
if the next letter is \(0\), append \(01\) to the word;
if the next letter is \(1\), append \(1\) to the word;
move to the next letter of the word.
Function: Over the alphabet \(\{1, 2\}\), the n-th letter of the Fibonacci word is \(\lfloor (n+2) \varphi \rfloor - \lfloor (n+1) \varphi \rfloor\) where \(\varphi=(1+\sqrt{5})/2\) is the golden ratio.
EXAMPLES:
sage: w = words.FibonacciWord(construction_method="recursive"); w word: 0100101001001010010100100101001001010010...
sage: v = words.FibonacciWord(construction_method="recursive", alphabet='ab'); v word: abaababaabaababaababaabaababaabaababaaba...
sage: u = words.FibonacciWord(construction_method="fixed point"); u word: 0100101001001010010100100101001001010010...
sage: words.FibonacciWord(construction_method="fixed point", alphabet=[4, 1]) word: 4144141441441414414144144141441441414414...
sage: words.FibonacciWord([0,1], 'function') # optional - sage.symbolic word: 0100101001001010010100100101001001010010... sage: words.FibonacciWord('ab', 'function') # optional - sage.symbolic word: abaababaabaababaababaabaababaabaababaaba...
- FixedPointOfMorphism(morphism, first_letter)#
Returns the fixed point of the morphism beginning with
first_letter
.A fixed point of a morphism \(\varphi\) is a word \(w\) such that \(\varphi(w) = w\).
INPUT:
morphism
– endomorphism prolongable onfirst_letter
. It must be something that WordMorphism’s constructor understands (dict, str, …).first_letter
– the first letter of the fixed point
OUTPUT:
The fixed point of the morphism beginning with
first_letter
EXAMPLES:
sage: mu = {0:[0,1], 1:[1,0]} sage: tm = words.FixedPointOfMorphism(mu,0); tm word: 0110100110010110100101100110100110010110... sage: TM = words.ThueMorseWord() sage: tm[:1000] == TM[:1000] # optional - sage.modules True
sage: mu = {0:[0,1], 1:[0]} sage: f = words.FixedPointOfMorphism(mu,0); f word: 0100101001001010010100100101001001010010... sage: F = words.FibonacciWord(); F word: 0100101001001010010100100101001001010010... sage: f[:1000] == F[:1000] # optional - sage.modules True
sage: fp = words.FixedPointOfMorphism('a->abc,b->,c->','a'); fp word: abc
- KolakoskiWord(alphabet=(1, 2))#
Returns the Kolakoski word over the given alphabet and starting with the first letter of the alphabet.
Let \(A = \{a,b\}\) be an alphabet, where \(a\) and \(b\) are two distinct positive integers. The Kolakoski word \(K_{a,b}\) over \(A\) and starting with \(a\) is the unique infinite word \(w\) such that \(w = \Delta(w)\), where \(\Delta(w)\) is the word encoding the runs of \(w\) (see
delta()
method on words for more details).Note that \(K_{a,b} \neq K_{b,a}\). On the other hand, the words \(K_{a,b}\) and \(K_{b,a}\) are the unique two words over \(A\) that are fixed by \(\Delta\).
Also note that the Kolakoski word is also known as the Oldenburger word.
INPUT:
alphabet
- (default: (1,2)) an iterable of two positive integers
OUTPUT:
infinite word
EXAMPLES:
The usual Kolakoski word:
sage: w = words.KolakoskiWord() sage: w word: 1221121221221121122121121221121121221221... sage: w.delta() word: 1221121221221121122121121221121121221221...
The other Kolakoski word on the same alphabet:
sage: w = words.KolakoskiWord(alphabet = (2,1)) sage: w word: 2211212212211211221211212211211212212211... sage: w.delta() word: 2211212212211211221211212211211212212211...
It is naturally generalized to any two integers alphabet:
sage: w = words.KolakoskiWord(alphabet = (2,5)) sage: w word: 2255222225555522552255225555522222555552... sage: w.delta() word: 2255222225555522552255225555522222555552...
REFERENCES:
[Kolakoski66]William Kolakoski, proposal 5304, American Mathematical Monthly 72 (1965), 674; for a partial solution, see “Self Generating Runs,” by Necdet Üçoluk, Amer. Math. Mon. 73 (1966), 681-2.
- LowerChristoffelWord#
alias of
LowerChristoffelWord
- LowerMechanicalWord(alpha, rho=0, alphabet=None)#
Returns the lower mechanical word with slope \(\alpha\) and intercept \(\rho\)
The lower mechanical word \(s_{\alpha,\rho}\) with slope \(\alpha\) and intercept \(\rho\) is defined by \(s_{\alpha,\rho}(n) = \lfloor\alpha(n+1) + \rho\rfloor - \lfloor\alpha n + \rho\rfloor\). [Loth02]
INPUT:
alpha
– real number such that \(0 \leq\alpha\leq 1\)rho
– real number (optional, default: 0)alphabet
– iterable of two elements orNone
(optional, default:None
)
OUTPUT:
infinite word
EXAMPLES:
sage: words.LowerMechanicalWord(1/golden_ratio^2) # optional - sage.symbolic word: 0010010100100101001010010010100100101001... sage: words.LowerMechanicalWord(1/5) # optional - sage.symbolic word: 0000100001000010000100001000010000100001... sage: words.LowerMechanicalWord(1/pi) # optional - sage.symbolic word: 0001001001001001001001000100100100100100...
- MinimalSmoothPrefix(n)#
This function finds and returns the minimal smooth prefix of length
n
.See [BMP2007] for a definition.
INPUT:
n
– the desired length of the prefix
OUTPUT:
word – the prefix
Note
Be patient, this function can take a really long time if asked for a large prefix.
EXAMPLES:
sage: words.MinimalSmoothPrefix(10) word: 1212212112
- PalindromicDefectWord(k=1, alphabet='ab')#
Return the finite word \(w = a b^k a b^{k-1} a a b^{k-1} a b^{k} a\).
As described by Brlek, Hamel, Nivat and Reutenauer in [BHNR2004], this finite word \(w\) is such that the infinite periodic word \(w^{\omega}\) has palindromic defect
k
.INPUT:
k
– positive integer (optional, default: 1)alphabet
– iterable (optional, default:'ab'
) of size two
OUTPUT:
finite word
EXAMPLES:
sage: words.PalindromicDefectWord(10) word: abbbbbbbbbbabbbbbbbbbaabbbbbbbbbabbbbbbb...
sage: w = words.PalindromicDefectWord(3) sage: w word: abbbabbaabbabbba sage: w.defect() 0 sage: (w^2).defect() 3 sage: (w^3).defect() 3
On other alphabets:
sage: words.PalindromicDefectWord(3, alphabet='cd') word: cdddcddccddcdddc sage: words.PalindromicDefectWord(3, alphabet=['c', 3]) word: c333c33cc33c333c
- RandomWord(n, m=2, alphabet=None)#
Return a random word of length \(n\) over the given \(m\)-letter alphabet.
INPUT:
n
- integer, the length of the wordm
- integer (default 2), the size of the output alphabetalphabet
- (default is \(\{0,1,...,m-1\}\)) any container of length m that is suitable to build an instance of OrderedAlphabet (list, tuple, str, …)
EXAMPLES:
sage: words.RandomWord(10) # random results word: 0110100101 sage: words.RandomWord(10, 4) # random results word: 0322313320 sage: words.RandomWord(100, 7) # random results word: 2630644023642516442650025611300034413310... sage: words.RandomWord(100, 7, range(-3,4)) # random results word: 1,3,-1,-1,3,2,2,0,1,-2,1,-1,-3,-2,2,0,3,0,-3,0,3,0,-2,-2,2,0,1,-3,2,-2,-2,2,0,2,1,-2,-3,-2,-1,0,... sage: words.RandomWord(100, 5, "abcde") # random results word: acebeaaccdbedbbbdeadeebbdeeebeaaacbadaac... sage: words.RandomWord(17, 5, "abcde") # random results word: dcacbbecbddebaadd
- StandardEpisturmianWord(directive_word)#
Returns the standard episturmian word (or epistandard word) directed by directive_word. Over a 2-letter alphabet, this function gives characteristic Sturmian words.
An infinite word \(w\) over a finite alphabet \(A\) is said to be standard episturmian (or epistandard) iff there exists an infinite word \(x_1x_2x_3\cdots\) over \(A\) (called the directive word of \(w\)) such that \(w\) is the limit as \(n\) goes to infinity of \(Pal(x_1\cdots x_n)\), where \(Pal\) is the iterated palindromic closure function.
Note that an infinite word is episturmian if it has the same set of factors as some epistandard word.
See for instance [DJP2001], [JP2002], and [GJ2007].
INPUT:
directive_word
- an infinite word or a period of a periodic infinite word
EXAMPLES:
sage: Fibonacci = words.StandardEpisturmianWord(Words('ab')('ab')); Fibonacci word: abaababaabaababaababaabaababaabaababaaba... sage: Tribonacci = words.StandardEpisturmianWord(Words('abc')('abc')); Tribonacci word: abacabaabacababacabaabacabacabaabacababa... sage: S = words.StandardEpisturmianWord(Words('abcd')('aabcabada')); S word: aabaacaabaaabaacaabaabaacaabaaabaacaabaa... sage: S = words.StandardEpisturmianWord(Fibonacci); S word: abaabaababaabaabaababaabaababaabaabaabab... sage: S[:25] word: abaabaababaabaabaababaaba sage: S = words.StandardEpisturmianWord(Tribonacci); S word: abaabacabaabaabacabaababaabacabaabaabaca... sage: words.StandardEpisturmianWord(123) Traceback (most recent call last): ... TypeError: directive_word is not a word, so it cannot be used to build an episturmian word sage: words.StandardEpisturmianWord(Words('ab')) Traceback (most recent call last): ... TypeError: directive_word is not a word, so it cannot be used to build an episturmian word
- ThueMorseWord(alphabet=(0, 1), base=2)#
Returns the (Generalized) Thue-Morse word over the given alphabet.
There are several ways to define the Thue-Morse word \(t\). We use the following definition: \(t[n]\) is the sum modulo \(m\) of the digits in the given base expansion of \(n\).
See [BmBGL07], [Brlek89], and [MH38].
INPUT:
alphabet
- (default: (0, 1) ) any container that is suitable to build an instance of OrderedAlphabet (list, tuple, str, …)base
- an integer (default : 2) greater or equal to 2
EXAMPLES:
Thue-Morse word:
sage: t = words.ThueMorseWord(); t word: 0110100110010110100101100110100110010110...
Thue-Morse word on other alphabets:
sage: t = words.ThueMorseWord('ab'); t word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: t = words.ThueMorseWord(['L1', 'L2']) sage: t[:8] word: L1,L2,L2,L1,L2,L1,L1,L2
Generalized Thue Morse word:
sage: words.ThueMorseWord(alphabet=(0,1,2), base=2) word: 0112122012202001122020012001011212202001... sage: t = words.ThueMorseWord(alphabet=(0,1,2), base=5); t word: 0120112012201200120112012120122012001201... sage: t[100:130].critical_exponent() 10/3
REFERENCES:
- UpperChristoffelWord(p, q, alphabet=(0, 1))#
Returns the upper Christoffel word of slope \(p/q\), where \(p\) and \(q\) are relatively prime non-negative integers, over the given alphabet.
The upper Christoffel word of slope `p/q` is equal to the reversal of the lower Christoffel word of slope \(p/q\). Equivalently, if \(xuy\) is the lower Christoffel word of slope \(p/q\), where \(x\) and \(y\) are letters, then \(yux\) is the upper Christoffel word of slope \(p/q\) (because \(u\) is a palindrome).
INPUT:
alphabet
- any container of length two that is suitable to build an instance of OrderedAlphabet (list, tuple, str, …)
EXAMPLES:
sage: words.UpperChristoffelWord(1,0) word: 1
sage: words.UpperChristoffelWord(0,1) word: 0
sage: words.UpperChristoffelWord(1,1) word: 10
sage: words.UpperChristoffelWord(4,7) word: 10100100100
- UpperMechanicalWord(alpha, rho=0, alphabet=None)#
Returns the upper mechanical word with slope \(\alpha\) and intercept \(\rho\)
The upper mechanical word \(s'_{\alpha,\rho}\) with slope \(\alpha\) and intercept \(\rho\) is defined by \(s'_{\alpha,\rho}(n) = \lceil\alpha(n+1) + \rho\rceil - \lceil\alpha n + \rho\rceil\). [Loth02]
INPUT:
alpha
– real number such that \(0 \leq\alpha\leq 1\)rho
– real number (optional, default: 0)alphabet
– iterable of two elements orNone
(optional, default:None
)
OUTPUT:
infinite word
EXAMPLES:
sage: words.UpperMechanicalWord(1/golden_ratio^2) # optional - sage.symbolic word: 1010010100100101001010010010100100101001... sage: words.UpperMechanicalWord(1/5) # optional - sage.symbolic word: 1000010000100001000010000100001000010000... sage: words.UpperMechanicalWord(1/pi) # optional - sage.symbolic word: 1001001001001001001001000100100100100100...
- dual_fibonacci_tile(n)#
Returns the \(n\)-th dual Fibonacci Tile [BmBGL09].
EXAMPLES:
sage: for i in range(4): words.dual_fibonacci_tile(i) # optional - sage.modules Path: 3210 Path: 32123032301030121012 Path: 3212303230103230321232101232123032123210... Path: 3212303230103230321232101232123032123210...
- fibonacci_tile(n)#
Returns the \(n\)-th Fibonacci Tile [BmBGL09].
EXAMPLES:
sage: for i in range(3): words.fibonacci_tile(i) # optional - sage.modules Path: 3210 Path: 323030101212 Path: 3230301030323212323032321210121232121010...
- s_adic(sequence, letters, morphisms=None)#
Returns the \(s\)-adic infinite word obtained from a sequence of morphisms applied on a letter.
DEFINITION (from [Fogg]):
Let \(w\) be a infinite word over an alphabet \(A = A_0\). A standard representation of \(w\) is obtained from a sequence of substitutions \(\sigma_k : A_{k+1} \to A_k\) and a sequence of letters \(a_k \in A_k\) such that:
\[\lim_{k\to\infty} \sigma_0 \circ \sigma_1 \circ \cdots \sigma_k(a_k).\]Given a set of substitutions \(S\), we say that the representation is \(S\)-adic standard if the substitutions are chosen in \(S\).
INPUT:
sequence
- An iterable sequence of indices or of morphisms. It may be finite or infinite. Ifsequence
is infinite, the image of the \((i+1)\)-th letter under the \((i+1)\)-th morphism must start with the \(i\)-th letter.letters
- A letter or a sequence of letters.morphisms
- dict, list, callable orNone
(optional, defaultNone
) an object that maps indices to morphisms. IfNone
, thensequence
must consist of morphisms.
OUTPUT:
A word.
EXAMPLES:
Let us define three morphisms and compute the first nested successive prefixes of the \(s\)-adic word:
sage: m1 = WordMorphism('e->gh,f->hg') sage: m2 = WordMorphism('c->ef,d->e') sage: m3 = WordMorphism('a->cd,b->dc') sage: words.s_adic([m1],'e') word: gh sage: words.s_adic([m1,m2],'ec') word: ghhg sage: words.s_adic([m1,m2,m3],'eca') word: ghhggh
When the given sequence of morphism is finite, one may simply give the last letter, i.e.
'a'
, instead of giving all of them, i.e.'eca'
:sage: words.s_adic([m1,m2,m3],'a') word: ghhggh sage: words.s_adic([m1,m2,m3],'b') word: ghghhg
If the letters don’t satisfy the hypothesis of the algorithm (nested prefixes), an error is raised:
sage: words.s_adic([m1,m2,m3],'ecb') Traceback (most recent call last): ... ValueError: the hypothesis of the algorithm used is not satisfied; the image of the 3-th letter (=b) under the 3-th morphism (=a->cd, b->dc) should start with the 2-th letter (=c)
Let’s define the Thue-Morse morphism and the Fibonacci morphism which will be used below to illustrate more examples and let’s import the
repeat
tool from theitertools
:sage: tm = WordMorphism('a->ab,b->ba') sage: fib = WordMorphism('a->ab,b->a') sage: from itertools import repeat
Two trivial examples of infinite \(s\)-adic words:
sage: words.s_adic(repeat(tm),repeat('a')) word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: words.s_adic(repeat(fib),repeat('a')) word: abaababaabaababaababaabaababaabaababaaba...
A less trivial infinite \(s\)-adic word:
sage: D = {4:tm,5:fib} sage: tmword = words.ThueMorseWord([4,5]) sage: it = (D[a] for a in tmword) sage: words.s_adic(it, repeat('a')) word: abbaababbaabbaabbaababbaababbaabbaababba...
The same thing using a sequence of indices:
sage: tmword = words.ThueMorseWord([0,1]) sage: words.s_adic(tmword, repeat('a'), [tm,fib]) word: abbaababbaabbaabbaababbaababbaabbaababba...
The correspondence of the indices may be given as a dict:
sage: words.s_adic(tmword, repeat('a'), {0:tm,1:fib}) word: abbaababbaabbaabbaababbaababbaabbaababba...
because dict are more versatile for indices:
sage: tmwordTF = words.ThueMorseWord('TF') sage: words.s_adic(tmwordTF, repeat('a'), {'T':tm,'F':fib}) word: abbaababbaabbaabbaababbaababbaabbaababba...
or by a callable:
sage: f = lambda n: tm if n == 0 else fib sage: words.s_adic(words.ThueMorseWord(), repeat('a'), f) word: abbaababbaabbaabbaababbaababbaabbaababba...
Random infinite \(s\)-adic words:
sage: from sage.misc.prandom import randint sage: def it(): ....: while True: yield randint(0,1) sage: words.s_adic(it(), repeat('a'), [tm,fib]) # random word: abbaabababbaababbaabbaababbaabababbaabba... sage: words.s_adic(it(), repeat('a'), [tm,fib]) # random word: abbaababbaabbaababbaababbaabbaababbaabba... sage: words.s_adic(it(), repeat('a'), [tm,fib]) # random word: abaaababaabaabaaababaabaaababaaababaabaa...
An example where the sequences cycle on two morphisms and two letters:
sage: G = WordMorphism('a->cd,b->dc') sage: H = WordMorphism('c->ab,d->ba') sage: from itertools import cycle sage: words.s_adic([G,H],'ac') word: cddc sage: words.s_adic(cycle([G,H]),cycle('ac')) word: cddcdccddccdcddcdccdcddccddcdccddccdcddc...
The morphism \(\sigma: a\mapsto ba, b\mapsto b\) can’t satisfy the hypothesis of the nested prefixes, but one may compute arbitrarily long finite words having the limit \(\sigma^\omega(a)\):
sage: sigma = WordMorphism('a->ba,b->b') sage: words.s_adic(repeat(sigma),repeat('a')) Traceback (most recent call last): ... ValueError: the hypothesis of the algorithm used is not satisfied; the image of the 2-th letter (=a) under the 2-th morphism (=a->ba, b->b) should start with the 1-th letter (=a) sage: words.s_adic([sigma],'a') word: ba sage: words.s_adic([sigma,sigma],'a') word: bba sage: words.s_adic([sigma]*3,'a') word: bbba sage: words.s_adic([sigma]*4,'a') word: bbbba sage: words.s_adic([sigma]*5,'a') word: bbbbba sage: words.s_adic([sigma]*6,'a') word: bbbbbba sage: words.s_adic([sigma]*7,'a') word: bbbbbbba
The following examples illustrates an \(S\)-adic word defined over an infinite set \(S\) of morphisms \(x_h\):
sage: x = lambda h:WordMorphism({1:[2],2:[3]+[1]*(h+1),3:[3]+[1]*h}) sage: for h in [0,1,2,3]: ....: print("{} {}".format(h, x(h))) 0 1->2, 2->31, 3->3 1 1->2, 2->311, 3->31 2 1->2, 2->3111, 3->311 3 1->2, 2->31111, 3->3111 sage: w = Word(lambda n : valuation(n+1, 2) ); w word: 0102010301020104010201030102010501020103... sage: s = words.s_adic(w, repeat(3), x); s word: 3232232232322322322323223223232232232232... sage: prefixe = s[:10000] sage: list(map(prefixe.number_of_factors, range(15))) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] sage: [_[i+1] - _[i] for i in range(len(_)-1)] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
AUTHORS:
Sébastien Labbé (2009-12-18): initial version