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
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.
EXAMPLES:
sage: t = words.ThueMorseWord(); t
Thue-Morse word over Ordered Alphabet [0, 1]
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] if
and alphabet[0] otherwise. The Christoffel
word is the word obtained by reading the edge labels along the
cycle beginning from 0.
EXAMPLES:
sage: w = words.LowerChristoffelWord(1,0); w
Lower Christoffel word of slope 1/0 over Ordered Alphabet [0, 1]
sage: print w
word: 1
sage: w = words.LowerChristoffelWord(0,1,'xy'); w
Lower Christoffel word of slope 0/1 over Ordered Alphabet ['x', 'y']
sage: print w
word: x
sage: w = words.LowerChristoffelWord(1,1); w
Lower Christoffel word of slope 1/1 over Ordered Alphabet [0, 1]
sage: print w
word: 01
sage: w = words.LowerChristoffelWord(4,7); w
Lower Christoffel word of slope 4/7 over Ordered Alphabet [0, 1]
sage: print w
word: 00100100101
sage: w = words.LowerChristoffelWord(4,7,alphabet='ab'); w
Lower Christoffel word of slope 4/7 over Ordered Alphabet ['a', 'b']
sage: print w
word: aabaabaabab
TESTS:
sage: words.LowerChristoffelWord(4,8)
...
ValueError: 4 and 8 are not relatively prime
sage: words.LowerChristoffelWord(17, 39, 'xyz')
...
ValueError: alphabet must contain exactly two distinct elements
sage: w = words.LowerChristoffelWord(4,7)
sage: w2 = loads(dumps(w))
sage: w == w2
True
sage: type(w2)
<class 'sage.combinat.words.word_generators.LowerChristoffelWord'>
sage: _ = w2.standard_factorization() # hackish test for self.__p and self.__q
EXAMPLES:
sage: from sage.combinat.words.word_generators import LowerChristoffelWord
sage: w = LowerChristoffelWord(5,7)
sage: w.__reduce__()
(<class 'sage.combinat.words.word_generators.LowerChristoffelWord'>, (5, 7, Ordered Alphabet [0, 1]))
EXAMPLES:
sage: w = words.LowerChristoffelWord(4,7,alphabet='ab'); w
Lower Christoffel word of slope 4/7 over Ordered Alphabet ['a', 'b']
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
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: print w
word: 00100100100101
sage: w1, w2 = w.standard_factorization()
sage: print w1
word: 001
sage: print w2
word: 00100100101
sage: w = words.LowerChristoffelWord(51,37)
sage: w1, w2 = w.standard_factorization()
sage: w1
Lower Christoffel word of slope 11/8 over Ordered Alphabet [0, 1]
sage: w2
Lower Christoffel word of slope 40/29 over Ordered Alphabet [0, 1]
sage: w1 * w2 == w
True
A class consisting of constructors for several famous words.
TESTS:
sage: type(loads(dumps(words)))
<class 'sage.combinat.words.word_generators.WordGenerator'>
Returns the characteristic Sturmian word over the given two-letter alphabet with slope given by the continued fraction [0, cf[1], cf[2], ...]. Here cf should be an iterator.
The characteristic Sturmian word of slope
is the limit of the
sequence:
for
.
Equivalently, the -th term of the characteristic Sturmian word
of slope
is
.
INPUT:
EXAMPLES:
sage: def cf():
... yield 0
... while True: yield 1
...
sage: F = words.CharacteristicSturmianWord(cf()); F
Characteristic Sturmian word over Ordered Alphabet [0, 1], defined recursively
sage: Fib = words.FibonacciWord(); Fib
Fibonacci word over Ordered Alphabet [0, 1], defined recursively
sage: F[:10000] == Fib[:10000]
True
sage: def cf():
... yield 0
... while True: yield 1
...
sage: G = words.CharacteristicSturmianWord(cf(),'rs'); G
Characteristic Sturmian word over Ordered Alphabet ['r', 's'], defined recursively
sage: print G[:50]
word: rsrrsrsrrsrrsrsrrsrsrrsrrsrsrrsrrsrsrrsrsrrsrrsrsr
TESTS:
sage: words.CharacteristicSturmianWord([1,1,1],'xyz')
...
TypeError: alphabet does not contain two distinct elements
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 [1].
EXAMPLES:
sage: alpha = 0.45
sage: beta = 0.48
sage: w = words.CodingOfRotationWord(0.45, 0.48); w
Coding of rotation with parameters (0.450000000000000, 0.480000000000000, 0)
sage: w[:100]
word: 1101010101001010101011010101010010101010...
sage: w = words.CodingOfRotationWord(0.45, 0.48, alphabet='xy')
sage: w[:100]
word: yyxyxyxyxyxxyxyxyxyxyyxyxyxyxyxxyxyxyxyx...
TESTS:
sage: words.CodingOfRotationWord(0.51,0.43,alphabet=[1,0,2])
...
TypeError: alphabet does not contain two distinct elements
REFERENCES:
Returns the Fibonacci word on the given two-letter alphabet.
INPUT:
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:
EXAMPLES:
sage: w = words.FibonacciWord(construction_method="recursive"); w
Fibonacci word over Ordered Alphabet [0, 1], defined recursively
sage: print w[:99]
word: 010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001
sage: v = words.FibonacciWord(construction_method="recursive", alphabet='ab'); v
Fibonacci word over Ordered Alphabet ['a', 'b'], defined recursively
sage: print v[:99]
word: abaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaab
sage: u = words.FibonacciWord(construction_method="fixed point"); u
Fibonacci word over Ordered Alphabet [0, 1], defined as the fixed point of a morphism
sage: print u[:99]
word: 010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001
sage: x = words.FibonacciWord(construction_method="fixed point", alphabet=[4, 1]); x
Fibonacci word over Ordered Alphabet [1, 4], defined as the fixed point of a morphism
sage: print x[:99]
word: 414414144144141441414414414144144141441414414414144141441441414414414144141441441414414414144141441
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")
...
TypeError: alphabet does not contain two distinct elements
Returns the fixed point of the morphism beginning with first_letter.
A fixed point of a morphism is a word
such that
.
INPUT:
EXAMPLES:
sage: mu = {0:[0,1], 1:[1,0]}
sage: tm = words.FixedPointOfMorphism(mu,0); tm
Fixed point beginning with 0 of the morphism WordMorphism: 0->01, 1->10
sage: TM = words.ThueMorseWord()
sage: tm[:1000] == TM[:1000]
True
sage: mu = {0:[0,1], 1:[0]}
sage: f = words.FixedPointOfMorphism(mu,0); f
Fixed point beginning with 0 of the morphism WordMorphism: 0->01, 1->0
sage: F = words.FibonacciWord(); F
Fibonacci word over Ordered Alphabet [0, 1], defined recursively
sage: f[:1000] == F[:1000]
True
sage: fp = words.FixedPointOfMorphism('a->abc,b->,c->','a'); fp
Fixed point beginning with 'a' of the morphism WordMorphism: a->abc, b->, c->
sage: fp[:10]
word: abc
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] if
and alphabet[0] otherwise. The Christoffel
word is the word obtained by reading the edge labels along the
cycle beginning from 0.
EXAMPLES:
sage: w = words.LowerChristoffelWord(1,0); w
Lower Christoffel word of slope 1/0 over Ordered Alphabet [0, 1]
sage: print w
word: 1
sage: w = words.LowerChristoffelWord(0,1,'xy'); w
Lower Christoffel word of slope 0/1 over Ordered Alphabet ['x', 'y']
sage: print w
word: x
sage: w = words.LowerChristoffelWord(1,1); w
Lower Christoffel word of slope 1/1 over Ordered Alphabet [0, 1]
sage: print w
word: 01
sage: w = words.LowerChristoffelWord(4,7); w
Lower Christoffel word of slope 4/7 over Ordered Alphabet [0, 1]
sage: print w
word: 00100100101
sage: w = words.LowerChristoffelWord(4,7,alphabet='ab'); w
Lower Christoffel word of slope 4/7 over Ordered Alphabet ['a', 'b']
sage: print w
word: aabaabaabab
TESTS:
sage: words.LowerChristoffelWord(4,8)
...
ValueError: 4 and 8 are not relatively prime
sage: words.LowerChristoffelWord(17, 39, 'xyz')
...
ValueError: alphabet must contain exactly two distinct elements
sage: w = words.LowerChristoffelWord(4,7)
sage: w2 = loads(dumps(w))
sage: w == w2
True
sage: type(w2)
<class 'sage.combinat.words.word_generators.LowerChristoffelWord'>
sage: _ = w2.standard_factorization() # hackish test for self.__p and self.__q
EXAMPLES:
sage: from sage.combinat.words.word_generators import LowerChristoffelWord
sage: w = LowerChristoffelWord(5,7)
sage: w.__reduce__()
(<class 'sage.combinat.words.word_generators.LowerChristoffelWord'>, (5, 7, Ordered Alphabet [0, 1]))
EXAMPLES:
sage: w = words.LowerChristoffelWord(4,7,alphabet='ab'); w
Lower Christoffel word of slope 4/7 over Ordered Alphabet ['a', 'b']
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
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: print w
word: 00100100100101
sage: w1, w2 = w.standard_factorization()
sage: print w1
word: 001
sage: print w2
word: 00100100101
sage: w = words.LowerChristoffelWord(51,37)
sage: w1, w2 = w.standard_factorization()
sage: w1
Lower Christoffel word of slope 11/8 over Ordered Alphabet [0, 1]
sage: w2
Lower Christoffel word of slope 40/29 over Ordered Alphabet [0, 1]
sage: w1 * w2 == w
True
This function finds and returns the minimal smooth prefix of length n.
See [1] for a definition.
INPUT:
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:
Returns a random word of length over the given
-letter
alphabet.
INPUT:
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")
...
TypeError: alphabet does not contain 3 distinct elements
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 [1], [2], and [3].
INPUT:
EXAMPLES:
sage: Fibonacci = words.StandardEpisturmianWord(Words('ab')('ab')); Fibonacci
Standard episturmian word over Ordered Alphabet ['a', 'b']
sage: Fibonacci[:25]
word: abaababaabaababaababaabaa
sage: Tribonacci = words.StandardEpisturmianWord(Words('abc')('abc')); Tribonacci
Standard episturmian word over Ordered Alphabet ['a', 'b', 'c']
sage: Tribonacci[:25]
word: abacabaabacababacabaabaca
sage: S = words.StandardEpisturmianWord(Words('abcd')('aabcabada')); S
Standard episturmian word over Ordered Alphabet ['a', 'b', 'c', 'd']
sage: print S[:75]
word: aabaacaabaaabaacaabaabaacaabaaabaacaabaaabaacaabaabaacaabaaabaacaabaadaabaa
sage: S = words.StandardEpisturmianWord(Fibonacci); S
Standard episturmian word over Ordered Alphabet ['a', 'b']
sage: S[:25]
word: abaabaababaabaabaababaaba
sage: S = words.StandardEpisturmianWord(Tribonacci); S
Standard episturmian word over Ordered Alphabet ['a', 'b', 'c']
sage: S[:25]
word: abaabacabaabaabacabaababa
sage: words.StandardEpisturmianWord(123)
...
TypeError: directive_word is not a word, so it cannot be used to build an episturmian word
sage: words.StandardEpisturmianWord(Words('ab'))
...
TypeError: directive_word is not a word, so it cannot be used to build an episturmian word
REFERENCES:
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
.
INPUT:
EXAMPLES:
Thue-Morse word:
sage: t = words.ThueMorseWord(); t
Thue-Morse word over Ordered Alphabet [0, 1]
sage: print t[:50]
word: 01101001100101101001011001101001100101100110100101
Thue-Morse word on other alphabets:
sage: t = words.ThueMorseWord('ab'); t
Thue-Morse word over Ordered Alphabet ['a', 'b']
sage: print t[:50]
word: abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab
sage: t = words.ThueMorseWord(['L1', 'L2']); t
Thue-Morse word over Ordered Alphabet ['L1', 'L2']
sage: words.ThueMorseWord(['L1','L2'])[:8]
word: L1,L2,L2,L1,L2,L1,L1,L2
Generalized Thue Morse word:
sage: words.ThueMorseWord(alphabet=(0,1,2), base=2)
Generalized Thue-Morse word using base 2 over Ordered Alphabet [0, 1, 2]
sage: t = words.ThueMorseWord(alphabet=(0,1,2), base=5); t
Generalized Thue-Morse word using base 5 over Ordered Alphabet [0, 1, 2]
sage: t[:20]
word: 01201120122012001201
sage: t[100:130].critical_exponent()
10/3
TESTS:
sage: words.ThueMorseWord(alphabet='ab', base=1)
...
ValueError: base (=1) and len(alphabet) (=2) must be at least 2
REFERENCES:
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:
EXAMPLES:
sage: w = words.UpperChristoffelWord(1,0); w
Upper Christoffel word of slope 1/0 over Ordered Alphabet [0, 1]
sage: print w
word: 1
sage: w = words.UpperChristoffelWord(0,1); w
Upper Christoffel word of slope 0/1 over Ordered Alphabet [0, 1]
sage: print w
word: 0
sage: w = words.UpperChristoffelWord(1,1); w
Upper Christoffel word of slope 1/1 over Ordered Alphabet [0, 1]
sage: print w
word: 10
sage: w = words.UpperChristoffelWord(4,7); w
Upper Christoffel word of slope 4/7 over Ordered Alphabet [0, 1]
sage: print w
word: 10100100100
TESTS::
sage: words.UpperChristoffelWord(51,43,"abc")
...
ValueError: alphabet must contain exactly two distinct elements
Internal function iterating over the symbols of the characteristic
Sturmian word of slope . This
word is the limit of the sequence:
for
.
TESTS:
sage: d = iter([1,1,1,1,1,1])
sage: list(words._CharacteristicSturmianWord_LetterIterator(d))
[0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1]
Internal function that returns the symbol in position of the
coding of rotation word corresponding to the parameters
,
, and
.
TESTS:
sage: alpha, beta = 0.45, 0.48
sage: words._CodingOfRotationWord_function(3, alpha, beta)
1
sage: words._CodingOfRotationWord_function(10, alpha, beta)
0
sage: words._CodingOfRotationWord_function(17, alpha, beta)
0
Iterates over the symbols of the Fibonacci word, as defined by
the following recursive construction: the Fibonacci word is the
limit of the sequence ,
,
for
.
TESTS:
sage: from sage.combinat.words.word_generators import WordGenerator
sage: from itertools import islice
sage: it = WordGenerator()._FibonacciWord_RecursiveConstructionIterator()
sage: list(islice(it,13))
[0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1]
Internal iterating over the symbols of the standard episturmian word defined by the (directive) word directive_word.
An infinite word over a finite alphabet
is 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.
INPUT:
TESTS:
sage: import itertools
sage: it = words._StandardEpisturmianWord_LetterIterator(Word('ab'))
sage: list(itertools.islice(it, 13))
['a', 'b', 'a', 'a', 'b', 'a', 'b', 'a', 'a', 'b', 'a', 'a', 'b']
Returns the -th letter of the (Generalized) Thue-Morse word.
The -th digit of the Thue-Morse word can be defined as the number
of bits in the 2-complement representation of the position
modulo 2 which is what this function uses. The running time
is
where
is the position desired.
The -th digit of the Generalized Thue Morse word can be defined as
the sum of the digits of
written in the given base mod
,
where
is the length of the given alphabet.
INPUT:
OUTPUT:
0 or 1 – the digit at the position letter – the letter of alphabet at the position
TESTS:
sage: from sage.combinat.words.word_generators import WordGenerator
sage: WordGenerator()._ThueMorseWord_nth_digit(0)
0
sage: WordGenerator()._ThueMorseWord_nth_digit(3)
0
sage: WordGenerator()._ThueMorseWord_nth_digit(32)
1
sage: WordGenerator()._ThueMorseWord_nth_digit(6, 'abc', base = 7)
'a'
Internal function building a coding table for the phi_inv_tab function.
TESTS:
sage: from sage.combinat.words.word_generators import _build_tab
sage: _build_tab(1, [], Words([1, 2]))
[1]
sage: _build_tab(1, [1], Words([1, 2]))
[1, 2]
sage: _build_tab(2, [1], Words([1, 2]))
[2, 2]
sage: _build_tab(2, [1, 2], Words([1, 2]))
[2, 2, 1]
sage: _build_tab(1, [2, 2], Words([1, 2]))
[1, 1, 2]