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