This modules implements morphisms over finite and infinite words.
AUTHORS:
EXAMPLES:
Creation of a morphism from a dictionary or a string:
sage: n = WordMorphism({0:[0,2,2,1],1:[0,2],2:[2,2,1]})
sage: m = WordMorphism('x->xyxsxss,s->xyss,y->ys')
sage: n
WordMorphism: 0->0221, 1->02, 2->221
sage: m
WordMorphism: s->xyss, x->xyxsxss, y->ys
The codomain may be specified:
sage: WordMorphism({0:[0,2,2,1],1:[0,2],2:[2,2,1]}, codomain=Words([0,1,2,3,4]))
WordMorphism: 0->0221, 1->02, 2->221
Power of a morphism:
sage: n^2
WordMorphism: 0->022122122102, 1->0221221, 2->22122102
Image under a morphism:
sage: m('y')
word: ys
sage: m('xxxsy')
word: xyxsxssxyxsxssxyxsxssxyssys
Iterated image under a morphism:
sage: m('y', 3)
word: ysxyssxyxsxssysxyssxyss
Infinite fixed point of morphism:
sage: fix = m.fixed_point('x')
sage: fix
word: xyxsxssysxyxsxssxyssxyxsxssxyssxyssysxys...
sage: fix.length()
+Infinity
Incidence matrix:
sage: matrix(m)
[2 3 1]
[1 3 0]
[1 1 1]
Many other functionalities...:
sage: m.is_identity()
False
sage: m.is_endomorphism()
True
Bases: dict
Wrapper of dictionary that makes it callable.
EXAMPLES:
sage: from sage.combinat.words.morphism import CallableDict
sage: d = CallableDict({1:'one', 2:'zwei', 3:'trois'})
sage: d(1), d(2), d(3)
('one', 'zwei', 'trois')
Bases: sage.structure.sage_object.SageObject
WordMorphism class
EXAMPLES:
sage: n = WordMorphism({0:[0,2,2,1],1:[0,2],2:[2,2,1]})
sage: m = WordMorphism('x->xyxsxss,s->xyss,y->ys')
Power of a morphism:
sage: n^2
WordMorphism: 0->022122122102, 1->0221221, 2->22122102
Image under a morphism:
sage: m('y')
word: ys
sage: m('xxxsy')
word: xyxsxssxyxsxssxyxsxssxyssys
Iterated image under a morphism:
sage: m('y', 3)
word: ysxyssxyxsxssysxyssxyss
See more examples in the documentation of the call method (m.__call__?).
Infinite fixed point of morphism:
sage: fix = m.fixed_point('x')
sage: fix
word: xyxsxssysxyxsxssxyssxyxsxssxyssxyssysxys...
sage: fix.length()
+Infinity
Incidence matrix:
sage: matrix(m)
[2 3 1]
[1 3 0]
[1 1 1]
Many other functionalities...:
sage: m.is_identity()
False
sage: m.is_endomorphism()
True
TESTS:
sage: wm = WordMorphism('a->ab,b->ba')
sage: wm == loads(dumps(wm))
True
Returns the subspace on which the incidence matrix of self acts by roots of unity.
EXAMPLES:
sage: WordMorphism('0->1,1->0').abelian_rotation_subspace()
Vector space of degree 2 and dimension 2 over Rational Field
Basis matrix:
[1 0]
[0 1]
sage: WordMorphism('0->01,1->10').abelian_rotation_subspace()
Vector space of degree 2 and dimension 0 over Rational Field
Basis matrix:
[]
sage: WordMorphism('0->01,1->1').abelian_rotation_subspace()
Vector space of degree 2 and dimension 1 over Rational Field
Basis matrix:
[0 1]
sage: WordMorphism('1->122,2->211').abelian_rotation_subspace()
Vector space of degree 2 and dimension 1 over Rational Field
Basis matrix:
[ 1 -1]
sage: WordMorphism('0->1,1->102,2->3,3->4,4->2').abelian_rotation_subspace()
Vector space of degree 5 and dimension 3 over Rational Field
Basis matrix:
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
The domain needs to be equal to the codomain:
sage: WordMorphism('0->1,1->',codomain=Words('01')).abelian_rotation_subspace()
Vector space of degree 2 and dimension 0 over Rational Field
Basis matrix:
[]
Returns the codomain of self.
EXAMPLES:
sage: WordMorphism('a->ab,b->a').codomain()
Words over {'a', 'b'}
sage: WordMorphism('6->ab,y->5,0->asd').codomain()
Words over {'5', 'a', 'b', 'd', 's'}
Returns the morphism where the image of the letter by self is conjugated of parameter pos.
INPUT:
EXAMPLES:
sage: m = WordMorphism('a->abcde')
sage: m.conjugate(0) == m
True
sage: m.conjugate(1)
WordMorphism: a->bcdea
sage: m.conjugate(3)
WordMorphism: a->deabc
sage: WordMorphism('').conjugate(4)
WordMorphism:
sage: m = WordMorphism('a->abcde,b->xyz')
sage: m.conjugate(2)
WordMorphism: a->cdeab, b->zxy
Returns domain of self.
EXAMPLES:
sage: WordMorphism('a->ab,b->a').domain()
Words over {'a', 'b'}
sage: WordMorphism('b->ba,a->ab').domain()
Words over {'a', 'b'}
sage: WordMorphism('6->ab,y->5,0->asd').domain()
Words over {'0', '6', 'y'}
Return the dual map of self (see [1]).
Note
It is acually implemented only for .
INPUT:
OUTPUT:
an instance of E1Star - the dual map
EXAMPLES:
sage: sigma = WordMorphism({1:[2],2:[3],3:[1,2]})
sage: sigma.dual_map()
E_1^*(1->2, 2->3, 3->12)
sage: sigma.dual_map(k=2)
Traceback (most recent call last):
...
NotImplementedError: The dual map E_k^* is implemented only for k = 1 (not 2)
REFERENCES:
Returns self extended by other.
Let and
be two morphisms. A morphism
corresponds to
extended by
if
if
and
otherwise.
INPUT:
OUTPUT:
WordMorphism
EXAMPLES:
sage: m = WordMorphism('a->ab,b->ba')
sage: n = WordMorphism({0:1,1:0,'a':5})
sage: m.extend_by(n)
WordMorphism: 0->1, 1->0, a->ab, b->ba
sage: n.extend_by(m)
WordMorphism: 0->1, 1->0, a->5, b->ba
sage: m.extend_by(m)
WordMorphism: a->ab, b->ba
TESTS:
sage: m.extend_by(WordMorphism({})) == m
True
sage: m.extend_by(WordMorphism('')) == m
True
sage: m.extend_by(4)
Traceback (most recent call last):
...
TypeError: other (=4) is not a WordMorphism
Returns the fixed point of self beginning by the given letter.
A fixed point of morphism is a word
such that
.
INPUT:
OUTPUT:
EXAMPLES:
Infinite fixed point:
sage: WordMorphism('a->ab,b->ba').fixed_point(letter='a')
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: WordMorphism('a->ab,b->a').fixed_point(letter='a')
word: abaababaabaababaababaabaababaabaababaaba...
sage: W = Words('abc')
sage: WordMorphism('a->ab,b->b,c->ba', codomain=W).fixed_point(letter='a')
word: abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
Infinite fixed point of an erasing morphism:
sage: WordMorphism('a->ab,b->,c->ba', codomain=W).fixed_point(letter='a')
word: ab
Finite fixed point:
sage: WordMorphism('a->ab,b->b,c->ba', codomain=W).fixed_point(letter='b')
word: b
Finite fixed point of an erasing morphism:
sage: m = WordMorphism('a->abc,b->,c->')
sage: fp = m.fixed_point('a'); fp
word: abc
sage: m = WordMorphism('a->ba,b->')
sage: m('ba')
word: ba
sage: m.fixed_point('a') #todo: not implemented
word: ba
Fixed point of a power of a morphism:
sage: m = WordMorphism('a->ba,b->ab')
sage: (m^2).fixed_point(letter='a')
word: abbabaabbaababbabaababbaabbabaabbaababba...
TESTS:
sage: WordMorphism('a->ab,b->,c->ba', codomain=W).fixed_point(letter='b')
Traceback (most recent call last):
...
TypeError: self must be prolongable on b
sage: WordMorphism('a->ab,b->,c->ba', codomain=W).fixed_point(letter='c')
Traceback (most recent call last):
...
TypeError: self must be prolongable on c
sage: WordMorphism('a->ab,b->,c->ba', codomain=W).fixed_point(letter='d')
Traceback (most recent call last):
...
TypeError: letter (=d) is not in the domain alphabet (={'a', 'b', 'c'})
sage: WordMorphism('a->aa,b->aac').fixed_point(letter='a')
Traceback (most recent call last):
...
TypeError: self (=a->aa, b->aac) is not an endomorphism
Returns the list of all fixed points of self.
EXAMPLES:
sage: f = WordMorphism('a->ab,b->ba')
sage: for w in f.fixed_points(): print w
abbabaabbaababbabaababbaabbabaabbaababba...
baababbaabbabaababbabaabbaababbaabbabaab...
sage: f = WordMorphism('a->ab,b->c,c->a')
sage: for w in f.fixed_points(): print w
abcaababcabcaabcaababcaababcabcaababcabc...
sage: f = WordMorphism('a->ab,b->cab,c->bcc')
sage: for w in f.fixed_points(): print w
abcabbccabcabcabbccbccabcabbccabcabbccab...
This shows that ticket trac ticket #13668 has been resolved:
sage: d = {1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]}
sage: s = WordMorphism(d)
sage: s7 = s^7
sage: s7.fixed_points()
[word: 12232342..., word: 2,3,4,5,6,7,8...]
sage: s7r = s7.reversal()
sage: s7r.fixed_points()
[]
This shows that ticket trac ticket #13668 has been resolved:
sage: s = "1->321331332133133,2->133321331332133133,3->2133133133321331332133133"
sage: s = WordMorphism(s)
sage: (s^2).fixed_points()
[]
Returns the list of growing letters.
See is_growing() for more information.
EXAMPLES:
sage: WordMorphism('0->01,1->10').growing_letters()
['0', '1']
sage: WordMorphism('0->01,1->1').growing_letters()
['0']
sage: WordMorphism('0->01,1->0,2->1',codomain=Words('012')).growing_letters()
['0', '1', '2']
Returns True if self has a conjugate in class -
.
DEFINITION : Let be an alphabet. We say that a
primitive substitution
is in the class P if there
exists a palindrome
and for each
a
palindrome
such that
for all
. [1]
Let be an involution on
. We say that a morphism
is in class
-
if there exists an
-palindrome
and for each
there exists an
-palindrome
such
that
. [2]
INPUT:
REFERENCES:
EXAMPLES:
sage: fibo = WordMorphism('a->ab,b->a')
sage: fibo.has_conjugate_in_classP()
True
sage: (fibo^2).is_in_classP()
False
sage: (fibo^2).has_conjugate_in_classP()
True
Returns True if all the non empty images of self begins with the same letter.
EXAMPLES:
sage: m = WordMorphism('a->abcde,b->xyz')
sage: m.has_left_conjugate()
False
sage: WordMorphism('b->xyz').has_left_conjugate()
True
sage: WordMorphism('').has_left_conjugate()
True
sage: WordMorphism('a->,b->xyz').has_left_conjugate()
True
sage: WordMorphism('a->abbab,b->abb').has_left_conjugate()
True
sage: WordMorphism('a->abbab,b->abb,c->').has_left_conjugate()
True
Returns True if all the non empty images of self ends with the same letter.
EXAMPLES:
sage: m = WordMorphism('a->abcde,b->xyz')
sage: m.has_right_conjugate()
False
sage: WordMorphism('b->xyz').has_right_conjugate()
True
sage: WordMorphism('').has_right_conjugate()
True
sage: WordMorphism('a->,b->xyz').has_right_conjugate()
True
sage: WordMorphism('a->abbab,b->abb').has_right_conjugate()
True
sage: WordMorphism('a->abbab,b->abb,c->').has_right_conjugate()
True
Return the image of a letter
INPUT:
OUTPUT:
word
..NOTE:
The letter is assumed to be in the domain alphabet
(no check done). Hence, this method is faster
than the ``__call__`` method suitable for words input.
EXAMPLES:
sage: m = WordMorphism('a->ab,b->ac,c->a')
sage: m.image('b')
word: ac
sage: s = WordMorphism({('a', 1):[('a', 1), ('a', 2)], ('a', 2):[('a', 1)]})
sage: s.image(('a',1))
word: ('a', 1),('a', 2)
sage: s = WordMorphism({0:[1,2], 'a':(2,3,4), ():[9,8,7]})
sage: s.image(0)
word: 12
sage: s.image('a')
word: 234
sage: s.image(())
word: 987
Returns the list of all the images of the letters of the alphabet under self.
EXAMPLES:
sage: WordMorphism('a->ab,b->a').images()
[word: ab, word: a]
sage: WordMorphism('6->ab,y->5,0->asd').images()
[word: 5, word: asd, word: ab]
Returns the incidence matrix of the morphism. The order of the rows and column are given by the order defined on the alphabet of the domain and the codomain.
The matrix returned is over the integers. If a different ring is desired, use either the change_ring function or the matrix function.
EXAMPLES:
sage: m = WordMorphism('a->abc,b->a,c->c')
sage: m.incidence_matrix()
[1 1 0]
[1 0 0]
[1 0 1]
sage: m = WordMorphism('a->abc,b->a,c->c,d->abbccccabca,e->abc')
sage: m.incidence_matrix()
[1 1 0 3 1]
[1 0 0 3 1]
[1 0 1 5 1]
Returns True if the cardinality of the domain is zero and False otherwise.
EXAMPLES:
sage: WordMorphism('').is_empty()
True
sage: WordMorphism('a->a').is_empty()
False
Returns True if the codomain is a subset of the domain.
EXAMPLES:
sage: WordMorphism('a->ab,b->a').is_endomorphism()
True
sage: WordMorphism('6->ab,y->5,0->asd').is_endomorphism()
False
sage: WordMorphism('a->a,b->aa,c->aaa').is_endomorphism()
False
sage: Wabc = Words('abc')
sage: m = WordMorphism('a->a,b->aa,c->aaa',codomain = Wabc)
sage: m.is_endomorphism()
True
We check that trac ticket #8674 is fixed:
sage: P = WordPaths('abcd')
sage: m = WordMorphism('a->adab,b->ab,c->cbcd,d->cd', codomain=P)
sage: m.is_endomorphism()
True
Returns True if self is an erasing morphism, i.e. the image of a letter is the empty word.
EXAMPLES:
sage: WordMorphism('a->ab,b->a').is_erasing()
False
sage: WordMorphism('6->ab,y->5,0->asd').is_erasing()
False
sage: WordMorphism('6->ab,y->5,0->asd,7->').is_erasing()
True
sage: WordMorphism('').is_erasing()
False
Return True if letter is a growing letter.
A letter is growing for the morphism
if the length of the
iterates of
tend to infinity as
goes to infinity.
INPUT:
Note
If letter is None, this returns True if self is everywhere growing, i.e., all letters are growing letters (see [CassNic10]), and that self must be an endomorphism.
EXAMPLES:
sage: WordMorphism('0->01,1->1').is_growing('0')
True
sage: WordMorphism('0->01,1->1').is_growing('1')
False
sage: WordMorphism('0->01,1->10').is_growing()
True
sage: WordMorphism('0->1,1->2,2->01').is_growing()
True
sage: WordMorphism('0->01,1->1').is_growing()
False
The domain needs to be equal to the codomain:
sage: WordMorphism('0->01,1->0,2->1',codomain=Words('012')).is_growing()
True
Test of erasing morphisms:
sage: WordMorphism('0->01,1->').is_growing('0')
False
sage: m = WordMorphism('a->bc,b->bcc,c->',codomain=Words('abc'))
sage: m.is_growing('a')
False
sage: m.is_growing('b')
False
sage: m.is_growing('c')
False
REFERENCES:
[CassNic10] | Cassaigne J., Nicolas F. Factor complexity. Combinatorics, automata and number theory, 163–247, Encyclopedia Math. Appl., 135, Cambridge Univ. Press, Cambridge, 2010. |
Returns True if self is the identity morphism.
EXAMPLES:
sage: m = WordMorphism('a->a,b->b,c->c,d->e')
sage: m.is_identity()
False
sage: WordMorphism('a->a,b->b,c->c').is_identity()
True
sage: WordMorphism('a->a,b->b,c->cb').is_identity()
False
sage: m = WordMorphism('a->b,b->c,c->a')
sage: (m^2).is_identity()
False
sage: (m^3).is_identity()
True
sage: (m^4).is_identity()
False
sage: WordMorphism('').is_identity()
True
sage: WordMorphism({0:[0],1:[1]}).is_identity()
True
We check that #8618 is fixed:
sage: t = WordMorphism({'a1':['a2'], 'a2':['a1']})
sage: (t*t).is_identity()
True
Returns True if self is in class (or
-
).
DEFINITION : Let be an alphabet. We say that a
primitive substitution
is in the class P if there
exists a palindrome
and for each
a
palindrome
such that
for all
. [1]
Let be an involution on
. “We say that a morphism
is in class
-
if there exists an
-palindrome
and for each
there exists an
-palindrome
such
that
. [2]
INPUT:
REFERENCES:
EXAMPLES:
sage: WordMorphism('a->bbaba,b->bba').is_in_classP()
True
sage: tm = WordMorphism('a->ab,b->ba')
sage: tm.is_in_classP()
False
sage: f = WordMorphism('a->b,b->a')
sage: tm.is_in_classP(f=f)
True
sage: (tm^2).is_in_classP()
True
sage: (tm^2).is_in_classP(f=f)
False
sage: fibo = WordMorphism('a->ab,b->a')
sage: fibo.is_in_classP()
True
sage: fibo.is_in_classP(f=f)
False
sage: (fibo^2).is_in_classP()
False
sage: f = WordMorphism('a->b,b->a,c->c')
sage: WordMorphism('a->acbcc,b->acbab,c->acbba').is_in_classP(f)
True
Returns True if self is an involution, i.e. its square is the identity.
INPUT:
EXAMPLES:
sage: WordMorphism('a->b,b->a').is_involution()
True
sage: WordMorphism('a->b,b->ba').is_involution()
False
sage: WordMorphism({0:[1],1:[0]}).is_involution()
True
TESTS:
sage: WordMorphism('').is_involution()
True
sage: WordMorphism({0:1,1:0,2:3}).is_involution()
Traceback (most recent call last):
...
TypeError: self (=0->1, 1->0, 2->3) is not an endomorphism
Returns True if self is primitive.
A morphism is primitive if there exists
an positive integer
such that for all
,
contains all the letters of
.
INPUT:
ALGORITHM:
Exercices 8.7.8, p.281 in [1] : (c) Letbe the least integer
such that
has all positive entries. Prove that, for all primitive matrices
, we have
. (d) Prove that the bound
is best possible.
EXAMPLES:
sage: tm = WordMorphism('a->ab,b->ba')
sage: tm.is_primitive()
True
sage: fibo = WordMorphism('a->ab,b->a');
sage: fibo.is_primitive()
True
sage: m = WordMorphism('a->bb,b->aa')
sage: m.is_primitive()
False
sage: f = WordMorphism({0:[1],1:[0]})
sage: f.is_primitive()
False
sage: s = WordMorphism('a->b,b->c,c->ab')
sage: s.is_primitive()
True
sage: s = WordMorphism('a->b,b->c,c->d,d->e,e->f,f->g,g->h,h->ab')
sage: s.is_primitive()
True
TESTS:
sage: m = WordMorphism('a->bb,b->aac')
sage: m.is_primitive()
Traceback (most recent call last):
...
TypeError: self (=a->bb, b->aac) is not an endomorphism
sage: m = WordMorphism('a->,b->',codomain=Words('ab'))
sage: m.is_primitive()
False
sage: m = WordMorphism('a->,b->')
sage: m.is_primitive()
Traceback (most recent call last):
...
TypeError: self (=a->, b->) is not an endomorphism
REFERENCES:
Returns True if self is prolongable on letter.
A morphism is prolongable on a letter
if
is a prefix of
.
INPUT:
OUTPUT:
Boolean
EXAMPLES:
sage: WordMorphism('a->ab,b->a').is_prolongable(letter='a')
True
sage: WordMorphism('a->ab,b->a').is_prolongable(letter='b')
False
sage: WordMorphism('a->ba,b->ab').is_prolongable(letter='b')
False
sage: (WordMorphism('a->ba,b->ab')^2).is_prolongable(letter='b')
True
sage: WordMorphism('a->ba,b->').is_prolongable(letter='b')
False
sage: WordMorphism('a->bb,b->aac').is_prolongable(letter='a')
False
We check that #8595 is fixed:
sage: s = WordMorphism({('a', 1) : [('a', 1), ('a', 2)], ('a', 2) : [('a', 1)]})
sage: s.is_prolongable(('a',1))
True
TESTS:
sage: WordMorphism('a->ab,b->b,c->ba').is_prolongable(letter='d')
Traceback (most recent call last):
...
TypeError: letter (=d) is not in the domain alphabet (={'a', 'b', 'c'})
sage: n0, n1 = matrix(2,[1,1,1,0]), matrix(2,[2,1,1,0])
sage: n = {'a':n0, 'b':n1}
sage: WordMorphism(n).is_prolongable(letter='a') #todo: not implemented
Traceback (most recent call last):
...
TypeError: codomain of self must be an instance of Words
Returns True if self is a -uniform morphism.
Let be a positive integer. A morphism
is called
-uniform
if for every letter
, we have
. In other
words, all images have length
. A morphism is called uniform if it
is
-uniform for some positive integer
.
INPUT:
EXAMPLES:
sage: phi = WordMorphism('a->ab,b->a')
sage: phi.is_uniform()
False
sage: phi.is_uniform(k=1)
False
sage: tau = WordMorphism('a->ab,b->ba')
sage: tau.is_uniform()
True
sage: tau.is_uniform(k=1)
False
sage: tau.is_uniform(k=2)
True
Get or set the actual latex layout (oneliner vs array).
INPUT:
EXAMPLES:
sage: s = WordMorphism('a->ab,b->ba')
sage: s.latex_layout()
'array'
sage: s.latex_layout('oneliner')
sage: s.latex_layout()
'oneliner'
Deprecated: Use _fixed_point_iterator() instead. See trac ticket #8595 for details.
Returns the list of all the conjugate morphisms of self.
DEFINITION:
Recall from Lothaire [1] (Section 2.3.4)
that is right conjugate of
,
noted
, if there exists
such that
for all , or equivalently that
, for all words
.
Clearly, this relation is not
symmetric so that we say that two morphisms
and
are conjugate, noted
, if
or
. It is easy to see that
conjugacy of morphisms is an equivalence relation.
REFERENCES:
EXAMPLES:
sage: m = WordMorphism('a->abbab,b->abb')
sage: m.list_of_conjugates()
[WordMorphism: a->babba, b->bab,
WordMorphism: a->abbab, b->abb,
WordMorphism: a->bbaba, b->bba,
WordMorphism: a->babab, b->bab,
WordMorphism: a->ababb, b->abb,
WordMorphism: a->babba, b->bba,
WordMorphism: a->abbab, b->bab]
sage: m = WordMorphism('a->aaa,b->aa')
sage: m.list_of_conjugates()
[WordMorphism: a->aaa, b->aa]
sage: WordMorphism('').list_of_conjugates()
[WordMorphism: ]
sage: m = WordMorphism('a->aba,b->aba')
sage: m.list_of_conjugates()
[WordMorphism: a->baa, b->baa,
WordMorphism: a->aab, b->aab,
WordMorphism: a->aba, b->aba]
sage: m = WordMorphism('a->abb,b->abbab,c->')
sage: m.list_of_conjugates()
[WordMorphism: a->bab, b->babba, c->,
WordMorphism: a->abb, b->abbab, c->,
WordMorphism: a->bba, b->bbaba, c->,
WordMorphism: a->bab, b->babab, c->,
WordMorphism: a->abb, b->ababb, c->,
WordMorphism: a->bba, b->babba, c->,
WordMorphism: a->bab, b->abbab, c->]
Returns a partition of the domain alphabet.
Let be an involution. There
exists a triple of sets
such that
;
,
and
are mutually disjoint and
,
,
.
These sets are not unique.
INPUT:
OUTPUT:
A tuple of three sets
EXAMPLES:
sage: m = WordMorphism('a->b,b->a')
sage: m.partition_of_domain_alphabet() #random ordering
({'a'}, {'b'}, {})
sage: m = WordMorphism('a->b,b->a,c->c')
sage: m.partition_of_domain_alphabet() #random ordering
({'a'}, {'b'}, {'c'})
sage: m = WordMorphism('a->a,b->b,c->c')
sage: m.partition_of_domain_alphabet() #random ordering
({}, {}, {'a', 'c', 'b'})
sage: m = WordMorphism('A->T,T->A,C->G,G->C')
sage: m.partition_of_domain_alphabet() #random ordering
({'A', 'C'}, {'T', 'G'}, {})
sage: I = WordMorphism({0:oo,oo:0,1:-1,-1:1,2:-2,-2:2,3:-3,-3:3})
sage: I.partition_of_domain_alphabet() #random ordering
({0, -1, -3, -2}, {1, 2, 3, +Infinity}, {})
TESTS:
sage: m = WordMorphism('a->b,b->a,c->a')
sage: m.partition_of_domain_alphabet()
Traceback (most recent call last):
...
TypeError: self (=a->b, b->a, c->a) is not an endomorphism
Return the periodic point of self that starts with letter.
EXAMPLES:
sage: f = WordMorphism('a->bab,b->aba')
sage: f.periodic_point('a')
word: abababababababababababababababababababab...
sage: f.fixed_point('a')
Traceback (most recent call last):
...
TypeError: self must be prolongable on a
Return the periodic points of f as a list of tuples where each tuple is a periodic orbit of f.
EXAMPLES:
sage: f = WordMorphism('a->aba,b->baa')
sage: for p in f.periodic_points():
... print len(p), ',', p[0]
1 , ababaaababaaabaabaababaaababaaabaabaabab...
1 , baaabaabaababaaabaababaaabaababaaababaaa...
sage: f = WordMorphism('a->bab,b->aa')
sage: for p in f.periodic_points():
... print len(p), ',', p[0]
2 , aababaaaababaababbabaababaababbabaababaa...
sage: f.fixed_points()
[]
This shows that ticket trac ticket #13668 has been resolved:
sage: d = {1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]}
sage: s = WordMorphism(d)
sage: s7 = s^7
sage: s7r = s7.reversal()
sage: s7r10 = s7r^10
sage: for p in s7r10.periodic_points(): p
[word: 1,10,9,8,7,6,5,4,3,2,10,9,8,7,6,5,4,3,2,...]
[word: 2,1,1,10,9,8,7,6,5,4,3,2,1,10,9,8,7,6,5,...]
[word: 3,2,2,1,2,1,1,10,9,8,7,6,5,4,3,2,2,1,1,1...]
[word: 4,3,2,3,2,2,1,3,2,2,1,2,1,1,10,9,8,7,6,5...]
[word: 5,4,3,2,4,3,2,3,2,2,1,4,3,2,3,2,2,1,3,2,...]
[word: 6543254324323221543243232214323221322121...]
[word: 7654326543254324323221654325432432322154...]
[word: 8765432765432654325432432322176543265432...]
[word: 9876543287654327654326543254324323221876...]
[word: 10,9,8,7,6,5,4,3,2,9,8,7,6,5,4,3,2,8,7,6...]
Returns the left eigenvector of the incidence matrix associated to the largest eigenvalue (in absolute value).
Unicity of the result is guaranteed when the multiplicity of the largest eigenvalue is one, for example when self is a Pisot irreductible substitution.
A substitution is Pisot irreducible if the characteristic
polynomial of its incidence matrix is irreducible over and
has all roots, except one, of modulus strictly smaller than 1.
INPUT:
EXAMPLES:
sage: m = WordMorphism('a->aaaabbc,b->aaabbc,c->aabc')
sage: matrix(m)
[4 3 2]
[2 2 1]
[1 1 1]
sage: m.pisot_eigenvector_left()
(1, 0.8392867552141611?, 0.5436890126920763?)
Returns the right eigenvector of the incidence matrix associated to the largest eigenvalue (in absolute value).
Unicity of the result is guaranteed when the multiplicity of the largest eigenvalue is one, for example when self is a Pisot irreductible substitution.
A substitution is Pisot irreducible if the characteristic
polynomial of its incidence matrix is irreducible over and
has all roots, except one, of modulus strictly smaller than 1.
INPUT:
EXAMPLES:
sage: m = WordMorphism('a->aaaabbc,b->aaabbc,c->aabc')
sage: matrix(m)
[4 3 2]
[2 2 1]
[1 1 1]
sage: m.pisot_eigenvector_right()
(1, 0.5436890126920763?, 0.2955977425220848?)
Returns a plot of the Rauzy fractal associated with a substitution.
The substitution does not have to be irreducible. The usual definition of a Rauzy fractal requires that its dominant eigenvalue is a Pisot number but the present method doesn’t require this, allowing to plot some interesting pictures in the non-Pisot case (see the examples below).
For more details about the definition of the fractal and the projection which is used, see Section 3.1 of [1].
Plots with less than 100,000 points take a few seconds, and several millions of points can be plotted in reasonable time.
Other ways to draw Rauzy fractals (and more generally projections of paths) can be found in sage.combinat.words.paths.FiniteWordPath_all.plot_projection() or in sage.combinat.e_one_star().
OUTPUT:
A Graphics object.
INPUT:
n - integer (default: None) The number of points used to plot the fractal. Default values: 1000 for a 1D fractal, 50000 for a 2D fractal, 10000 for a 3D fractal.
exchange - boolean (default: False). Plot the Rauzy fractal with domain exchange.
eig - a real element of QQbar of degree >= 2 (default: None). The eigenvalue used to plot the fractal. It must be an eigenvalue of self.incidence_matrix(). The one used by default the maximal eigenvalue of self.incidence_matrix() (usually a Pisot number), but for substitutions with more than 3 letters other interesting choices are sometimes possible.
translate - a list of vectors of RR^size_alphabet, or a dictionary from the alphabet to lists of vectors (default: None). Plot translated copies of the fractal. This option allows to plot tilings easily. The projection used for these vectors is the same as the projection used for the canonical basis to plot the fractal. If the input is a list, all the pieces will be translated and plotted. If the input is a dictionary, each piece will be translated and plotted accordingly to the vectors associated with each letter in the dictionary. Note: by default, the Rauzy fractal placed at the origin is not plotted with the translate option; the vector (0,0,...,0) has to be added manually.
prec - integer (default: 53). The number of bits used in the floating point representations of the points of the fractal.
colormap - color map or dictionary (default: 'hsv'). It can be one of the following :
- string - a coloring map. For available coloring map names type: sorted(colormaps)
- dict - a dictionary of the alphabet mapped to colors.
opacity - a dictionary from the alphabet to the real interval [0,1] (default: None). If none is specified, all letters are plotted with opacity 1.
plot_origin - a couple (k,c) (default: None). If specified, mark the origin by a point of size k and color c.
plot_basis - boolean (default: False). Plot the projection of the canonical basis with the fractal.
point_size - float (default: None). The size of the points used to plot the fractal.
EXAMPLES:
The Rauzy fractal of the Tribonacci substitution:
sage: s = WordMorphism('1->12,2->13,3->1')
sage: s.rauzy_fractal_plot() # long time
The “Hokkaido” fractal. We tweak the plot using the plotting options to get a nice reusable picture, in which we mark the origin by a black dot:
sage: s = WordMorphism('a->ab,b->c,c->d,d->e,e->a')
sage: G = s.rauzy_fractal_plot(n=100000, point_size=3, plot_origin=(50,"black")) # not tested
sage: G.show(figsize=10, axes=false) # not tested
Another “Hokkaido” fractal and its domain exchange:
sage: s = WordMorphism({1:[2], 2:[4,3], 3:[4], 4:[5,3], 5:[6], 6:[1]})
sage: s.rauzy_fractal_plot() # not tested takes > 1 second
sage: s.rauzy_fractal_plot(exchange=True) # not tested takes > 1 second
A three-dimensional Rauzy fractal:
sage: s = WordMorphism('1->12,2->13,3->14,4->1')
sage: s.rauzy_fractal_plot() # not tested takes > 1 second
A one-dimensional Rauzy fractal (very scattered):
sage: s = WordMorphism('1->2122,2->1')
sage: s.rauzy_fractal_plot().show(figsize=20) # not tested takes > 1 second
A high resolution plot of a complicated fractal:
sage: s = WordMorphism('1->23,2->123,3->1122233')
sage: G = s.rauzy_fractal_plot(n=300000) # not tested takes > 1 second
sage: G.show(axes=false, figsize=20) # not tested takes > 1 second
A nice colorful animation of a domain exchange:
sage: s = WordMorphism('1->21,2->3,3->4,4->25,5->6,6->7,7->1')
sage: L = [s.rauzy_fractal_plot(), s.rauzy_fractal_plot(exchange=True)] # not tested takes > 1 second
sage: animate(L, axes=false).show(delay=100) # not tested takes > 1 second
Plotting with only one color:
sage: s = WordMorphism('1->12,2->31,3->1')
sage: s.rauzy_fractal_plot(colormap={'1':'black', '2':'black', '3':'black'}) # not tested takes > 1 second
Different fractals can be obtained by choosing another (non-Pisot) eigenvalue:
sage: s = WordMorphism('1->12,2->3,3->45,4->5,5->6,6->7,7->8,8->1')
sage: E = s.incidence_matrix().eigenvalues()
sage: x = [x for x in E if -0.8 < x < -0.7][0]
sage: s.rauzy_fractal_plot() # not tested takes > 1 second
sage: s.rauzy_fractal_plot(eig=x) # not tested takes > 1 second
A Pisot reducible substitution with seemingly overlapping tiles:
sage: s = WordMorphism({1:[1,2], 2:[2,3], 3:[4], 4:[5], 5:[6], 6:[7], 7:[8], 8:[9], 9:[10], 10:[1]})
sage: s.rauzy_fractal_plot() # not tested takes > 1 second
A non-Pisot reducible substitution with a strange Rauzy fractal:
sage: s = WordMorphism({1:[3,2], 2:[3,3], 3:[4], 4:[1]})
sage: s.rauzy_fractal_plot() # not tested takes > 1 second
A substitution with overlapping tiles. We use the options colormap and opacity to study how the tiles overlap:
sage: s = WordMorphism('1->213,2->4,3->5,4->1,5->21')
sage: s.rauzy_fractal_plot() # not tested takes > 1 second
sage: s.rauzy_fractal_plot(colormap={'1':'red', '4':'purple'}) # not tested takes > 1 second
sage: s.rauzy_fractal_plot(opacity={'1':0.1,'2':1,'3':0.1,'4':0.1,'5':0.1}, n=150000) # not tested takes > 1 second
Funny experiments by playing with the precision of the float numbers used to plot the fractal:
sage: s = WordMorphism('1->12,2->13,3->1')
sage: s.rauzy_fractal_plot(prec=6) # not tested
sage: s.rauzy_fractal_plot(prec=9) # not tested
sage: s.rauzy_fractal_plot(prec=15) # not tested
sage: s.rauzy_fractal_plot(prec=19) # not tested
sage: s.rauzy_fractal_plot(prec=25) # not tested
Using the translate option to plot periodic tilings:
sage: s = WordMorphism('1->12,2->13,3->1')
sage: s.rauzy_fractal_plot(n=10000, translate=[(0,0,0),(-1,0,1),(0,-1,1),(1,-1,0),(1,0,-1),(0,1,-1),(-1,1,0)]) # not tested takes > 1 second
sage: t = WordMorphism("a->aC,b->d,C->de,d->a,e->ab") # substitution found by Julien Bernat
sage: V = [vector((0,0,1,0,-1)), vector((0,0,1,-1,0))]
sage: S = set(map(tuple, [i*V[0] + j*V[1] for i in [-1,0,1] for j in [-1,0,1]]))
sage: t.rauzy_fractal_plot(n=10000, translate=S, exchange=true) # not tested takes > 1 second
Using the translate option to plot arbitrary tilings with the fractal pieces. This can be used for example to plot the self-replicating tiling of the Rauzy fractal:
sage: s = WordMorphism({1:[1,2], 2:[3], 3:[4,3], 4:[5], 5:[6], 6:[1]})
sage: s.rauzy_fractal_plot() # not tested takes > 1 second
sage: D = {1:[(0,0,0,0,0,0), (0,1,0,0,0,0)], 3:[(0,0,0,0,0,0), (0,1,0,0,0,0)], 6:[(0,1,0,0,0,0)]}
sage: s.rauzy_fractal_plot(n=30000, translate=D) # not tested takes > 1 second
Plot the projection of the canonical basis with the fractal:
sage: s = WordMorphism({1:[2,1], 2:[3], 3:[6,4], 4:[5,1], 5:[6], 6:[7], 7:[8], 8:[9], 9:[1]})
sage: s.rauzy_fractal_plot(plot_basis=True) # not tested takes > 1 second
TESTS:
sage: s = WordMorphism('a->ab,b->c,c->d,d->e,e->a')
sage: s.rauzy_fractal_plot(n=1000, colormap='Set1', opacity={'a':0.5,'b':1,'c':0.7,'d':0,'e':0.2}, plot_origin=(100,"black"), plot_basis=True, point_size=2.5)
REFERENCES:
AUTHOR:
Timo Jolivet (2012-06-16)
Returns a dictionary of list of points associated with the pieces of the Rauzy fractal of self.
INPUT:
See the method rauzy_fractal_plot() for a description of the options and more examples.
OUTPUT:
dictionary of list of points
EXAMPLES:
The Rauzy fractal of the Tribonacci substitution and the number of points in the piece of the fractal associated with '1', '2' and '3' are respectively:
sage: s = WordMorphism('1->12,2->13,3->1')
sage: D = s.rauzy_fractal_points(n=100)
sage: len(D['1'])
54
sage: len(D['2'])
30
sage: len(D['3'])
16
TESTS:
sage: s = WordMorphism('1->12,2->13,3->1')
sage: D = s.rauzy_fractal_points(n=100, exchange=True, translate=[(3,1,-2), (5,-33,8)], prec=40)
sage: len(D['1'])
108
AUTHOR:
Timo Jolivet (2012-06-16)
Returns a dictionary giving the projection of the canonical basis.
See the method rauzy_fractal_plot() for more details about the projection.
INPUT:
OUTPUT:
dictionary, letter -> vector, giving the projection
EXAMPLES:
The projection for the Rauzy fractal of the Tribonacci substitution is:
sage: s = WordMorphism('1->12,2->13,3->1')
sage: s.rauzy_fractal_projection()
{'1': (1.00..., 0.00...), '3': (-0.77..., 1.11...), '2': (-1.41..., -0.60...)}
TESTS:
sage: t = WordMorphism('1->12,2->3,3->45,4->5,5->6,6->7,7->8,8->1')
sage: E = t.incidence_matrix().eigenvalues()
sage: x = [x for x in E if -0.8 < x < -0.7][0]
sage: t.rauzy_fractal_projection(prec=10)
{'1': (1.0, 0.00), '3': (0.79, 1.3), '2': (-1.7, -0.56), '5': (-1.7, -0.56), '4': (1.9, -0.74), '7': (0.21, -1.3), '6': (0.79, 1.3), '8': (-0.88, 0.74)}
sage: t.rauzy_fractal_projection(eig=x, prec=10)
{'1': (1.0, 0.00), '3': (-0.66, -0.56), '2': (-0.12, -0.74), '5': (-0.54, 0.18), '4': (-0.46, -0.18), '7': (0.12, 0.74), '6': (-0.34, 0.56), '8': (0.66, 0.56)}
AUTHOR:
Timo Jolivet (2012-06-16)
Returns a restriction of self to the given alphabet.
INPUT:
OUTPUT:
WordMorphism
EXAMPLES:
sage: m = WordMorphism('a->b,b->a')
sage: m.restrict_domain('a')
WordMorphism: a->b
sage: m.restrict_domain('')
WordMorphism:
sage: m.restrict_domain('A')
WordMorphism:
sage: m.restrict_domain('Aa')
WordMorphism: a->b
The input alphabet must be iterable:
sage: m.restrict_domain(66)
Traceback (most recent call last):
...
TypeError: 'sage.rings.integer.Integer' object is not iterable
Returns the reversal of self.
EXAMPLES:
sage: WordMorphism('6->ab,y->5,0->asd').reversal()
WordMorphism: 0->dsa, 6->ba, y->5
sage: WordMorphism('a->ab,b->a').reversal()
WordMorphism: a->ba, b->a
Return the cycle of the function f on the finite set domain. It is assumed that f is an endomorphism.
INPUT:
EXAMPLES:
sage: from sage.combinat.words.morphism import get_cycles
sage: get_cycles(lambda i: (i+1)%3, domain=[0,1,2])
[(0, 1, 2)]
sage: get_cycles(lambda i: [0,0,0][i], domain=[0,1,2])
[(0,)]
sage: get_cycles(lambda i: [1,1,1][i], domain=[0,1,2])
[(1,)]