Word morphisms/substitutions¶

This modules implements morphisms over finite and infinite words.

AUTHORS:

Sebastien Labbe (2007-06-01): initial version
Sebastien Labbe (2008-07-01): merged into sage-words
Sebastien Labbe (2008-12-17): merged into sage
Sebastien Labbe (2009-02-03): words next generation
Sebastien Labbe (2009-11-20): allowing the choice of the datatype of the image. Doc improvements.

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
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.WordMorphism(data, codomain=None)¶

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

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

codomain()¶

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']

conjugate(pos)¶

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

domain()¶

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']

extend_by(other)¶

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

fixed_point(letter)¶

Returns 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, 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:

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').fixed_point(letter='a')
word: abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

Infinite fixed point of an erasing morphism:

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

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

has_conjugate_in_classP(f=None)¶

Returns 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()¶

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

has_right_conjugate()¶

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

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({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

images()¶

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]

incidence_matrix()¶

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]

is_empty()¶

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

is_endomorphism()¶

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

is_erasing()¶

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

is_identity()¶

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

is_in_classP(f=None)¶

Returns 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_involution()¶

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

is_primitive()¶

Returns 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

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

REFERENCES:

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

is_prolongable(letter)¶

Returns 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 #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')
...
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

letter_iterator(*args, **kwds)¶

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:

self - an endomorphism, must be prolongable on letter
letter - a letter in the domain of self

OUTPUT:

iterator - iterator of the fixed point

EXAMPLES:

sage: m = WordMorphism('a->abc,b->,c->')
sage: list(m._fixed_point_iterator('a'))
['a', 'b', 'c']

The morphism must be prolongable on the letter:

sage: list(m._fixed_point_iterator('b'))
...
IndexError: pop from empty list

The morphism must be an endomorphism:

sage: m = WordMorphism('a->ac,b->aac')
sage: list(m._fixed_point_iterator('a'))
...
KeyError: 'c'

We check that #8595 is fixed:

sage: s = WordMorphism({('a', 1):[('a', 1), ('a', 2)], ('a', 2):[('a', 1)]})
sage: it = s._fixed_point_iterator(('a',1))
sage: it.next()
('a', 1)

list_fixed_points()¶

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]

list_of_conjugates()¶

Returns 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: 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->']

partition_of_domain_alphabet()¶

Returns 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}, {})

TESTS:

sage: m = WordMorphism('a->b,b->a,c->a')
sage: m.partition_of_domain_alphabet()
...
TypeError: self is not an involution

restrict_domain(alphabet)¶

Returns a restriction of self to the given alphabet.

INPUT:

alphabet - an iterable

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

reversal()¶

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

Word morphisms/substitutions¶

Previous topic

Next topic

This Page

Navigation

Word morphisms/substitutions¶

Previous topic

Next topic

This Page

Quick search

Navigation