Word Morphisms¶

Word morphisms methods and iterators

EXAMPLES:

sage: from slabbe.word_morphisms import iter_primitive_marked_classP_morphisms
sage: F = FiniteWords('ab')
sage: it = iter_primitive_marked_classP_morphisms(F, 4)
sage: list(it)
[WordMorphism: a->aba, b->a,
WordMorphism: a->bab, b->a,
WordMorphism: a->b, b->aba,
WordMorphism: a->b, b->bab,
WordMorphism: a->abb, b->a,
WordMorphism: a->ab, b->aa,
WordMorphism: a->bb, b->ba,
WordMorphism: a->b, b->baa]

slabbe.word_morphisms.compute_xsi(self, u)

EXAMPLES:

sage: from slabbe.word_morphisms import compute_xsi
sage: s = WordMorphism({0:[0,1],1:[1,0]})
sage: compute_xsi(s, Word([0]))
sigma_u= 0->012, 1->02, 2->1
theta_u= 0->011, 1->01, 2->0
psi= 0->(0, 0),(0, 1),(0, 2), 1->(1, 0),(1, 1), 2->(2, 0)
psi*sigma_u= 0->(0, 0),(0, 1),(0, 2),(1, 0),(1, 1),(2, 0), 1->(0, 0),(0, 1),(0, 2),(2, 0), 2->(1, 0),(1, 1)
Finite words over {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0)}
[1 0 0]
[1 0 0]
[1 0 0]
[0 1 0]
[0 1 0]
[0 0 1]
We want zeta such that:
zeta((0, 0),(0, 1),(0, 2)) = (0, 0),(0, 1),(0, 2),(1, 0),(1, 1),(2, 0)
zeta((1, 0),(1, 1)) = (0, 0),(0, 1),(0, 2),(2, 0)
zeta((2, 0)) = (1, 0),(1, 1)

slabbe.word_morphisms.desubstitute(self, u)

EXAMPLES:

Unique preimage:

sage: from slabbe.word_morphisms import desubstitute
sage: s = WordMorphism({0:[0,1],1:[1,0]})
sage: desubstitute(s, Word([0,1,0,1,1,0]))
[word: 001]


Non-unique preimage:

sage: s = WordMorphism({0:[0,1],1:[1,0],2:[1,0]})
sage: desubstitute(s, Word([0,1,0,1,1,0]))
[word: 001, word: 002]


No preimage:

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


Lot of preimages (computation is done in parallel with Florent’s Hivert parallel map reduce code):

sage: s = WordMorphism({0:[0,1],1:[0,1]})
sage: w = Word([0,1]) ^ 10
sage: L = desubstitute(s, w)
sage: len(L)
1024

slabbe.word_morphisms.desubstitute_prefix_code(self, u)

Return the preimage of u under self.

INPUT:

• self – word morphism, a prefix code

• u – word

EXAMPLES:

sage: from slabbe.word_morphisms import desubstitute_prefix_code
sage: s = WordMorphism({0:[0,1],1:[1,0]})
sage: w = desubstitute_prefix_code(s, Word([0,1,0,1,1,0]))
sage: w
word: 001


The result lives in the domain of the given substitution:

sage: w.parent()
Finite words over {0, 1}


TESTS:

sage: s = WordMorphism({0:[0,1],1:[1,0],2:[1,0]})
sage: desubstitute_prefix_code(s, Word([0,1,0,1,1,0]))
Traceback (most recent call last):
...
ValueError: non unique desubstitution, m(1)=10, m(2)=10 are prefixes of u[4:]

sage: s = WordMorphism({0:[0,1],1:[1,0]})
sage: desubstitute_prefix_code(s, Word([0,1,0,1,1,1]))
Traceback (most recent call last):
...
ValueError: desubstitution is impossible for u[4:]

slabbe.word_morphisms.is_left_marked(m)

EXAMPLES:

sage: from slabbe.word_morphisms import is_left_marked
sage: m = WordMorphism('0->00001,1->00010')
sage: is_left_marked(m)
True
sage: m = WordMorphism('0->00001,1->00001')
sage: is_left_marked(m)
False
sage: m = WordMorphism('0->00001,1->00001,2->201')
sage: is_left_marked(m)
False
sage: m = WordMorphism('0->00001,1->10001,2->201')
sage: is_left_marked(m)
True
sage: m = WordMorphism('0->000001,1->010001,2->0201')
sage: is_left_marked(m)
True
sage: m = WordMorphism('0->000001,1->010001,2->0101')
sage: is_left_marked(m)
False

slabbe.word_morphisms.is_marked(m)

EXAMPLES:

sage: from slabbe.word_morphisms import is_marked
sage: m = WordMorphism('0->00001,1->00010')
sage: is_marked(m)
True

slabbe.word_morphisms.iter_conjugate_classP(words, n)

EXAMPLES:

sage: from slabbe.word_morphisms import iter_conjugate_classP
sage: F = FiniteWords('ab')
sage: list(iter_conjugate_classP(F, 2))
[WordMorphism: a->a, b->a,
WordMorphism: a->a, b->b,
WordMorphism: a->b, b->a,
WordMorphism: a->b, b->b]
sage: list(iter_conjugate_classP(F, 3))
[WordMorphism: a->aa, b->a,
WordMorphism: a->aa, b->b,
WordMorphism: a->bb, b->a,
WordMorphism: a->bb, b->b,
WordMorphism: a->a, b->aa,
WordMorphism: a->a, b->bb,
WordMorphism: a->b, b->aa,
WordMorphism: a->b, b->bb,
WordMorphism: a->ba, b->b,
WordMorphism: a->ab, b->a,
WordMorphism: a->b, b->ba,
WordMorphism: a->a, b->ab]

slabbe.word_morphisms.iter_palindromes(words, length)

EXAMPLES:

sage: from slabbe.word_morphisms import iter_palindromes
sage: list(iter_palindromes(Words('ab'), 2))
[word: aa, word: bb]
sage: list(iter_palindromes(Words('ab'), 3))
[word: aaa, word: aba, word: bab, word: bbb]
sage: list(iter_palindromes(Words('ab'), 4))
[word: aaaa, word: abba, word: baab, word: bbbb]
sage: list(iter_palindromes(Words('ab'), 5))
[word: aaaaa,
word: aabaa,
word: ababa,
word: abbba,
word: baaab,
word: babab,
word: bbabb,
word: bbbbb]

slabbe.word_morphisms.iter_pisot_irreductible(d=3, arg=None)

Return an iterator over Pisot irreductible substitutions

INPUT:

• d – size of alphabet, [0,1,…,d-1]

• “arg” – (optional, default: None) It can be one of the following :

• “None” – then the method iterates through all morphisms.

• tuple (a, b) of two integers - It specifies the range “range(a, b)” of values to consider for the sum of the length

EXAMPLES:

sage: from slabbe.word_morphisms import iter_pisot_irreductible
sage: it = iter_pisot_irreductible(3)
sage: for _ in range(4): next(it)
WordMorphism: 0->01, 1->2, 2->0
WordMorphism: 0->02, 1->0, 2->1
WordMorphism: 0->10, 1->2, 2->0
WordMorphism: 0->12, 1->0, 2->1


Pour linstant, avec le tuple, il y a un bogue:

sage: it = iter_pisot_irreductible(3, (5,10))
sage: for _ in range(4): next(it)
WordMorphism: 0->0000001, 1->2, 2->0
WordMorphism: 0->0000002, 1->0, 2->1
WordMorphism: 0->0000010, 1->2, 2->0
WordMorphism: 0->0000012, 1->0, 2->1

slabbe.word_morphisms.iter_primitive_marked_classP_morphisms(words, n)

EXAMPLES:

sage: from slabbe.word_morphisms import iter_primitive_marked_classP_morphisms
sage: F = FiniteWords('ab')
sage: it = iter_primitive_marked_classP_morphisms(F, 2)
sage: list(it)
[]
sage: it = iter_primitive_marked_classP_morphisms(F, 3)
sage: list(it)
[WordMorphism: a->ab, b->a, WordMorphism: a->b, b->ba]
sage: it = iter_primitive_marked_classP_morphisms(F, 4)
sage: list(it)
[WordMorphism: a->aba, b->a,
WordMorphism: a->bab, b->a,
WordMorphism: a->b, b->aba,
WordMorphism: a->b, b->bab,
WordMorphism: a->abb, b->a,
WordMorphism: a->ab, b->aa,
WordMorphism: a->bb, b->ba,
WordMorphism: a->b, b->baa]

slabbe.word_morphisms.return_substitution(self, u, coding=False, length=1000)

Return the return substitution of self according to factor u.

INPUT:

• self – word morphism

• u – word such that u is a prefix of self(u)

• coding – boolean (default: False), whether to include the return word coding morphism

• length – integer (default: 1000), compute the first 1000 letters of the derived sequence to make sure every return word are seen

EXAMPLES:

sage: from slabbe.word_morphisms import return_substitution
sage: s = WordMorphism({0:[0,1],1:[1,0]})
sage: return_substitution(s, Word([0]))
WordMorphism: 0->012, 1->02, 2->1
sage: return_substitution(s, Word([0,1]))
WordMorphism: 0->01, 1->23, 2->013, 3->2
sage: return_substitution(s, Word([0,1,1]))
WordMorphism: 0->01, 1->23, 2->013, 3->2

sage: return_substitution(s, Word([0]), True)
(WordMorphism: 0->012, 1->02, 2->1,
WordMorphism: 0->011, 1->01, 2->0)
sage: return_substitution(s, Word([0,1]), True)
(WordMorphism: 0->01, 1->23, 2->013, 3->2,
WordMorphism: 0->011, 1->010, 2->0110, 3->01)

sage: s = WordMorphism({0:[0,0,1],1:[0,1]})
sage: return_substitution(s, Word([0]))
WordMorphism: 0->01, 1->011


TESTS:

sage: s = WordMorphism({0:[0,1],1:[1,0]})
sage: sigma_u, theta_u = return_substitution(s, Word([0]), coding=True)
sage: sigma_u
WordMorphism: 0->012, 1->02, 2->1
sage: theta_u
WordMorphism: 0->011, 1->01, 2->0
sage: theta_u*sigma_u == s*theta_u
True
sage: theta_u*sigma_u
WordMorphism: 0->011010, 1->0110, 2->01