A collection of constructors of 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
- Sebastien Labbe (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
, where
and
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
with generator
as follows. If
is an edge in the Cayley graph, then
. Label the edge
by
alphabet[1]
ifand
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
TESTS:
sage: words.LowerChristoffelWord(1,0) word: 1 sage: words.LowerChristoffelWord(0,1,'xy') word: x sage: words.LowerChristoffelWord(1,1) word: 01
-
markoff_number
()¶ Returns the Markoff number associated to the Christoffel word self.
The Markoff number of a Christoffel word
is
, where
is the
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
is the unique factorization of
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.TESTS:
sage: from sage.combinat.words.word_generators import WordGenerator sage: words2 = WordGenerator() sage: type(loads(dumps(words2))) <class 'sage.combinat.words.word_generators.WordGenerator'>
-
CharacteristicSturmianWord
(slope, alphabet=(0, 1), bits=None)¶ Returns the characteristic Sturmian word (also called standard Sturmian word) of given slope.
Over a binary alphabet
, the characteristic Sturmian word
of irrational slope
is the infinite word satisfying
and
, where
and
are respectively the lower and upper mechanical words with slope
and intercept
. Equivalently, for irrationnal
,
.
Let
be the continued fraction expansion of
. It has been shown that the characteristic Sturmian word of slope
is also the limit of the sequence:
for
.
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
- iterable over the continued fraction expansion of a real
number in
- real number in
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
be the continued fraction expansion of
. Then, the characteristic Sturmian word of slope
is the limit of the sequence:
,
and
for
.
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
:
sage: words.CharacteristicSturmianWord((sqrt(3)-1)/2) word: 0100100101001001001010010010010100100101...
The same word defined from the continued fraction expansion of
:
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
:
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...
TESTS:
sage: words.CharacteristicSturmianWord([1,1,1],'xyz') Traceback (most recent call last): ... TypeError: alphabet does not contain two distinct elements
sage: words.CharacteristicSturmianWord(5/4) Traceback (most recent call last): ... ValueError: The argument slope (=5/4) must be in ]0,1[.
sage: words.CharacteristicSturmianWord(1/golden_ratio^2, bits=30) doctest:...: DeprecationWarning: the argument 'bits' is deprecated See http://trac.sagemath.org/14567 for details. word: 0100101001001010010100100101001001010010... sage: _.length() +Infinity
sage: a = words.LowerMechanicalWord(1/pi)[1:] sage: b = words.UpperMechanicalWord(1/pi)[1:] sage: c = words.CharacteristicSturmianWord(1/pi) sage: n = 500; a[:n] == b[:n] == c[:n] True
sage: alpha = random() sage: c = words.CharacteristicSturmianWord(alpha) sage: l = words.LowerMechanicalWord(alpha)[1:] sage: u = words.UpperMechanicalWord(alpha)[1:] sage: i = 10000; j = i + 500; c[i:j] == l[i:j] == u[i:j] True
sage: a, b = 207, 232 sage: u = words.ChristoffelWord(a, b) sage: v = words.CharacteristicSturmianWord(a/(a+b)) sage: u[1:-1] == v[:-2] True
-
ChristoffelWord
¶ alias of
LowerChristoffelWord
-
CodingOfRotationWord
(alpha, beta, x=0, alphabet=(0, 1))¶ Returns the infinite word obtained from the coding of rotation of parameters
over the given two-letter alphabet.
The coding of rotation corresponding to the parameters
is the symbolic sequence
defined over the binary alphabet
by
if
and
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...
TESTS:
sage: words.CodingOfRotationWord(0.51,0.43,alphabet=[1,0,2]) Traceback (most recent call last): ... TypeError: alphabet does not contain two distinct elements
-
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:
,
,
for
.
Fixed point construction: the Fibonacci word is the fixed point of the morphism:
and
. Hence, it can be constructed by the following read-write process:
- beginning at the first letter of
,
- if the next letter is
, append
to the word;
- if the next letter is
, append
to the word;
- move to the next letter of the word.
Function: Over the alphabet
, the n-th letter of the Fibonacci word is
where
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...
TESTS:
sage: from math import floor, sqrt sage: golden_ratio = (1 + sqrt(5))/2.0 sage: a = golden_ratio / (1 + 2*golden_ratio) sage: wn = lambda n : int(floor(a*(n+2)) - floor(a*(n+1))) sage: f = Words([0,1])(wn); f word: 0100101001001010010100100101001001010010... sage: f[:10000] == w[:10000] True sage: f[:10000] == u[:10000] #long time True sage: words.FibonacciWord("abc") Traceback (most recent call last): ... TypeError: alphabet does not contain two distinct elements
-
FixedPointOfMorphism
(morphism, first_letter)¶ Returns the fixed point of the morphism beginning with
first_letter
.A fixed point of a morphism
is a word
such that
.
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] 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
be an alphabet, where
and
are two distinct positive integers. The Kolakoski word
over
and starting with
is the unique infinite word
such that
, where
is the word encoding the runs of
(see
delta()
method on words for more details).Note that
. On the other hand, the words
and
are the unique two words over
that are fixed by
.
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...
TESTS:
sage: for i in range(1,10): ... for j in range(1,10): ... if i != j: ... w = words.KolakoskiWord(alphabet=(i,j)) ... assert w[:50] == w.delta()[:50]
sage: words.KolakoskiWord((0, 2)) Traceback (most recent call last): ... ValueError: The alphabet (=(0, 2)) must consist of two distinct positive integers
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
and intercept
The lower mechanical word
with slope
and intercept
is defined by
. [Loth02]
INPUT:
alpha
– real number such thatrho
– 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) word: 0010010100100101001010010010100100101001... sage: words.LowerMechanicalWord(1/5) word: 0000100001000010000100001000010000100001... sage: words.LowerMechanicalWord(1/pi) word: 0001001001001001001001000100100100100100...
TESTS:
sage: m = words.LowerMechanicalWord(1/golden_ratio^2)[1:] sage: s = words.CharacteristicSturmianWord(1/golden_ratio^2) sage: m[:500] == s[:500] True
Check that this returns a word in an alphabet (trac ticket #10054):
sage: words.UpperMechanicalWord(1/golden_ratio^2).parent() Words over {0, 1}
-
MinimalSmoothPrefix
(n)¶ This function finds and returns the minimal smooth prefix of length
n
.See [BMP07] 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
REFERENCES:
[BMP07] S. Brlek, G. Melançon, G. Paquin, Properties of the extremal infinite smooth words, Discrete Math. Theor. Comput. Sci. 9 (2007) 33–49.
-
PalindromicDefectWord
(k=1, alphabet='ab')¶ Returns the finite word
.
As described by Brlek, Hamel, Nivat and Reuteunaer in [BHNR04], this finite word
is such that the infinite periodic word
have 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
TESTS:
sage: k = 25 sage: (words.PalindromicDefectWord(k)^2).defect() 25
If k is negative or zero, then we get the same word:
sage: words.PalindromicDefectWord(0) word: aaaaaa sage: words.PalindromicDefectWord(-3) word: aaaaaa
-
RandomWord
(n, m=2, alphabet=None)¶ Returns a random word of length
over the given
-letter alphabet.
INPUT:
n
- integer, the length of the wordm
- integer (default 2), the size of the output alphabetalphabet
- (default is) 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
TESTS:
sage: words.RandomWord(2,3,"abcd") Traceback (most recent call last): ... TypeError: alphabet does not contain 3 distinct elements
-
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
over a finite alphabet
is said to be standard episturmian (or epistandard) iff there exists an infinite word
over
(called the directive word of
) such that
is the limit as
goes to infinity of
, where
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 [DJP01], [JP02], and [GJ07].
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
REFERENCES:
[JP02] J. Justin, G. Pirillo, Episturmian words and episturmian morphisms, Theoret. Comput. Sci. 276 (2002) 281–313. [GJ07] A. Glen, J. Justin, Episturmian words: a survey, Preprint, 2007, arXiv:0801.1655.
-
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
. We use the following definition:
is the sum modulo
of the digits in the given base expansion of
.
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
TESTS:
sage: words.ThueMorseWord(alphabet='ab', base=1) Traceback (most recent call last): ... ValueError: base (=1) and len(alphabet) (=2) must be at least 2
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
, where
and
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
. Equivalently, if
is the lower Christoffel word of slope
, where
and
are letters, then
is the upper Christoffel word of slope
(because
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
TESTS:
sage: words.UpperChristoffelWord(51,43,"abc") Traceback (most recent call last): ... ValueError: alphabet must contain exactly two distinct elements
-
UpperMechanicalWord
(alpha, rho=0, alphabet=None)¶ Returns the upper mechanical word with slope
and intercept
The upper mechanical word
with slope
and intercept
is defined by
. [Loth02]
INPUT:
alpha
– real number such thatrho
– 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) word: 1010010100100101001010010010100100101001... sage: words.UpperMechanicalWord(1/5) word: 1000010000100001000010000100001000010000... sage: words.UpperMechanicalWord(1/pi) word: 1001001001001001001001000100100100100100...
TESTS:
sage: m = words.UpperMechanicalWord(1/golden_ratio^2)[1:] sage: s = words.CharacteristicSturmianWord(1/golden_ratio^2) sage: m[:500] == s[:500] True
Check that this returns a word in an alphabet (trac ticket #10054):
sage: words.UpperMechanicalWord(1/golden_ratio^2).parent() Words over {0, 1}
-
dual_fibonacci_tile
(n)¶ Returns the
-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
-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
-adic infinite word obtained from a sequence of morphisms applied on a letter.
DEFINITION (from [Fogg]):
Let
be a infinite word over an alphabet
. A standard representation of
is obtained from a sequence of substitutions
and a sequence of letters
such that:
Given a set of substitutions
, we say that the representation is
-adic standard if the subtitutions are chosen in
.
INPUT:
sequence
- An iterable sequence of indices or of morphisms. It may be finite or infinite. Ifsequence
is infinite, the image of the-th letter under the
-th morphism must start with the
-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’s define three morphisms and compute the first nested succesive prefixes of the
-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
-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
-adic word:
sage: t = words.ThueMorseWord([tm,fib]) sage: words.s_adic(t, 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
-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]) word: abbaabababbaababbaabbaababbaabababbaabba... sage: words.s_adic(it(), repeat('a'), [tm,fib]) word: abbaababbaabbaababbaababbaabbaababbaabba... sage: words.s_adic(it(), repeat('a'), [tm,fib]) 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
can’t satisfy the hypothesis of the nested prefixes, but one may compute arbitrarily long finite words having the limit
:
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
-adic word defined over an infinite set
of morphisms
:
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 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: 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]
TESTS:
sage: tm = WordMorphism('a->ab,b->ba') sage: fib = WordMorphism('a->ab,b->a') sage: w = words.s_adic([fib,tm,tm,fib,tm,fib]*3,'a') sage: w word: abaaabaababaabaaababaaababaaabaababaabaa... sage: w.length() 32400 sage: w.parent() Words over {'a', 'b'} sage: type(w) <class 'sage.combinat.words.word.FiniteWord_iter_with_caching'>
sage: words.s_adic([fib,tm,tm,fib,tm,fib],'aaaaaaa') word: abaaabaababaabaaababaaababaaabaababa
sage: words.s_adic([0,1,0,1,0,1,0,1],'a',[tm,fib]) word: abbaabababbaabbaababbaababbaabababbaabba...
sage: words.s_adic([fib,fib],'bb') Traceback (most recent call last): ... ValueError: The hypothesis of the algorithm used is not satisfied: the image of the 2-th letter (=b) under the 2-th morphism (=a->ab, b->a) should start with the 1-th letter (=b).
Test on different letters:
sage: tm = WordMorphism({0:[0,1], 1:[1,0]}) sage: fib = WordMorphism({0:[0,1], 1:[0]}) sage: f = lambda n: tm if n == 0 else fib sage: words.s_adic(words.ThueMorseWord(), repeat(0), f) word: 0110010110011001100101100101100110010110...
Testing the message error for the third argument:
sage: words.s_adic(words.ThueMorseWord(), repeat(0), 5) Traceback (most recent call last): ... TypeError: morphisms (=5) must be None, callable or provide a __getitem__ method.
AUTHORS:
- Sebastien Labbe (2009-12-18): initial version
-