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 (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...
>>> from sage.all import *
>>> t = words.ThueMorseWord(); t
word: 0110100110010110100101100110100110010110...
- class sage.combinat.words.word_generators.LowerChristoffelWord(p, q, alphabet=(0, 1), algorithm='cf')[source]¶
Bases:
FiniteWord_listReturn the lower Christoffel word of slope \(p/q\), where \(p\) and \(q\) are relatively prime nonnegative 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
>>> from sage.all import * >>> words.LowerChristoffelWord(Integer(4),Integer(7)) word: 00100100101
sage: words.LowerChristoffelWord(4,7,alphabet='ab') word: aabaabaabab
>>> from sage.all import * >>> words.LowerChristoffelWord(Integer(4),Integer(7),alphabet='ab') word: aabaabaabab
- markoff_number()[source]¶
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)) # needs sage.modules sage: (m0,m1,m2) # needs sage.modules (294685, 13, 7561) sage: m0**2 + m1**2 + m2**2 == 3*m0*m1*m2 # needs sage.modules True
>>> from sage.all import * >>> w0 = words.LowerChristoffelWord(Integer(4),Integer(7)) >>> w1, w2 = w0.standard_factorization() >>> (m0,m1,m2) = (w.markoff_number() for w in (w0,w1,w2)) # needs sage.modules >>> (m0,m1,m2) # needs sage.modules (294685, 13, 7561) >>> m0**Integer(2) + m1**Integer(2) + m2**Integer(2) == Integer(3)*m0*m1*m2 # needs sage.modules True
- standard_factorization()[source]¶
Return 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
>>> from sage.all import * >>> w = words.LowerChristoffelWord(Integer(5),Integer(9)) >>> w word: 00100100100101 >>> w1, w2 = w.standard_factorization() >>> w1 word: 001 >>> 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
>>> from sage.all import * >>> w = words.LowerChristoffelWord(Integer(51),Integer(37)) >>> w1, w2 = w.standard_factorization() >>> w1 word: 0101011010101101011 >>> w2 word: 0101011010101101011010101101010110101101... >>> w1 * w2 == w True
- class sage.combinat.words.word_generators.WordGenerator[source]¶
Bases:
objectConstructor of several famous words.
EXAMPLES:
sage: words.ThueMorseWord() word: 0110100110010110100101100110100110010110...
>>> from sage.all import * >>> words.ThueMorseWord() word: 0110100110010110100101100110100110010110...
sage: words.FibonacciWord() word: 0100101001001010010100100101001001010010...
>>> from sage.all import * >>> words.FibonacciWord() word: 0100101001001010010100100101001001010010...
sage: words.ChristoffelWord(5, 8) word: 0010010100101
>>> from sage.all import * >>> words.ChristoffelWord(Integer(5), Integer(8)) word: 0010010100101
sage: words.RandomWord(10, 4) # not tested random word: 1311131221
>>> from sage.all import * >>> words.RandomWord(Integer(10), Integer(4)) # not tested random word: 1311131221
sage: words.CodingOfRotationWord(alpha=0.618, beta=0.618) word: 1010110101101101011010110110101101101011...
>>> from sage.all import * >>> words.CodingOfRotationWord(alpha=RealNumber('0.618'), beta=RealNumber('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...
>>> from sage.all import * >>> tm = WordMorphism('a->ab,b->ba') >>> fib = WordMorphism('a->ab,b->a') >>> tmword = words.ThueMorseWord([Integer(0), Integer(1)]) >>> from itertools import repeat >>> words.s_adic(tmword, repeat('a'), {Integer(0):tm, Integer(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()[source]¶
Return 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 0s 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...
>>> from sage.all import * >>> 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
>>> from sage.all import * >>> w = words.BaumSweetWord() >>> f = lambda n: '1' if all(len(x)%Integer(2)==Integer(0) for x in bin(n)[Integer(2):].split('1')) else '0' >>> all(f(i) == w[i] for i in range(Integer(1),Integer(100))) True
- CharacteristicSturmianWord(slope, alphabet=(0, 1), bits=None)[source]¶
Return 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 ifslopeis 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) # needs sage.symbolic word: 0100101001001010010100100101001001010010... sage: words.CharacteristicSturmianWord(4/5) # needs sage.rings.real_mpfr word: 11110 sage: words.CharacteristicSturmianWord(5/14) # needs sage.rings.real_mpfr word: 01001001001001 sage: words.CharacteristicSturmianWord(pi - 3) # needs sage.symbolic word: 0000001000000100000010000001000000100000...
>>> from sage.all import * >>> words.CharacteristicSturmianWord(Integer(1)/golden_ratio**Integer(2)) # needs sage.symbolic word: 0100101001001010010100100101001001010010... >>> words.CharacteristicSturmianWord(Integer(4)/Integer(5)) # needs sage.rings.real_mpfr word: 11110 >>> words.CharacteristicSturmianWord(Integer(5)/Integer(14)) # needs sage.rings.real_mpfr word: 01001001001001 >>> words.CharacteristicSturmianWord(pi - Integer(3)) # needs 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 # needs sage.rings.real_mpfr word: 0100101001001010010100100101001001010010... sage: Fib = words.FibonacciWord(); Fib word: 0100101001001010010100100101001001010010... sage: F[:10000] == Fib[:10000] # needs sage.rings.real_mpfr True
>>> from sage.all import * >>> def cf(): ... yield Integer(0) ... yield Integer(2) ... while True: yield Integer(1) >>> F = words.CharacteristicSturmianWord(cf()); F # needs sage.rings.real_mpfr word: 0100101001001010010100100101001001010010... >>> Fib = words.FibonacciWord(); Fib word: 0100101001001010010100100101001001010010... >>> F[:Integer(10000)] == Fib[:Integer(10000)] # needs sage.rings.real_mpfr True
The alphabet may be specified:
sage: words.CharacteristicSturmianWord(cf(), 'rs') # needs sage.rings.real_mpfr word: rsrrsrsrrsrrsrsrrsrsrrsrrsrsrrsrrsrsrrsr...
>>> from sage.all import * >>> words.CharacteristicSturmianWord(cf(), 'rs') # needs sage.rings.real_mpfr word: rsrrsrsrrsrrsrsrrsrsrrsrrsrsrrsrrsrsrrsr...
The characteristic sturmian word of slope \((\sqrt{3}-1)/2\):
sage: words.CharacteristicSturmianWord((sqrt(3)-1)/2) # needs sage.symbolic word: 0100100101001001001010010010010100100101...
>>> from sage.all import * >>> words.CharacteristicSturmianWord((sqrt(Integer(3))-Integer(1))/Integer(2)) # needs 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...
>>> from sage.all import * >>> from itertools import cycle, chain >>> it = chain([Integer(0)], cycle([Integer(2), Integer(1)])) >>> 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...
>>> from sage.all import * >>> words.CharacteristicSturmianWord([Integer(0),Integer(2)]) word: 01 >>> words.CharacteristicSturmianWord([Integer(0),Integer(2),Integer(1)]) word: 010 >>> words.CharacteristicSturmianWord([Integer(0),Integer(2),Integer(1),Integer(2)]) word: 01001001 >>> words.CharacteristicSturmianWord([Integer(0),Integer(2),Integer(1),Integer(2),Integer(1)]) word: 01001001010 >>> words.CharacteristicSturmianWord([Integer(0),Integer(2),Integer(1),Integer(2),Integer(1),Integer(2)]) word: 010010010100100100101001001001 >>> words.CharacteristicSturmianWord([Integer(0),Integer(2),Integer(1),Integer(2),Integer(1),Integer(2),Integer(1)]) word: 0100100101001001001010010010010100100101...
- ChristoffelWord[source]¶
alias of
LowerChristoffelWord
- CodingOfRotationWord(alpha, beta, x=0, alphabet=(0, 1))[source]¶
Return 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...
>>> from sage.all import * >>> alpha = RealNumber('0.45') >>> beta = RealNumber('0.48') >>> words.CodingOfRotationWord(RealNumber('0.45'), RealNumber('0.48')) word: 1101010101001010101011010101010010101010...
sage: words.CodingOfRotationWord(0.45, 0.48, alphabet='xy') word: yyxyxyxyxyxxyxyxyxyxyyxyxyxyxyxxyxyxyxyx...
>>> from sage.all import * >>> words.CodingOfRotationWord(RealNumber('0.45'), RealNumber('0.48'), alphabet='xy') word: yyxyxyxyxyxxyxyxyxyxyyxyxyxyxyxxyxyxyxyx...
- FibonacciWord(alphabet=(0, 1), construction_method='recursive')[source]¶
Return 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...
>>> from sage.all import * >>> w = words.FibonacciWord(construction_method='recursive'); w word: 0100101001001010010100100101001001010010...
sage: v = words.FibonacciWord(construction_method='recursive', alphabet='ab'); v word: abaababaabaababaababaabaababaabaababaaba...
>>> from sage.all import * >>> v = words.FibonacciWord(construction_method='recursive', alphabet='ab'); v word: abaababaabaababaababaabaababaabaababaaba...
sage: u = words.FibonacciWord(construction_method="fixed point"); u word: 0100101001001010010100100101001001010010...
>>> from sage.all import * >>> u = words.FibonacciWord(construction_method="fixed point"); u word: 0100101001001010010100100101001001010010...
sage: words.FibonacciWord(construction_method="fixed point", alphabet=[4, 1]) word: 4144141441441414414144144141441441414414...
>>> from sage.all import * >>> words.FibonacciWord(construction_method="fixed point", alphabet=[Integer(4), Integer(1)]) word: 4144141441441414414144144141441441414414...
sage: words.FibonacciWord([0,1], 'function') # needs sage.symbolic word: 0100101001001010010100100101001001010010... sage: words.FibonacciWord('ab', 'function') # needs sage.symbolic word: abaababaabaababaababaabaababaabaababaaba...
>>> from sage.all import * >>> words.FibonacciWord([Integer(0),Integer(1)], 'function') # needs sage.symbolic word: 0100101001001010010100100101001001010010... >>> words.FibonacciWord('ab', 'function') # needs sage.symbolic word: abaababaabaababaababaabaababaabaababaaba...
- FixedPointOfMorphism(morphism, first_letter)[source]¶
Return 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_letterEXAMPLES:
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] # needs sage.modules True
>>> from sage.all import * >>> mu = {Integer(0):[Integer(0),Integer(1)], Integer(1):[Integer(1),Integer(0)]} >>> tm = words.FixedPointOfMorphism(mu,Integer(0)); tm word: 0110100110010110100101100110100110010110... >>> TM = words.ThueMorseWord() >>> tm[:Integer(1000)] == TM[:Integer(1000)] # needs 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] # needs sage.modules True
>>> from sage.all import * >>> mu = {Integer(0):[Integer(0),Integer(1)], Integer(1):[Integer(0)]} >>> f = words.FixedPointOfMorphism(mu,Integer(0)); f word: 0100101001001010010100100101001001010010... >>> F = words.FibonacciWord(); F word: 0100101001001010010100100101001001010010... >>> f[:Integer(1000)] == F[:Integer(1000)] # needs sage.modules True
sage: fp = words.FixedPointOfMorphism('a->abc,b->,c->','a'); fp word: abc
>>> from sage.all import * >>> fp = words.FixedPointOfMorphism('a->abc,b->,c->','a'); fp word: abc
- KolakoskiWord(alphabet=(1, 2))[source]¶
Return 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...
>>> from sage.all import * >>> w = words.KolakoskiWord() >>> w word: 1221121221221121122121121221121121221221... >>> 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...
>>> from sage.all import * >>> w = words.KolakoskiWord(alphabet = (Integer(2),Integer(1))) >>> w word: 2211212212211211221211212211211212212211... >>> 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...
>>> from sage.all import * >>> w = words.KolakoskiWord(alphabet = (Integer(2),Integer(5))) >>> w word: 2255222225555522552255225555522222555552... >>> 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[source]¶
alias of
LowerChristoffelWord
- LowerMechanicalWord(alpha, rho=0, alphabet=None)[source]¶
Return 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 (default: 0)alphabet– iterable of two elements orNone(default:None)
OUTPUT: infinite word
EXAMPLES:
sage: words.LowerMechanicalWord(1/golden_ratio^2) # needs sage.symbolic word: 0010010100100101001010010010100100101001... sage: words.LowerMechanicalWord(1/5) # needs sage.symbolic word: 0000100001000010000100001000010000100001... sage: words.LowerMechanicalWord(1/pi) # needs sage.symbolic word: 0001001001001001001001000100100100100100...
>>> from sage.all import * >>> words.LowerMechanicalWord(Integer(1)/golden_ratio**Integer(2)) # needs sage.symbolic word: 0010010100100101001010010010100100101001... >>> words.LowerMechanicalWord(Integer(1)/Integer(5)) # needs sage.symbolic word: 0000100001000010000100001000010000100001... >>> words.LowerMechanicalWord(Integer(1)/pi) # needs sage.symbolic word: 0001001001001001001001000100100100100100...
- MinimalSmoothPrefix(n)[source]¶
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
>>> from sage.all import * >>> words.MinimalSmoothPrefix(Integer(10)) word: 1212212112
- PalindromicDefectWord(k=1, alphabet='ab')[source]¶
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 (default: 1)alphabet– iterable of size two (default:'ab')
OUTPUT: finite word
EXAMPLES:
sage: words.PalindromicDefectWord(10) word: abbbbbbbbbbabbbbbbbbbaabbbbbbbbbabbbbbbb...
>>> from sage.all import * >>> words.PalindromicDefectWord(Integer(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
>>> from sage.all import * >>> w = words.PalindromicDefectWord(Integer(3)) >>> w word: abbbabbaabbabbba >>> w.defect() 0 >>> (w**Integer(2)).defect() 3 >>> (w**Integer(3)).defect() 3
On other alphabets:
sage: words.PalindromicDefectWord(3, alphabet='cd') word: cdddcddccddcdddc sage: words.PalindromicDefectWord(3, alphabet=['c', 3]) word: c333c33cc33c333c
>>> from sage.all import * >>> words.PalindromicDefectWord(Integer(3), alphabet='cd') word: cdddcddccddcdddc >>> words.PalindromicDefectWord(Integer(3), alphabet=['c', Integer(3)]) word: c333c33cc33c333c
- RandomWord(n, m=2, alphabet=None)[source]¶
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: \(\{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
>>> from sage.all import * >>> words.RandomWord(Integer(10)) # random results word: 0110100101 >>> words.RandomWord(Integer(10), Integer(4)) # random results word: 0322313320 >>> words.RandomWord(Integer(100), Integer(7)) # random results word: 2630644023642516442650025611300034413310... >>> words.RandomWord(Integer(100), Integer(7), range(-Integer(3),Integer(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,... >>> words.RandomWord(Integer(100), Integer(5), "abcde") # random results word: acebeaaccdbedbbbdeadeebbdeeebeaaacbadaac... >>> words.RandomWord(Integer(17), Integer(5), "abcde") # random results word: dcacbbecbddebaadd
- StandardEpisturmianWord(directive_word)[source]¶
Return 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
>>> from sage.all import * >>> Fibonacci = words.StandardEpisturmianWord(Words('ab')('ab')); Fibonacci word: abaababaabaababaababaabaababaabaababaaba... >>> Tribonacci = words.StandardEpisturmianWord(Words('abc')('abc')); Tribonacci word: abacabaabacababacabaabacabacabaabacababa... >>> S = words.StandardEpisturmianWord(Words('abcd')('aabcabada')); S word: aabaacaabaaabaacaabaabaacaabaaabaacaabaa... >>> S = words.StandardEpisturmianWord(Fibonacci); S word: abaabaababaabaabaababaabaababaabaabaabab... >>> S[:Integer(25)] word: abaabaababaabaabaababaaba >>> S = words.StandardEpisturmianWord(Tribonacci); S word: abaabacabaabaabacabaababaabacabaabaabaca... >>> words.StandardEpisturmianWord(Integer(123)) Traceback (most recent call last): ... TypeError: directive_word is not a word, so it cannot be used to build an episturmian word >>> 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)[source]¶
Return 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– integer (default: 2); greater than or equal to 2
EXAMPLES:
Thue-Morse word:
sage: t = words.ThueMorseWord(); t word: 0110100110010110100101100110100110010110...
>>> from sage.all import * >>> t = words.ThueMorseWord(); t word: 0110100110010110100101100110100110010110...
Thue-Morse word on other alphabets:
sage: t = words.ThueMorseWord('ab'); t word: abbabaabbaababbabaababbaabbabaabbaababba...
>>> from sage.all import * >>> 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
>>> from sage.all import * >>> t = words.ThueMorseWord(['L1', 'L2']) >>> t[:Integer(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
>>> from sage.all import * >>> words.ThueMorseWord(alphabet=(Integer(0),Integer(1),Integer(2)), base=Integer(2)) word: 0112122012202001122020012001011212202001... >>> t = words.ThueMorseWord(alphabet=(Integer(0),Integer(1),Integer(2)), base=Integer(5)); t word: 0120112012201200120112012120122012001201... >>> t[Integer(100):Integer(130)].critical_exponent() 10/3
REFERENCES:
- UpperChristoffelWord(p, q, alphabet=(0, 1))[source]¶
Return the upper Christoffel word of slope \(p/q\), where \(p\) and \(q\) are relatively prime nonnegative 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
>>> from sage.all import * >>> words.UpperChristoffelWord(Integer(1),Integer(0)) word: 1
sage: words.UpperChristoffelWord(0,1) word: 0
>>> from sage.all import * >>> words.UpperChristoffelWord(Integer(0),Integer(1)) word: 0
sage: words.UpperChristoffelWord(1,1) word: 10
>>> from sage.all import * >>> words.UpperChristoffelWord(Integer(1),Integer(1)) word: 10
sage: words.UpperChristoffelWord(4,7) word: 10100100100
>>> from sage.all import * >>> words.UpperChristoffelWord(Integer(4),Integer(7)) word: 10100100100
- UpperMechanicalWord(alpha, rho=0, alphabet=None)[source]¶
Return 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 (default: 0)alphabet– iterable of two elements orNone(default:None)
OUTPUT: infinite word
EXAMPLES:
sage: words.UpperMechanicalWord(1/golden_ratio^2) # needs sage.symbolic word: 1010010100100101001010010010100100101001... sage: words.UpperMechanicalWord(1/5) # needs sage.symbolic word: 1000010000100001000010000100001000010000... sage: words.UpperMechanicalWord(1/pi) # needs sage.symbolic word: 1001001001001001001001000100100100100100...
>>> from sage.all import * >>> words.UpperMechanicalWord(Integer(1)/golden_ratio**Integer(2)) # needs sage.symbolic word: 1010010100100101001010010010100100101001... >>> words.UpperMechanicalWord(Integer(1)/Integer(5)) # needs sage.symbolic word: 1000010000100001000010000100001000010000... >>> words.UpperMechanicalWord(Integer(1)/pi) # needs sage.symbolic word: 1001001001001001001001000100100100100100...
- dual_fibonacci_tile(n)[source]¶
Return the \(n\)-th dual Fibonacci Tile [BmBGL09].
EXAMPLES:
sage: for i in range(4): words.dual_fibonacci_tile(i) # needs sage.modules Path: 3210 Path: 32123032301030121012 Path: 3212303230103230321232101232123032123210... Path: 3212303230103230321232101232123032123210...
>>> from sage.all import * >>> for i in range(Integer(4)): words.dual_fibonacci_tile(i) # needs sage.modules Path: 3210 Path: 32123032301030121012 Path: 3212303230103230321232101232123032123210... Path: 3212303230103230321232101232123032123210...
- fibonacci_tile(n)[source]¶
Return the \(n\)-th Fibonacci Tile [BmBGL09].
EXAMPLES:
sage: for i in range(3): words.fibonacci_tile(i) # needs sage.modules Path: 3210 Path: 323030101212 Path: 3230301030323212323032321210121232121010...
>>> from sage.all import * >>> for i in range(Integer(3)): words.fibonacci_tile(i) # needs sage.modules Path: 3210 Path: 323030101212 Path: 3230301030323212323032321210121232121010...
- s_adic(sequence, letters, morphisms=None)[source]¶
Return 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. Ifsequenceis 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 lettersmorphisms– dict, list, callable orNone(default:None) an object that maps indices to morphisms. IfNone, thensequencemust 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
>>> from sage.all import * >>> m1 = WordMorphism('e->gh,f->hg') >>> m2 = WordMorphism('c->ef,d->e') >>> m3 = WordMorphism('a->cd,b->dc') >>> words.s_adic([m1],'e') word: gh >>> words.s_adic([m1,m2],'ec') word: ghhg >>> 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
>>> from sage.all import * >>> words.s_adic([m1,m2,m3],'a') word: ghhggh >>> 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)
>>> from sage.all import * >>> 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
repeattool from theitertools:sage: tm = WordMorphism('a->ab,b->ba') sage: fib = WordMorphism('a->ab,b->a') sage: from itertools import repeat
>>> from sage.all import * >>> tm = WordMorphism('a->ab,b->ba') >>> fib = WordMorphism('a->ab,b->a') >>> from itertools import repeat
Two trivial examples of infinite \(s\)-adic words:
sage: words.s_adic(repeat(tm),repeat('a')) word: abbabaabbaababbabaababbaabbabaabbaababba...
>>> from sage.all import * >>> words.s_adic(repeat(tm),repeat('a')) word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: words.s_adic(repeat(fib),repeat('a')) word: abaababaabaababaababaabaababaabaababaaba...
>>> from sage.all import * >>> 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...
>>> from sage.all import * >>> D = {Integer(4):tm,Integer(5):fib} >>> tmword = words.ThueMorseWord([Integer(4),Integer(5)]) >>> it = (D[a] for a in tmword) >>> 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...
>>> from sage.all import * >>> tmword = words.ThueMorseWord([Integer(0),Integer(1)]) >>> 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...
>>> from sage.all import * >>> words.s_adic(tmword, repeat('a'), {Integer(0):tm,Integer(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...
>>> from sage.all import * >>> tmwordTF = words.ThueMorseWord('TF') >>> 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...
>>> from sage.all import * >>> f = lambda n: tm if n == Integer(0) else fib >>> 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...
>>> from sage.all import * >>> from sage.misc.prandom import randint >>> def it(): ... while True: yield randint(Integer(0),Integer(1)) >>> words.s_adic(it(), repeat('a'), [tm,fib]) # random word: abbaabababbaababbaabbaababbaabababbaabba... >>> words.s_adic(it(), repeat('a'), [tm,fib]) # random word: abbaababbaabbaababbaababbaabbaababbaabba... >>> 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...
>>> from sage.all import * >>> G = WordMorphism('a->cd,b->dc') >>> H = WordMorphism('c->ab,d->ba') >>> from itertools import cycle >>> words.s_adic([G,H],'ac') word: cddc >>> 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
>>> from sage.all import * >>> sigma = WordMorphism('a->ba,b->b') >>> 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) >>> words.s_adic([sigma],'a') word: ba >>> words.s_adic([sigma,sigma],'a') word: bba >>> words.s_adic([sigma]*Integer(3),'a') word: bbba >>> words.s_adic([sigma]*Integer(4),'a') word: bbbba >>> words.s_adic([sigma]*Integer(5),'a') word: bbbbba >>> words.s_adic([sigma]*Integer(6),'a') word: bbbbbba >>> words.s_adic([sigma]*Integer(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]
>>> from sage.all import * >>> x = lambda h:WordMorphism({Integer(1):[Integer(2)],Integer(2):[Integer(3)]+[Integer(1)]*(h+Integer(1)),Integer(3):[Integer(3)]+[Integer(1)]*h}) >>> for h in [Integer(0),Integer(1),Integer(2),Integer(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 >>> w = Word(lambda n : valuation(n+Integer(1), Integer(2)) ); w word: 0102010301020104010201030102010501020103... >>> s = words.s_adic(w, repeat(Integer(3)), x); s word: 3232232232322322322323223223232232232232... >>> prefixe = s[:Integer(10000)] >>> list(map(prefixe.number_of_factors, range(Integer(15)))) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] >>> [_[i+Integer(1)] - _[i] for i in range(len(_)-Integer(1))] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
AUTHORS:
Sébastien Labbé (2009-12-18): initial version