Word morphisms/substitutions#

This module implements morphisms over finite and infinite words.

AUTHORS:

  • Sébastien Labbé (2007-06-01): initial version

  • Sébastien Labbé (2008-07-01): merged into sage-words

  • Sébastien Labbé (2008-12-17): merged into sage

  • Sébastien Labbé (2009-02-03): words next generation

  • Sébastien Labbé (2009-11-20): allowing the choice of the datatype of the image. Doc improvements.

  • Stepan Starosta (2012-11-09): growing letters

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

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
class sage.combinat.words.morphism.PeriodicPointIterator(m, cycle)#

Bases: object

(Lazy) constructor of the periodic points of a word morphism.

This class is mainly used in WordMorphism.periodic_point and WordMorphism.periodic_points.

EXAMPLES:

sage: from sage.combinat.words.morphism import PeriodicPointIterator
sage: s = WordMorphism('a->bacca,b->cba,c->aab')
sage: p = PeriodicPointIterator(s, ['a','b','c'])
sage: p._cache[0]
lazy list ['a', 'a', 'b', ...]
sage: p._cache[1]
lazy list ['b', 'a', 'c', ...]
sage: p._cache[2]
lazy list ['c', 'b', 'a', ...]
get_iterator(i)#

Internal method.

EXAMPLES:

sage: from sage.combinat.words.morphism import PeriodicPointIterator
sage: s = WordMorphism('a->bacca,b->cba,c->aab')
sage: p = PeriodicPointIterator(s, ['a','b','c'])
sage: p.get_iterator(0)
<generator object ...get_iterator at ...>
class sage.combinat.words.morphism.WordMorphism(data, domain=None, codomain=None)#

Bases: sage.structure.sage_object.SageObject

WordMorphism class

INPUT:

  • data – dict or str or an instance of WordMorphism, the map giving the image of letters

  • domain – (optional:None) set of words over a given alphabet. If None, the domain alphabet is computed from data and is sorted.

  • codomain – (optional:None) set of words over a given alphabet. If None, the codomain alphabet is computed from data and is sorted.

Note

When the domain or the codomain are not explicitly given, it is expected that the letters are comparable because the alphabets of the domain and of the codomain are sorted.

EXAMPLES:

From a dictionary:

sage: n = WordMorphism({0:[0,2,2,1],1:[0,2],2:[2,2,1]})
sage: n
WordMorphism: 0->0221, 1->02, 2->221

From a string with '->' as separation:

sage: m = WordMorphism('x->xyxsxss,s->xyss,y->ys')
sage: m
WordMorphism: s->xyss, x->xyxsxss, y->ys
sage: m.domain()
Finite words over {'s', 'x', 'y'}
sage: m.codomain()
Finite words over {'s', 'x', 'y'}

Specifying the domain and codomain:

sage: W = FiniteWords([0,1,2])
sage: d = {0:[0,1], 1:[0,1,0], 2:[0]}
sage: m = WordMorphism(d, domain=W, codomain=W)
sage: m([0]).parent()
Finite words over {0, 1, 2}

When the alphabet is non-sortable, the domain and/or codomain must be explicitly given:

sage: W = FiniteWords(['a',6])
sage: d = {'a':['a',6,'a'],6:[6,6,6,'a']}
sage: WordMorphism(d, domain=W, codomain=W)
WordMorphism: 6->666a, a->a6a
abelian_rotation_subspace()#

Return 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:
[]
codomain()#

Return the codomain of self.

EXAMPLES:

sage: WordMorphism('a->ab,b->a').codomain()
Finite words over {'a', 'b'}
sage: WordMorphism('6->ab,y->5,0->asd').codomain()
Finite words over {'5', 'a', 'b', 'd', 's'}
conjugate(pos)#

Return the morphism where the image of the letter by self is conjugated of parameter pos.

INPUT:

  • pos - integer

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
domain()#

Return domain of self.

EXAMPLES:

sage: WordMorphism('a->ab,b->a').domain()
Finite words over {'a', 'b'}
sage: WordMorphism('b->ba,a->ab').domain()
Finite words over {'a', 'b'}
sage: WordMorphism('6->ab,y->5,0->asd').domain()
Finite words over {'0', '6', 'y'}
dual_map(k=1)#

Return the dual map \(E_k^*\) of self (see [1]).

Note

It is actually implemented only for \(k=1\).

INPUT:

  • self - unimodular endomorphism defined on integers 1, 2, \ldots, d

  • k - integer (optional, default: 1)

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:

  • [1] Sano, Y., Arnoux, P. and Ito, S., Higher dimensional extensions of substitutions and their dual maps, Journal d’Analyse Mathématique 83 (2001), 183-206.

extend_by(other)#

Return self extended by other.

Let \(\varphi_1:A^*\rightarrow B^*\) and \(\varphi_2:C^*\rightarrow D^*\) be two morphisms. A morphism \(\mu:(A\cup C)^*\rightarrow (B\cup D)^*\) corresponds to \(\varphi_1\) extended by \(\varphi_2\) if \(\mu(a)=\varphi_1(a)\) if \(a\in A\) and \(\mu(a)=\varphi_2(a)\) otherwise.

INPUT:

  • other - a WordMorphism.

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
fixed_point(letter)#

Return the fixed point of self beginning by the given letter.

A fixed point of morphism \(\varphi\) is a word \(w\) such that \(\varphi(w) = w\).

INPUT:

  • self - an endomorphism (or more generally a self-composable morphism), must be prolongable on letter

  • letter - in the domain of self, the first letter of the fixed point.

OUTPUT:

  • word - the fixed point of self beginning with letter.

EXAMPLES:

sage: W = FiniteWords('abc')

  1. 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: WordMorphism('a->ab,b->b,c->ba', codomain=W).fixed_point(letter='a')
word: abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

  2. Infinite fixed point of an erasing morphism:

    sage: WordMorphism('a->ab,b->,c->ba', codomain=W).fixed_point(letter='a')
word: ab

  3. Finite fixed point:

    sage: WordMorphism('a->ab,b->b,c->ba', codomain=W).fixed_point(letter='b')
word: b
sage: _.parent()
Finite words over {'a', 'b', 'c'}

sage: WordMorphism('a->ab,b->cc,c->', codomain=W).fixed_point(letter='a')
word: abcc
sage: _.parent()
Finite words over {'a', 'b', 'c'}

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

  1. Fixed point of a power of a morphism:

    sage: m = WordMorphism('a->ba,b->ab')
sage: (m^2).fixed_point(letter='a')
word: abbabaabbaababbabaababbaabbabaabbaababba...

  2. With a self-composable but not endomorphism

    sage: m = WordMorphism(‘a->cbc,b->bc,c->b’) sage: m.is_endomorphism() False sage: m.fixed_point(‘b’) word: bcbbcbcbbcbbcbcbbcbcbbcbbcbcbbcbbcbcbbcb…

fixed_points()#

Return 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.periodic_point(2)
word: 2,1,1,10,9,8,7,6,5,4,3,2,1,10,9,8,7,6,5,4,3,2,10,9,8,7,6,5,4,3,2,9,8,7,6,5,4,3,2,8,...

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()
[]
growing_letters()#

Return 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']
sage: WordMorphism('a->b,b->a').growing_letters()
[]
sage: WordMorphism('a->b,b->c,c->d,d->c', codomain=Words('abcd')).growing_letters()
[]
has_conjugate_in_classP(f=None)#

Return True if self has a conjugate in class \(f\)-\(P\).

DEFINITION : Let \(A\) be an alphabet. We say that a primitive substitution \(S\) is in the class P if there exists a palindrome \(p\) and for each \(b\in A\) a palindrome \(q_b\) such that \(S(b)=pq_b\) for all \(b\in A\). [1]

Let \(f\) be an involution on \(A\). We say that a morphism \(\varphi\) is in class \(f\)-\(P\) if there exists an \(f\)-palindrome \(p\) and for each \(\alpha \in A\) there exists an \(f\)-palindrome \(q_\alpha\) such that \(\varphi(\alpha)=pq_\alpha\). [2]

INPUT:

  • f - involution (default: None) on the alphabet of self. It must be callable on letters as well as words (e.g. WordMorphism).

REFERENCES:

  • [1] Hof, A., O. Knill et B. Simon, Singular continuous spectrum for palindromic Schrödinger operators, Commun. Math. Phys. 174 (1995) 149-159.

  • [2] Labbe, Sebastien. Proprietes combinatoires des \(f\)-palindromes, Memoire de maitrise en Mathematiques, Montreal, UQAM, 2008, 109 pages.

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
has_left_conjugate()#

Return 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
has_right_conjugate()#

Return 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
image(letter)#

Return the image of a letter.

INPUT:

  • letter – a letter in the domain alphabet

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({'b':[1,2], 'a':(2,3,4), 'z':[9,8,7]})
sage: s.image('b')
word: 12
sage: s.image('a')
word: 234
sage: s.image('z')
word: 987
images()#

Return the list of all the images of the letters of the alphabet under self.

EXAMPLES:

sage: sorted(WordMorphism('a->ab,b->a').images())
[word: a, word: ab]
sage: sorted(WordMorphism('6->ab,y->5,0->asd').images())
[word: 5, word: ab, word: asd]
immortal_letters()#

Return the list of immortal letters.

A letter \(a\) is immortal for the morphism \(s\) if the length of the iterates of \(| s^n(a) |\) is larger than zero as \(n\) goes to infinity.

Requires this morphism to be self-composable.

EXAMPLES:

sage: WordMorphism('a->a').immortal_letters()
['a']
sage: WordMorphism('a->b,b->a').immortal_letters()
['a', 'b']
sage: WordMorphism('a->abcd,b->cd,c->dd,d->').immortal_letters()
['a']
sage: WordMorphism('a->bc,b->cac,c->de,d->,e->').immortal_letters()
['a', 'b']
sage: WordMorphism('a->', domain=Words('a'), codomain=Words('a')).immortal_letters()
[]

sage: WordMorphism('a->').immortal_letters()
[]
incidence_matrix()#

Return 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]
infinite_repetitions_primitive_roots(w=None, allow_growing=None)#

Return the set of primitive roots (up to conjugacy) of infinite repetitions from the language \(\{m^n(w) | n \ge 0\}\), where \(m\) is this morphism and \(w\) is a word inputted as a parameter.

Requires this morphism to be an endomorphism.

The word \(v^\omega\) is an infinite repetition (in other words, an infinite periodic factor) of a language, if \(v\) is a non-empty word and for each positive integer \(k\) the word \(v^k\) is a factor of some word from the language. It turns out that a language created by iterating a morphism has a finite number of primitive roots of infinite repetitions.

If \(v\) is a primitive root of an infinite repetition, then all its conjugations are also primitive roots of an infinite repetition. For simplicity’s sake this method returns only the lexicographically minimal one from each conjugacy class.

INPUT:

  • w – finite iterable (default: self.domain().alphabet()). Represents a word used to start the language.

  • allow_growing – boolean or None (default: None). If False, return only the primitive roots that contain no growing letters. If True, return only the primitive roots that contain at least one growing letter. If None, return both.

ALGORITHM:

The algorithm used is described in detail in [KS2015].

EXAMPLES:

sage: m = WordMorphism('a->aba,b->aba,c->cd,d->e,e->d')
sage: inf_reps = m.infinite_repetitions_primitive_roots('ac')
sage: sorted(inf_reps)
[word: aab, word: de]

allow_growing parameter:

sage: sorted(m.infinite_repetitions_primitive_roots('ac', True))
[word: aab]
sage: sorted(m.infinite_repetitions_primitive_roots('ac', False))
[word: de]

Incomplete check that these words are indeed the primitive roots of infinite repetitions:

sage: SL = m._language_naive(10, Word('ac'))
sage: all(x in SL for x in inf_reps)
True
sage: all(x^2 in SL for x in inf_reps)
True
sage: all(x^3 in SL for x in inf_reps)
True

Large example:

sage: m = WordMorphism('a->1b5,b->fcg,c->dae,d->432,e->678,f->f,g->g,1->2,2->3,3->4,4->1,5->6,6->7,7->8,8->5')
sage: sorted(m.infinite_repetitions_primitive_roots('a'))
[word: 1432f2143f3214f4321f, word: 5678g8567g7856g6785g]
is_empty()#

Return 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
is_endomorphism()#

Return whether self is an endomorphism, that is if the domain coincide with the codomain.

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', domain=P, codomain=P)
sage: m.is_endomorphism()
True
is_erasing()#

Return 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
is_growing(letter=None)#

Return True if letter is a growing letter.

A letter \(a\) is growing for the morphism \(s\) if the length of the iterates of \(| s^n(a) |\) tend to infinity as \(n\) goes to infinity.

INPUT:

  • letter – None or a letter in the domain of self

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.

is_identity()#

Return 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 trac ticket #8618 is fixed:

sage: t = WordMorphism({'a1':['a2'], 'a2':['a1']})
sage: (t*t).is_identity()
True
is_in_classP(f=None)#

Return True if self is in class \(P\) (or \(f\)-\(P\)).

DEFINITION : Let \(A\) be an alphabet. We say that a primitive substitution \(S\) is in the class P if there exists a palindrome \(p\) and for each \(b\in A\) a palindrome \(q_b\) such that \(S(b)=pq_b\) for all \(b\in A\). [1]

Let \(f\) be an involution on \(A\). “We say that a morphism \(\varphi\) is in class \(f\)-\(P\) if there exists an \(f\)-palindrome \(p\) and for each \(\alpha \in A\) there exists an \(f\)-palindrome \(q_\alpha\) such that \(\varphi(\alpha)=pq_\alpha\). [2]

INPUT:

  • f - involution (default: None) on the alphabet of self. It must be callable on letters as well as words (e.g. WordMorphism).

REFERENCES:

  • [1] Hof, A., O. Knill et B. Simon, Singular continuous spectrum for palindromic Schrödinger operators, Commun. Math. Phys. 174 (1995) 149-159.

  • [2] Labbe, Sebastien. Proprietes combinatoires des \(f\)-palindromes, Memoire de maitrise en Mathematiques, Montreal, UQAM, 2008, 109 pages.

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
is_injective()#

Return whether this morphism is injective.

ALGORITHM:

Uses a version of Wikipedia article Sardinas–Patterson_algorithm. Time complexity is on average quadratic with regards to the size of the morphism.

EXAMPLES:

sage: WordMorphism('a->0,b->10,c->110,d->111').is_injective()
True
sage: WordMorphism('a->00,b->01,c->012,d->20001').is_injective()
False
is_involution()#

Return True if self is an involution, i.e. its square is the identity.

INPUT:

  • self - an endomorphism

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
is_primitive()#

Return True if self is primitive.

A morphism \(\varphi\) is primitive if there exists an positive integer \(k\) such that for all \(\alpha\in\Sigma\), \(\varphi^k(\alpha)\) contains all the letters of \(\Sigma\).

INPUT:

  • self - an endomorphism

ALGORITHM:

Exercices 8.7.8, p.281 in [1]: (c) Let \(y(M)\) be the least integer \(e\) such that \(M^e\) has all positive entries. Prove that, for all primitive matrices \(M\), we have \(y(M) \leq (d-1)^2 + 1\). (d) Prove that the bound \(y(M)\leq (d-1)^2+1\) 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

REFERENCES:

  • [1] Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.

is_prolongable(letter)#

Return True if self is prolongable on letter.

A morphism \(\varphi\) is prolongable on a letter \(a\) if \(a\) is a prefix of \(\varphi(a)\).

INPUT:

  • self - its codomain must be an instance of Words

  • letter - a letter in the domain alphabet

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 trac ticket #8595 is fixed:

sage: s = WordMorphism({('a', 1) : [('a', 1), ('a', 2)], ('a', 2) : [('a', 1)]})
sage: s.is_prolongable(('a',1))
True
is_pushy(w=None)#

Return whether the language \(\{m^n(w) | n \ge 0\}\) is pushy, where \(m\) is this morphism and \(w\) is a word inputted as a parameter.

Requires this morphism to be an endomorphism.

A language created by iterating a morphism is pushy, if its words contain an infinite number of factors containing no growing letters. It turns out that this is equivalent to having at least one infinite repetition containing no growing letters.

See infinite_repetitions_primitive_roots() and is_growing().

INPUT:

  • w – finite iterable (default: self.domain().alphabet()). Represents a word used to start the language.

EXAMPLES:

sage: WordMorphism('a->abca,b->bc,c->').is_pushy()
False
sage: WordMorphism('a->abc,b->,c->bcb').is_pushy()
True
is_repetitive(w=None)#

Return whether the language \(\{m^n(w) | n \ge 0\}\) is repetitive, where \(m\) is this morphism and \(w\) is a word inputted as a parameter.

Requires this morphism to be an endomorphism.

A language is repetitive, if for each positive integer \(k\) there exists a word \(u\) such that \(u^k\) is a factor of some word of the language.

It turns out that for languages created by iterating a morphism this is equivalent to having at least one infinite repetition (this property is also known as strong repetitiveness).

See infinite_repetitions_primitive_roots().

INPUT:

  • w – finite iterable (default: self.domain().alphabet()). Represents a word used to start the language.

EXAMPLES:

This method can be used to check whether a purely morphic word is not k-power free for all positive integers k. For example, the language containing just the Thue-Morse word and its prefixes is not repetitive, since the Thue-Morse word is cube-free:

sage: WordMorphism('a->ab,b->ba').is_repetitive('a')
False

Similarly, the Hanoi word is square-free:

sage: WordMorphism('a->aC,A->ac,b->cB,B->cb,c->bA,C->ba').is_repetitive('a')
False

However, this method solves a more general problem, as it can be called on any morphism \(m\) and with any word \(w\):

sage: WordMorphism('a->c,b->cda,c->a,d->abc').is_repetitive('bd')
True
is_self_composable()#

Return whether the codomain of self is contained in the domain.

EXAMPLES:

sage: f = WordMorphism('a->a,b->a')
sage: f.is_endomorphism()
False
sage: f.is_self_composable()
True
is_unboundedly_repetitive(w=None)#

Return whether the language \(\{m^n(w) | n \ge 0\}\) is unboundedly repetitive, where \(m\) is this morphism and \(w\) is a word inputted as a parameter.

Requires this morphism to be an endomorphism.

A language created by iterating a morphism is unboundedly repetitive, if it has at least one infinite repetition containing at least one growing letter.

See infinite_repetitions_primitive_roots() and is_growing().

INPUT:

  • w – finite iterable (default: self.domain().alphabet()). Represents a word used to start the language.

EXAMPLES:

sage: WordMorphism('a->abca,b->bc,c->').is_unboundedly_repetitive()
True
sage: WordMorphism('a->abc,b->,c->bcb').is_unboundedly_repetitive()
False
is_uniform(k=None)#

Return True if self is a \(k\)-uniform morphism.

Let \(k\) be a positive integer. A morphism \(\phi\) is called \(k\)-uniform if for every letter \(\alpha\), we have \(|\phi(\alpha)| = k\). In other words, all images have length \(k\). A morphism is called uniform if it is \(k\)-uniform for some positive integer \(k\).

INPUT:

  • k - a positive integer or None. If set to a positive integer, then the function return True if self is \(k\)-uniform. If set to None, then the function return True if self is uniform.

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
language(n, u=None)#

Return the words of length n in the language generated by this substitution.

Given a non-erasing substitution \(s\) and a word \(u\) the DOL-language generated by \(s\) and \(u\) is the union of the factors of \(s^n(u)\) where \(n\) is a non-negative integer.

INPUT:

  • n – non-negative integer - length of the words in the language

  • u – a word or None (optional, default None) - if set to None some letter of the alphabet is used

OUTPUT: a Python set

EXAMPLES:

The fibonacci morphism:

sage: s = WordMorphism({0: [0,1], 1:[0]})
sage: sorted(s.language(3))
[word: 001, word: 010, word: 100, word: 101]
sage: len(s.language(1000))
1001
sage: all(len(s.language(n)) == n+1 for n in range(100))
True

A growing but non-primitive example. The DOL-languages generated by 0 and 2 are different:

sage: s = WordMorphism({0: [0,1], 1:[0], 2:[2,0,2]})

sage: u = s.fixed_point(0)
sage: A0 = u[:200].factor_set(5)
sage: B0 = s.language(5, [0])
sage: set(A0) == B0
True

sage: v = s.fixed_point(2)
sage: A2 = v[:200].factor_set(5)
sage: B2 = s.language(5, [2])
sage: set(A2) == B2
True

sage: len(A0), len(A2)
(6, 20)

The Chacon transformation (non-primitive):

sage: s = WordMorphism({0: [0,0,1,0], 1:[1]})
sage: sorted(s.language(10))
[word: 0001000101,
 word: 0001010010,
 ...
 word: 1010010001,
 word: 1010010100]
latex_layout(layout=None)#

Get or set the actual latex layout (oneliner vs array).

INPUT:

  • layout - string (default: None), can take one of the following values:

    • None - Returns the actual latex layout. By default, the layout is 'array'

    • 'oneliner' - Set the layout to 'oneliner'

    • 'array' - Set the layout to 'array'

EXAMPLES:

sage: s = WordMorphism('a->ab,b->ba')
sage: s.latex_layout()
'array'
sage: s.latex_layout('oneliner')
sage: s.latex_layout()
'oneliner'
letter_growth_types()#

Return the mortal, polynomial and exponential growing letters.

The growth of \(| s^n(a) |\) as \(n\) goes to \(\infty\) is always of the form \(\alpha^n n^\beta\) (where \(\alpha\) is a Perron number and \(\beta\) an integer).

Without doing any linear algebra three cases can be differentiated: mortal (ultimately empty or \(\alpha=0\)); polynomial (\(\alpha=1\)); exponential (\(\alpha > 1\)). This is what is done in this method.

It requires this morphism to be an endomorphism.

OUTPUT:

The output is a 3-tuple of lists (mortal, polynomial, exponential) where:

  • mortal: list of mortal letters

  • polynomial: a list of lists where polynomial[i] is the list of letters with growth \(n^i\).

  • exponential: list of at least exponentionally growing letters

EXAMPLES:

sage: s = WordMorphism('a->abc,b->bc,c->c')
sage: mortal, poly, expo = s.letter_growth_types()
sage: mortal
[]
sage: poly
[['c'], ['b'], ['a']]
sage: expo
[]

When three mortal letters (c, d, and e), and two letters (a, b) are not growing:

sage: s = WordMorphism('a->bc,b->cac,c->de,d->,e->')
sage: s^20
WordMorphism: a->cacde, b->debcde, c->, d->, e->
sage: mortal, poly, expo = s.letter_growth_types()
sage: mortal
['c', 'd', 'e']
sage: poly
[['a', 'b']]
sage: expo
[]

sage: s = WordMorphism('a->abcd,b->bc,c->c,d->a')
sage: mortal, poly, expo = s.letter_growth_types()
sage: mortal
[]
sage: poly
[['c'], ['b']]
sage: expo
['a', 'd']
list_of_conjugates()#

Return the list of all the conjugate morphisms of self.

DEFINITION:

Recall from Lothaire [1] (Section 2.3.4) that \(\varphi\) is right conjugate of \(\varphi'\), noted \(\varphi\triangleleft\varphi'\), if there exists \(u \in \Sigma^*\) such that

\[\varphi(\alpha)u = u\varphi'(\alpha),\]

for all \(\alpha \in \Sigma\), or equivalently that \(\varphi(x)u = u\varphi'(x)\), for all words \(x \in \Sigma^*\). Clearly, this relation is not symmetric so that we say that two morphisms \(\varphi\) and \(\varphi'\) are conjugate, noted \(\varphi\bowtie\varphi'\), if \(\varphi\triangleleft\varphi'\) or \(\varphi'\triangleleft\varphi\). It is easy to see that conjugacy of morphisms is an equivalence relation.

REFERENCES:

  • [1] M. Lothaire, Algebraic Combinatorics on words, Cambridge University Press, 2002.

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->]
partition_of_domain_alphabet()#

Return a partition of the domain alphabet.

Let \(\varphi:\Sigma^*\rightarrow\Sigma^*\) be an involution. There exists a triple of sets \((A, B, C)\) such that

  • \(A \cup B \cup C =\Sigma\);

  • \(A\), \(B\) and \(C\) are mutually disjoint and

  • \(\varphi(A)= B\), \(\varphi(B)= A\), \(\varphi(C)= C\).

These sets are not unique.

INPUT:

  • self - An involution.

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}, {})
periodic_point(letter)#

Return the periodic point of self that starts with letter.

EXAMPLES:

sage: f = WordMorphism('a->bab,b->ab')
sage: f.periodic_point('a')
word: abbababbababbabababbababbabababbababbaba...
sage: f.fixed_point('a')
Traceback (most recent call last):
...
TypeError: self must be prolongable on a

Make sure that trac ticket #31759 is fixed:

sage: WordMorphism('a->b,b->a').periodic_point('a')
word: a
periodic_points()#

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("{} , {}".format(len(p), p[0]))
1 , ababaaababaaabaabaababaaababaaabaabaabab...
1 , baaabaabaababaaabaababaaabaababaaababaaa...

sage: f = WordMorphism('a->bab,b->aa')
sage: for p in f.periodic_points():
....:     print("{} , {}".format(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: for p in s7r.periodic_points(): p
[word: 1,10,9,8,7,6,5,4,3,2,10,9,8,7,6,5,4,3,2,...,
 word: 8765432765432654325432432322176543265432...,
 word: 5,4,3,2,4,3,2,3,2,2,1,4,3,2,3,2,2,1,3,2,...,
 word: 2,1,1,10,9,8,7,6,5,4,3,2,1,10,9,8,7,6,5,...,
 word: 9876543287654327654326543254324323221876...,
 word: 6543254324323221543243232214323221322121...,
 word: 3,2,2,1,2,1,1,10,9,8,7,6,5,4,3,2,2,1,1,1...,
 word: 10,9,8,7,6,5,4,3,2,9,8,7,6,5,4,3,2,8,7,6...,
 word: 7654326543254324323221654325432432322154...,
 word: 4,3,2,3,2,2,1,3,2,2,1,2,1,1,10,9,8,7,6,5...]

Make sure that trac ticket #31454 is fixed:

sage: WordMorphism('a->a,b->bb').periodic_points()
[[word: bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...]]
pisot_eigenvector_left()#

Return 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 \(\QQ\) and has all roots, except one, of modulus strictly smaller than 1.

INPUT:

  • self - a Pisot irreducible substitution.

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?)
pisot_eigenvector_right()#

Return 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 \(\QQ\) and has all roots, except one, of modulus strictly smaller than 1.

INPUT:

  • self - a Pisot irreducible substitution.

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?)
rauzy_fractal_plot(n=None, exchange=False, eig=None, translate=None, prec=53, colormap='hsv', opacity=None, plot_origin=None, plot_basis=False, point_size=None)#

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

  1. The Rauzy fractal of the Tribonacci substitution:

    sage: s = WordMorphism('1->12,2->13,3->1')
sage: s.rauzy_fractal_plot()     # long time
Graphics object consisting of 3 graphics primitives

  2. 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

  3. 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

  4. 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

  5. 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

  6. 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

  7. 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

  8. 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

  9. 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

  10. 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

  11. 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

  12. 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

  13. 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

  14. 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

  15. 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

  16. 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

REFERENCES:

AUTHOR:

Timo Jolivet (2012-06-16)

rauzy_fractal_points(n=None, exchange=False, eig=None, translate=None, prec=53)#

Return 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

AUTHOR:

Timo Jolivet (2012-06-16)

rauzy_fractal_projection(eig=None, prec=53)#

Return a dictionary giving the projection of the canonical basis.

See the method rauzy_fractal_plot() for more details about the projection.

INPUT:

  • eig - a real element of QQbar of degree >= 2 (default: None). The eigenvalue used for the projection. It must be an eigenvalue of self.incidence_matrix(). The one used by default is 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.

  • prec - integer (default: 53). The number of bits used in the floating point representations of the coordinates.

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.00000000000000, 0.000000000000000),
 '2': (-1.41964337760708, -0.606290729207199),
 '3': (-0.771844506346038, 1.11514250803994)}

AUTHOR:

Timo Jolivet (2012-06-16)

restrict_domain(alphabet)#

Return a restriction of self to the given alphabet.

INPUT:

  • alphabet - an iterable

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
reversal()#

Return 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
simplify_alphabet_size(Z=None)#

If this morphism is simplifiable, return morphisms \(h\) and \(k\) such that this morphism is simplifiable with respect to \(h\) and \(k\), otherwise raise ValueError.

This method is quite fast if this morphism is non-injective, but very slow if it is injective.

Let \(f: X^* \rightarrow Y^*\) be a morphism. Then \(f\) is simplifiable with respect to morphisms \(h: X^* \rightarrow Z^*\) and \(k: Z^* \rightarrow Y^*\), if \(f = k \circ h\) and \(|Z| < |X|\). If also \(Y \subseteq X\), then the morphism \(g: Z^* \rightarrow Z^* = h \circ k\) is a simplification of \(f\) (with respect to \(h\) and \(k\)).

Loosely speaking, a morphism is simplifiable if it contains “more letters than is needed”. Non-injectivity implies simplifiability. Simplification preserves some properties of the original morphism (e.g. repetitiveness).

For more information see Section 3 in [KO2000].

INPUT:

  • Z – iterable (default: self.domain().alphabet()), whose elements are used as an alphabet for the simplification.

EXAMPLES:

Example of a simplifiable (non-injective) morphism:

sage: f = WordMorphism('a->aca,b->badc,c->acab,d->adc')
sage: h, k = f.simplify_alphabet_size('xyz'); h, k
(WordMorphism: a->x, b->zy, c->xz, d->y, WordMorphism: x->aca, y->adc, z->b)
sage: k * h == f
True
sage: g = h * k; g
WordMorphism: x->xxzx, y->xyxz, z->zy

Example of a simplifiable (injective) morphism:

sage: f = WordMorphism('a->abcc,b->abcd,c->abdc,d->abdd')
sage: h, k = f.simplify_alphabet_size('xyz'); h, k
(WordMorphism: a->xyy, b->xyz, c->xzy, d->xzz, WordMorphism: x->ab, y->c, z->d)
sage: k * h == f
True
sage: g = h * k; g
WordMorphism: x->xyyxyz, y->xzy, z->xzz

Example of a non-simplifiable morphism:

sage: WordMorphism('a->aa').simplify_alphabet_size()
Traceback (most recent call last):
...
ValueError: self (a->aa) is not simplifiable

Example of an erasing morphism:

sage: f = WordMorphism('a->abc,b->cc,c->')
sage: h, k = f.simplify_alphabet_size(); h, k
(WordMorphism: a->a, b->b, c->, WordMorphism: a->abc, b->cc)
sage: k * h == f
True
sage: g = h * k; g
WordMorphism: a->ab, b->

Example of a morphism, that is not an endomorphism:

sage: f = WordMorphism('a->xx,b->xy,c->yx,d->yy')
sage: h, k = f.simplify_alphabet_size(NN); h, k
(WordMorphism: a->00, b->01, c->10, d->11, WordMorphism: 0->x, 1->y)
sage: k * h == f
True
sage: len(k.domain().alphabet()) < len(f.domain().alphabet())
True
simplify_until_injective()#

Return a quadruplet \((g, h, k, i)\), where \(g\) is an injective simplification of this morphism with respect to \(h\), \(k\) and \(i\).

Requires this morphism to be an endomorphism.

This methods basically calls simplify_alphabet_size() until the returned simplification is injective. If this morphism is already injective, a quadruplet \((g, h, k, i)\) is still returned, where \(g\) is this morphism, \(h\) and \(k\) are the identity morphisms and \(i\) is 0.

Let \(f: X^* \rightarrow Y^*\) be a morphism and \(Y \subseteq X\). Then \(g: Z^* \rightarrow Z^*\) is an injective simplification of \(f\) with respect to morphisms \(h: X^* \rightarrow Z^*\) and \(k: Z^* \rightarrow Y^*\) and a positive integer \(i\), if \(g\) is injective, \(|Z| < |X|\), \(g^i = h \circ k\) and \(f^i = k \circ h\).

For more information see Section 4 in [KO2000].

EXAMPLES:

sage: f = WordMorphism('a->abc,b->a,c->bc')
sage: g, h, k, i = f.simplify_until_injective(); g, h, k, i
(WordMorphism: a->aa, WordMorphism: a->aa, b->a, c->a, WordMorphism: a->abc, 2)
sage: g.is_injective()
True
sage: g**i == h * k
True
sage: f**i == k * h
True
sage.combinat.words.morphism.get_cycles(f, domain)#

Return the list of cycles of the function f contained in domain.

INPUT:

  • f - function.

  • domain - iterable, a subdomain of the domain of definition of f.

EXAMPLES:

sage: from sage.combinat.words.morphism import get_cycles
sage: get_cycles(lambda i: (i+1)%3, [0,1,2])
[(0, 1, 2)]
sage: get_cycles(lambda i: [0,0,0][i], [0,1,2])
[(0,)]
sage: get_cycles(lambda i: [1,1,1][i], [0,1,2])
[(1,)]
sage: get_cycles(lambda i: [2,3,0][i], [0,1,2])
[(0, 2)]
sage: d = {'a': 'a', 'b': 'b'}
sage: get_cycles(d.__getitem__, 'ba')
[('b',), ('a',)]