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 codeu
– 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 morphismu
– word such that u is a prefix of self(u)coding
– boolean (default:False
), whether to include the return word coding morphismlength
– 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