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
Morphism from Words over Ordered Alphabet [0, 1, 2] to Words over Ordered Alphabet [0, 1, 2]
sage: m
Morphism from Words over Ordered Alphabet ['s', 'x', 'y'] to Words over Ordered Alphabet ['s', 'x', 'y']
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]))
Morphism from Words over Ordered Alphabet [0, 1, 2] to Words over Ordered Alphabet [0, 1, 2, 3, 4]
Power of a morphism:
sage: print 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
Fixed point beginning with 'x' of the morphism WordMorphism: s->xyss, x->xyxsxss, y->ys
sage: fix.length()
+Infinity
sage: fix[100:]
word: ysxyxsxssxyssxyxsxssxyssxyssxyxsxssysxys...
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 image of w under self to the given order.
INPUT:
OUTPUT:
EXAMPLES:
The image of a word under a morphism:
The image of a finite word under a morphism:
sage: tm = WordMorphism ('a->ab,b->ba')
sage: tm('a')
word: ab
sage: tm('aabababb')
word: ababbaabbaabbaba
The iterated image of a word:
sage: tm('a', 2)
word: abba
sage: tm('aba', 3)
word: abbabaabbaababbaabbabaab
The infinitely iterated image of a letter:
sage: tm('a', oo)
Fixed point beginning with 'a' of the morphism WordMorphism: a->ab, b->ba
The image of an infinite word:
sage: t = words.ThueMorseWord()
sage: n = WordMorphism({0:[0, 1], 1:[1, 0]})
sage: n(t)
word: 0110100110010110100101100110100110010110...
sage: n(t, 3)
word: 0110100110010110100101100110100110010110...
sage: n(t)[:1000] == t[:1000]
True
sage: w = words.FibonacciWord()
sage: m = WordMorphism({0:'a', 1:'b'})
sage: m(w)
word: abaababaabaababaababaabaababaabaababaaba...
sage: f = words.FibonacciWord('ab')
sage: f[:1000] == m(w)[:1000]
True
sage: w = words.FibonacciWord("ab")
sage: m = WordMorphism('a->01,b->101')
sage: m(w)
word: 0110101011010110101011010101101011010101...
The word must be in the domain of self:
sage: tm('0021')
...
ValueError: 0 not in alphabet!
The order must be a positive integer or plus Infinity:
sage: tm('a', -1)
...
TypeError: order (-1) must be a positive integer or plus Infinity
sage: tm('a', 6.7)
...
TypeError: order (6.70000000000000) must be a positive integer or plus Infinity
Infinitely iterated image of a word is defined only for those of length one:
sage: tm('aba',oo)
...
TypeError: For infinite powers, the length of the word must be 1 (not 3)
self must be prolongable on the given letter for infinitely iterated image:
sage: m = WordMorphism('a->ba,b->ab')
sage: m('a', oo)
...
TypeError: self must be prolongable on a
TESTS:
sage: for i in range(6):
... tm('a', i)
...
word: a
word: ab
word: abba
word: abbabaab
word: abbabaabbaababba
word: abbabaabbaababbabaababbaabbabaab
sage: m = WordMorphism('a->,b->')
sage: m('')
word:
Returns True if self is equal to other.
EXAMPLES:
sage: n = WordMorphism('a->a,b->aa,c->aaa')
sage: n**3 == n**1
True
sage: WordMorphism('b->ba,a->ab') == WordMorphism('a->ab,b->ba')
True
sage: WordMorphism('b->ba,a->ab') == WordMorphism({"a":"ab","b":"ba"})
True
sage: m = WordMorphism({0:[1,2,3],1:[4,5,6]}); print m
WordMorphism: 0->123, 1->456
sage: o = WordMorphism('0->123,1->456'); print o
WordMorphism: 0->123, 1->456
sage: m == o
False
Construction of the morphism.
EXAMPLES:
If data is a str:
sage: print WordMorphism('a->ab,b->ba')
WordMorphism: a->ab, b->ba
sage: print WordMorphism('a->ab,b->ba')
WordMorphism: a->ab, b->ba
sage: print WordMorphism('a->abc,b->bca,c->cab')
WordMorphism: a->abc, b->bca, c->cab
sage: print WordMorphism('a->abdsf,b->hahdad,c->asdhasd')
WordMorphism: a->abdsf, b->hahdad, c->asdhasd
sage: print WordMorphism('(->(),)->)(')
WordMorphism: (->(), )->)(
sage: print WordMorphism('a->53k,b->y5?,$->49i')
WordMorphism: $->49i, a->53k, b->y5?
An erasing morphism:
sage: print WordMorphism('a->ab,b->')
WordMorphism: a->ab, b->
Use the arrows (‘->’) correctly:
sage: WordMorphism('a->ab,b-')
...
ValueError: The second and third characters must be '->' (not '-')
sage: WordMorphism('a->ab,b')
...
ValueError: The second and third characters must be '->' (not '')
sage: WordMorphism('a->ab,a-]asdfa')
...
ValueError: The second and third characters must be '->' (not '-]')
Each letter must be defined only once:
sage: WordMorphism('a->ab,a->ba')
...
ValueError: The image of 'a' is defined twice.
From a dictionary:
sage: print WordMorphism({"a":"ab","b":"ba"})
WordMorphism: a->ab, b->ba
sage: print WordMorphism({2:[4,5,6],3:[1,2,3]})
WordMorphism: 2->456, 3->123
sage: print WordMorphism({'a':['a',6,'a'],6:[6,6,6,'a']})
WordMorphism: 6->666a, a->a6a
The image of a letter can be a set, but the order is not preserved:
sage: print WordMorphism({2:[4,5,6],3:set([4,1,8])}) #random results
WordMorphism: 2->456, 3->814
If the image of a letter is not iterable, it is considered as a letter:
sage: print WordMorphism({0:1, 1:0})
WordMorphism: 0->1, 1->0
sage: print WordMorphism({0:123, 1:789})
WordMorphism: 0->123, 1->789
sage: print WordMorphism({2:[4,5,6], 3:123})
WordMorphism: 2->456, 3->123
From a WordMorphism:
sage: print WordMorphism(WordMorphism('a->ab,b->ba'))
WordMorphism: a->ab, b->ba
TESTS:
sage: print WordMorphism(',,,a->ab,,,b->ba,,')
WordMorphism: a->ab, b->ba
Returns the morphism self*``other``.
EXAMPLES:
sage: m = WordMorphism('a->ab,b->ba')
sage: fibo = WordMorphism('a->ab,b->a')
sage: print fibo*m
WordMorphism: a->aba, b->aab
sage: print fibo*fibo
WordMorphism: a->aba, b->ab
sage: print m*fibo
WordMorphism: a->abba, b->ab
sage: n = WordMorphism('a->a,b->aa,c->aaa')
sage: p1 = n*m
sage: print p1
WordMorphism: a->aaa, b->aaa
sage: p1.domain()
Words over Ordered Alphabet ['a', 'b']
sage: p1.codomain()
Words over Ordered Alphabet ['a']
sage: p2 = m*n
sage: print p2
WordMorphism: a->ab, b->abab, c->ababab
sage: p2.domain()
Words over Ordered Alphabet ['a', 'b', 'c']
sage: p2.codomain()
Words over Ordered Alphabet ['a', 'b']
TESTS:
sage: m = WordMorphism('a->b,b->c,c->a')
sage: WordMorphism('')*m
...
ValueError: b not in alphabet!
sage: print m * WordMorphism('')
WordMorphism:
Returns the power of self with exponent = exp.
INPUT:
EXAMPLES:
sage: m = WordMorphism('a->ab,b->ba')
sage: print m^1
WordMorphism: a->ab, b->ba
sage: print m^2
WordMorphism: a->abba, b->baab
sage: print m^3
WordMorphism: a->abbabaab, b->baababba
The exponent must be a positive integer:
sage: m^1.5
...
ValueError: exponent (1.50000000000000) must be an integer
sage: print m^-2
...
ValueError: exponent (-2) must be strictly positive
When self is not an endomorphism:
sage: n = WordMorphism('a->ba,b->abc')
sage: n^2
...
ValueError: c not in alphabet!
Returns the morphism in str (for display).
EXAMPLES:
sage: WordMorphism('a->ab,b->ba')
Morphism from Words over Ordered Alphabet ['a', 'b'] to Words over Ordered Alphabet ['a', 'b']
sage: d = {0:[0,1],1:[1,0]}
sage: WordMorphism(d)
Morphism from Words over Ordered Alphabet [0, 1] to Words over Ordered Alphabet [0, 1]
Returns the morphism in str (for display).
EXAMPLES:
sage: print WordMorphism('a->ab,b->ba')
WordMorphism: a->ab, b->ba
sage: print WordMorphism('b->ba,a->ab')
WordMorphism: a->ab, b->ba
sage: d = {0:[0,1],1:[1,0]}
sage: print WordMorphism(d)
WordMorphism: 0->01, 1->10
Returns a Words domain containing all the letter in the keys of data (which must be a dictionary).
TESTS:
If the image of all the letters are iterable:
sage: wm = WordMorphism('a->ab,b->ba')
sage: wm._build_codomain({'a': 'ab', 'b': 'ba'})
Words over Ordered Alphabet ['a', 'b']
sage: wm._build_codomain({'a': 'dcb', 'b': 'a'})
Words over Ordered Alphabet ['a', 'b', 'c', 'd']
sage: wm._build_codomain({2:[4,5,6],3:[1,2,3]})
Words over Ordered Alphabet [1, 2, 3, 4, 5, 6]
sage: wm._build_codomain({2:[4,5,6],3:set([4,1,8])})
Words over Ordered Alphabet [1, 4, 5, 6, 8]
If the image of a letter is not iterable, it is considered as a letter:
sage: wm._build_codomain({2:[4,5,6],3:123})
Words over Ordered Alphabet [4, 5, 6, 123]
sage: wm._build_codomain({0:1, 1:0, 2:2})
Words over Ordered Alphabet [0, 1, 2]
Parse the string input to WordMorphism and build the dictionary it represents.
TESTS:
sage: wm = WordMorphism('a->ab,b->ba')
sage: wm._build_dict('a->ab,b->ba') == {'a': 'ab', 'b': 'ba'}
True
sage: wm._build_dict('a->ab,a->ba')
...
ValueError: The image of 'a' is defined twice.
sage: wm._build_dict('a->ab,b>ba')
...
ValueError: The second and third characters must be '->' (not '>b')
Returns True if all the letters of the domain appear in all the images of letters of the domain.
INPUT:
EXAMPLES:
sage: m = WordMorphism('a->ab,b->ba')
sage: m._check_primitive()
True
sage: fibo = WordMorphism('a->ab,b->a')
sage: fibo._check_primitive()
False
sage: print WordMorphism({2:[4,5,6],3:[4,1,8]})
WordMorphism: 2->456, 3->418
sage: WordMorphism({2:[4,5,6],3:[4,1,8]})._check_primitive()
False
Returns the incidence matrix of the morphism over the specified ring.
EXAMPLES:
sage: fibo = WordMorphism('a->ab,b->a')
sage: tm = WordMorphism('a->ab,b->ba')
sage: Mfibo = matrix(fibo); Mfibo
[1 1]
[1 0]
sage: Mtm = matrix(tm); Mtm
[1 1]
[1 1]
sage: Mtm * Mfibo == matrix(tm*fibo)
True
sage: Mfibo * Mtm == matrix(fibo*tm)
True
sage: Mfibo.parent()
Full MatrixSpace of 2 by 2 dense matrices over Integer Ring
sage: p = Mfibo.charpoly(); p
x^2 - x - 1
sage: p.roots(ring=RR, multiplicities=False)
[-0.618033988749895, 1.61803398874989]
Returns the codomain of self.
EXAMPLES:
sage: WordMorphism('a->ab,b->a').codomain()
Words over Ordered Alphabet ['a', 'b']
sage: WordMorphism('6->ab,y->5,0->asd').codomain()
Words over Ordered Alphabet ['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: print m.conjugate(1)
WordMorphism: a->bcdea
sage: print m.conjugate(3)
WordMorphism: a->deabc
sage: print WordMorphism('').conjugate(4)
WordMorphism:
sage: m = WordMorphism('a->abcde,b->xyz')
sage: print m.conjugate(2)
WordMorphism: a->cdeab, b->zxy
Returns domain of self.
EXAMPLES:
sage: WordMorphism('a->ab,b->a').domain()
Words over Ordered Alphabet ['a', 'b']
sage: WordMorphism('b->ba,a->ab').domain()
Words over Ordered Alphabet ['a', 'b']
sage: WordMorphism('6->ab,y->5,0->asd').domain()
Words over Ordered Alphabet ['0', '6', 'y']
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: print m.extend_by(n)
WordMorphism: 0->1, 1->0, a->ab, b->ba
sage: print n.extend_by(m)
WordMorphism: 0->1, 1->0, a->5, b->ba
sage: print 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)
...
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')
Fixed point beginning with 'a' of the morphism WordMorphism: a->ab, b->ba
sage: WordMorphism('a->ab,b->a').fixed_point(letter='a')
Fixed point beginning with 'a' of the morphism WordMorphism: a->ab, b->a
sage: WordMorphism('a->ab,b->b,c->ba').fixed_point(letter='a')
Fixed point beginning with 'a' of the morphism WordMorphism: a->ab, b->b, c->ba
Infinite fixed point of an erasing morphism:
sage: WordMorphism('a->ab,b->,c->ba').fixed_point(letter='a')
Fixed point beginning with 'a' of the morphism WordMorphism: a->ab, b->, c->ba
Finite fixed point:
sage: WordMorphism('a->ab,b->b,c->ba').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
Fixed point beginning with 'a' of the morphism WordMorphism: a->abc, b->, c->
sage: fp[:10]
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')
Fixed point beginning with 'a' of the morphism WordMorphism: a->abba, b->baab
TESTS:
sage: WordMorphism('a->ab,b->,c->ba').fixed_point(letter='b')
...
TypeError: self must be prolongable on b
sage: WordMorphism('a->ab,b->,c->ba').fixed_point(letter='c')
...
TypeError: self must be prolongable on c
sage: WordMorphism('a->ab,b->,c->ba').fixed_point(letter='d')
...
TypeError: letter (=d) is not in the domain alphabet (=Ordered Alphabet ['a', 'b', 'c'])
sage: WordMorphism('a->aa,b->aac').fixed_point(letter='a')
...
TypeError: self (=WordMorphism: a->aa, b->aac) is not a endomorphism
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
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()
True
sage: Wabc = Words('abc')
sage: m = WordMorphism('a->a,b->aa,c->aaa',codomain = Wabc)
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
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
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->bb').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()
...
TypeError: self (=WordMorphism: 0->1, 1->0, 2->3) is not a 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:
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
TESTS:
sage: m = WordMorphism('a->bb,b->aac')
sage: m.is_primitive()
...
TypeError: self (=WordMorphism: a->bb, b->aac) is not a endomorphism
sage: m = WordMorphism('a->,b->',codomain=Words('ab'))
sage: m.is_primitive()
False
sage: m = WordMorphism('a->,b->')
sage: m.is_primitive()
False
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
TESTS:
sage: WordMorphism('a->ab,b->b,c->ba').is_prolongable(letter='d')
...
TypeError: letter (=d) is not in the domain alphabet (=Ordered 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
...
TypeError: codomain of self must be an instance of Words
Returns an iterator of the letters of the fixed point of self starting with letter.
If w is the iterated word, then this iterator: outputs the elements of morphism[ w[i] ], appends morphism[ w[i+1] ] to w, increments i.
INPUT:
OUTPUT:
EXAMPLES:
sage: m = WordMorphism('a->abc,b->,c->')
sage: list(m.letter_iterator('b'))
...
TypeError: self must be prolongable on b
sage: list(m.letter_iterator('a'))
['a', 'b', 'c']
sage: m = WordMorphism('a->aa,b->aac')
sage: list(m.letter_iterator('a'))
...
TypeError: self (=WordMorphism: a->aa, b->aac) is not a endomorphism
Returns the list of all fixed points of self.
EXAMPLES:
sage: WordMorphism('a->ab,b->ba').list_fixed_points() #not implemented
[Fixed point beginning with 'a' of the morphism WordMorphism: a->ab, b->ba,
Fixed point beginning with 'b' of the morphism WordMorphism: a->ab, b->ba]
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: map(str, 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: map(str, m.list_of_conjugates())
['WordMorphism: a->aaa, b->aa']
sage: WordMorphism('').list_of_conjugates()
[Morphism from Words over Ordered Alphabet [] to Words over Ordered Alphabet []]
sage: m = WordMorphism('a->aba,b->aba')
sage: map(str, 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: map(str, 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()
...
TypeError: self is not an involution
Returns a restriction of self to the given alphabet.
INPUT:
OUTPUT:
WordMorphism
EXAMPLES:
sage: m = WordMorphism('a->b,b->a')
sage: print m.restrict_domain('a')
WordMorphism: a->b
sage: print m.restrict_domain('')
WordMorphism:
sage: print m.restrict_domain('A')
WordMorphism:
sage: print m.restrict_domain('Aa')
WordMorphism: a->b
The input alphabet must be iterable:
sage: print m.restrict_domain(66)
...
TypeError: 'sage.rings.integer.Integer' object is not iterable
Returns the reversal of self.
EXAMPLES:
sage: print WordMorphism('6->ab,y->5,0->asd').reversal()
WordMorphism: 0->dsa, 6->ba, y->5
sage: print WordMorphism('a->ab,b->a').reversal()
WordMorphism: a->ba, b->a