Common words

AUTHORS:

  • Franco Saliola (2008-12-17): merged into sage

  • Sebastien Labbe (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 (trac ticket #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:

AC03

B. Adamczewski, J. Cassaigne, On the transcendence of real numbers with a regular expansion, J. Number Theory 103 (2003) 27–37.

BmBGL07

A. Blondin-Masse, S. Brlek, A. Glen, and S. Labbe. On the critical exponent of generalized Thue-Morse words. Discrete Math. Theor. Comput. Sci. 9 (1):293–304, 2007.

BmBGL09(1,2)

A. Blondin-Masse, S. Brlek, A. Garon, and S. Labbe. Christoffel and Fibonacci Tiles, DGCI 2009, Montreal, to appear in LNCS.

Loth02(1,2,3)

M. Lothaire, Algebraic Combinatorics On Words, vol. 90 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, U.K., 2002.

Fogg

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: sage.combinat.words.word.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\) and alphabet[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()

Returns 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))
sage: (m0,m1,m2)
(294685, 13, 7561)
sage: m0**2 + m1**2 + m2**2 == 3*m0*m1*m2
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 if slope 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)
word: 0100101001001010010100100101001001010010...
sage: words.CharacteristicSturmianWord(4/5)
word: 11110
sage: words.CharacteristicSturmianWord(5/14)
word: 01001001001001
sage: words.CharacteristicSturmianWord(pi-3)
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)
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:

  1. beginning at the first letter of \(01\),

  2. if the next letter is \(0\), append \(01\) to the word;

  3. if the next letter is \(1\), append \(1\) to the word;

  4. 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')
word: 0100101001001010010100100101001001010010...
sage: words.FibonacciWord('ab', 'function')
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 on first_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]
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]
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 or None (optional, default: None)

OUTPUT:

infinite word

EXAMPLES:

sage: words.LowerMechanicalWord(1/golden_ratio^2)
word: 0010010100100101001010010010100100101001...
sage: words.LowerMechanicalWord(1/5)
word: 0000100001000010000100001000010000100001...
sage: words.LowerMechanicalWord(1/pi)
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 word

  • m - integer (default 2), the size of the output alphabet

  • alphabet - (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:

Brlek89

Brlek, S. 1989. «Enumeration of the factors in the Thue-Morse word», Discrete Appl. Math., vol. 24, p. 83–96.

MH38

Morse, M., et G. A. Hedlund. 1938. «Symbolic dynamics», American Journal of Mathematics, vol. 60, p. 815–866.

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 or None (optional, default: None)

OUTPUT:

infinite word

EXAMPLES:

sage: words.UpperMechanicalWord(1/golden_ratio^2)
word: 1010010100100101001010010010100100101001...
sage: words.UpperMechanicalWord(1/5)
word: 1000010000100001000010000100001000010000...
sage: words.UpperMechanicalWord(1/pi)
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)
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)
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. If sequence 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 or None (optional, default None) an object that maps indices to morphisms. If None, then sequence 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 the itertools:

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 correspondance 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:

  • Sebastien Labbe (2009-12-18): initial version