Factor complexity and Bispecial Extension Type¶
Factor complexity, Bispecial factors and Extension types
This module was developped for the article on the factor complexity of infinite sequences genereated by substitutions written with Valérie Berthé [BL2014].
[BL2014] | V. Berthé, S. Labbé, Factor Complexity of S-adic sequences generated by the Arnoux-Rauzy-Poincaré Algorithm. arXiv:1404.4189 (April, 2014). |
EXAMPLES:
The extension type of an ordinary bispecial factor:
sage: from slabbe import ExtensionType1to1
sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)]
sage: E = ExtensionType1to1(L, alphabet=(1,2,3))
sage: E
E(w) 1 2 3
1 X
2 X
3 X X X
m(w)=0, ord.
sage: E.is_ordinaire()
True
Creation of a strong-weak pair of bispecial words from a neutral not ordinairy word:
sage: m = WordMorphism({1:[1,2,3],2:[2,3],3:[3]})
sage: E = ExtensionType1to1([(1,2),(2,3),(3,1),(3,2),(3,3)], [1,2,3])
sage: E
E(w) 1 2 3
1 X
2 X
3 X X X
m(w)=0, neutral
sage: E1, E2 = E.apply(m)
sage: E1
E(w) 1 2 3
1
2 X X
3 X X X
m(w)=1, strong
sage: E2
E(w) 1 2 3
1 X
2
3 X
m(w)=-1, weak
TODO:
- use __classcall_private__ stuff for ExtensionType ?
- fix bug of apply for ExtensionTypeLong when the word appears in the image of a letter (first initial fix: 18 May 2016, to be confirmed)
- use this to compute the factor complexity function
- When should two bispecial extension type be equal? In graphs, we sometimes prefer when they are all different…
-
class
slabbe.bispecial_extension_type.
ExtensionType
¶ Bases:
object
-
bispecial_factors_table_under_sadic
(substitutions, substitutions_dict, keep_empty=True)¶ Return the summary table of bispecial factors obtain from this extension type after the application of substitutions.
INPUT:
substitutions
– the sequence of substitutionssubstitutions_dict
- dict of substitutionskeep_empty
– (default: True) whether to keep images that are empty, thus it will include all bispecial factors of age <= k on the highest graded component.
EXAMPLES:
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: E1.bispecial_factors_table_under_sadic([132]*2+[123]*6, S) |w| w m(w) d^-(w) d2^-(w) info +-----+----------------------+------+--------+---------+---------+ 0 0 3 5 ord. 1 2 0 3 4 neutral 2 22 0 2 2 ord. 4 2322 0 2 3 ord. 5 22322 0 2 2 ord. 7 2322322 0 2 3 ord. 8 22322322 0 2 2 ord. 10 2322322322 0 2 3 ord. 11 22322322322 0 2 2 ord. 13 2322322322322 0 2 3 ord. 14 22322322322322 0 2 2 ord. 16 2322322322322322 0 2 3 ord. 17 22322322322322322 0 2 2 ord. 19 2322322322322322322 1 2 3 strong 20 22322322322322322322 -1 2 2 weak
-
cardinality
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.cardinality() 5
-
distinct_bispecial_factors_under_sadic
(substitutions, substitutions_dict, keep_empty=True)¶ Return the list of distinct bispecial factors obtain from this extension type after the application of substitutions.
This method essentially removes duplicates with distinct extension types but subset of others.
INPUT:
substitutions
– the sequence of substitutionssubstitutions_dict
- dict of substitutionskeep_empty
– (default: True) whether to keep images that are empty, thus it will include all bispecial factors of age <= k on the highest graded component.
EXAMPLES:
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: L = E1.distinct_bispecial_factors_under_sadic([132]*2+[123]*6, S) sage: sorted(Z.factor() for Z in L) [word: , word: 2, word: 22, word: 22322, word: 22322322, word: 22322322322, word: 22322322322322, word: 22322322322322322, word: 22322322322322322322, word: 2322, word: 2322322, word: 2322322322, word: 2322322322322, word: 2322322322322322, word: 2322322322322322322] sage: sorted(Z.multiplicity() for Z in L) [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
-
equivalence_class
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: len(E.equivalence_class()) 6
-
factor
()¶ Return the bispecial factor.
EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: p = WordMorphism({1:[1,2,3],2:[2,3],3:[3]}) sage: E = ExtensionType1to1([(1,2),(2,3),(3,1),(3,2),(3,3)], [1,2,3]) sage: A,B = E.apply(p) sage: A.factor() word: 3 sage: B.factor() word: 23
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: b12 = WordMorphism({1:[1,2],2:[2],3:[3]}) sage: A,B = E.apply(b12) sage: A.factor() word: sage: B.factor() word: 2
sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: data = [((3, 1), (2,)), ((1, 2), (3,)), ((3, 2), (3,)), ((2, ....: 3), (1,)), ((2, 3), (2,)), ((2, 3), (3,)), ((3, 3), (1,))] sage: e = ExtensionTypeLong(data, [1,2,3]) sage: e = e.apply(S[132])[1] sage: e.factor() word: 2 sage: e = e.apply(S[321])[0] sage: e.factor() word: 21 sage: e = e.apply(S[312])[0] sage: e.factor() word: 212
-
static
from_factor
(bispecial, word, nleft=1, nright=1, repr_options=None)¶ INPUT:
bispecial
– the bispecial factorword
– the word describing the languagenleft
– length of left extensions (default:1
)nright
– length of right extensions (default:1
)repr_options
- dict (default:None
) representation options whether to include the factor and or the valence in the string or latex representation. The valueNone
is replaced bydict(factor=False,multiplicity=True,valence=False))
.
EXAMPLES:
sage: from slabbe import ExtensionType sage: W = Words([0,1,2]) sage: ExtensionType.from_factor(W(), W([0,1,1,2,0])) E(w) 0 1 2 0 X 1 X X 2 X m(w)=-1, weak
sage: ExtensionType.from_factor(W(), W([0,1,1,2,0]), nleft=2) E(w) 0 1 2 01 X 11 X 12 X m(w)=-1, weak
sage: ExtensionType.from_factor(W(), W([0,1,1,2,0]), nright=2) E(w) 11 12 20 0 X 1 X X m(w)=0, ord.
sage: prefix = words.FibonacciWord()[:1000] sage: ExtensionType.from_factor(W(), prefix, nright=2, nleft=2) E(w) 00 01 10 00 X 10 X X 01 X X m(w)=0, ord.
-
static
from_morphism
(m, repr_options=None)¶ Return the extension type of the empty word in the language defined by the image of the free monoid under the morphism m.
INPUT:
m
- endomorphimrepr_options
- dict (default:None
) representation options whether to include the factor and or the valence in the string or latex representation. The valueNone
is replaced bydict(factor=False,multiplicity=True,valence=False))
.
EXAMPLES:
sage: from slabbe import ExtensionType sage: ar = WordMorphism({1:[1,3],2:[2,3],3:[3]}) sage: ExtensionType.from_morphism(ar) E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, ord.
sage: p = WordMorphism({1:[1,2,3],2:[2,3],3:[3]}) sage: ExtensionType.from_morphism(p) E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, neutral
sage: b12 = WordMorphism({1:[1,2],2:[2],3:[3]}) sage: ExtensionType.from_morphism(b12) E(w) 1 2 3 1 X 2 X X X 3 X X X m(w)=2, strong
-
graph_under_language
(language, initial, substitutions_dict, keep_empty=False, max_depth=inf, growth_limit=inf)¶ Return the recursively enumerated set of extension type generated by a language of substitutions.
INPUT:
language
– the language of substitutionsinitial
– initial substitutionsubstitutions_dict
- dict of substitutionskeep_empty
– bool (default: False) whether to keep images that are emptymax_depth
– integer (default:float('inf')
), max depthgrowth_limit
– integer (default:float('inf')
), the maximal growth in length of the bispecial extended images
EXAMPLES:
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: from slabbe.language import languages sage: L = languages.Brun() sage: E = [E for E in E1.apply(S[123]) if E.factor().length() == 1][0] sage: E.graph_under_language(L, 123, S, max_depth=2) # long time (3s) Looped multi-digraph on 41 vertices
-
graph_under_language_joined
(language, initial, substitutions_dict, keep_empty=False, max_depth=inf, growth_limit=inf)¶ Return the recursively enumerated set of extension type generated by a language of substitutions where the extension type of the same age and joined.
INPUT:
language
– the language of substitutionsinitial
– initial substitutionsubstitutions_dict
- dict of substitutionskeep_empty
– bool (default: False) whether to keep images that are emptymax_depth
– integer (default:float('inf')
), max depthgrowth_limit
– integer (default:float('inf')
), the maximal growth in length of the bispecial extended images
EXAMPLES:
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: from slabbe.language import languages sage: L = languages.Brun() sage: E = [E for E in E1.apply(S[123]) if E.factor().length() == 1][0] sage: E.graph_under_language_joined(L, 123, S, max_depth=2) Looped multi-digraph on 26 vertices sage: E.graph_under_language_joined(L, 123, S, max_depth=2, growth_limit=1) Looped multi-digraph on 21 vertices sage: E.graph_under_language_joined(L, 123, S) # not tested long time Looped multi-digraph on 715 vertices
-
graph_under_sadic
(substitutions, substitutions_dict, keep_equal_length=False, raw=False, growth_limit=inf)¶ Return the graph of extension types under the application of an s-adic word.
INPUT:
substitutions
– the sequence of substitutionssubstitutions_dict
- dict of substitutionskeep_equal_length
– (default: False) whether to keep images that have equal length, thus it will include all bispecial factors of age <= k on the highest graded component.raw
– bool (default: False), whether to keep the vertices raw, i.e. including history and factors informationgrowth_limit
– integer (default:float('inf')
), the maximal growth in length of the bispecial extended images
EXAMPLES:
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: E1.graph_under_sadic([132]*2+[123]*6, S) Looped multi-digraph on 9 vertices sage: E1.graph_under_sadic([132]*2+[123]*6, S, keep_equal_length=True) Looped multi-digraph on 19 vertices sage: E1.graph_under_sadic([132]*2+[123]*6, S, raw=True) Looped multi-digraph on 18 vertices sage: E1.graph_under_sadic([132]*2+[123]*6, S, raw=True, keep_equal_length=True) Looped multi-digraph on 59 vertices
sage: G = E1.graph_under_sadic([132]*2+[123]*6, S) sage: from slabbe.tikz_picture import TikzPicture sage: _ = TikzPicture.from_graph(G).pdf(view=False) # long time (9s)
-
graph_under_sadic_joined
(substitutions, substitutions_dict, keep_equal_length=False, keep_unique=False, growth_limit=inf, filter_fn=None, raw=False)¶ Return the graph of extension types under the application of an s-adic word where the extension type of the same age are joined.
INPUT:
substitutions
– the sequence of substitutionssubstitutions_dict
- dict of substitutionskeep_equal_length
– (default: False) whether to keep images that have equal lengthkeep_unique
– (default: False) whether to keep a unique copy of equal extension typesgrowth_limit
– integer (default:float('inf')
), the maximal growth in length of the bispecial extended imagesfilter_fn
– function (default:None
)raw
– bool (default: False), whether to keep the vertices raw, i.e. including history and factors information
EXAMPLES:
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: E1._repr_options=dict(factor=False) sage: seq = [231,213,213,213,321]+[213,231,231,231,123]+[132,123] sage: E1.graph_under_sadic_joined(seq, S, growth_limit=1) Looped multi-digraph on 10 vertices
-
image
(m)¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: b23 = WordMorphism({1:[1],2:[2,3],3:[3]}) sage: E.image(b23) E(w) 1 2 3 31 X 12 X 32 X 23 X X X 33 X m(w)=0, neutral
-
information
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.information() 'ord.'
-
is_bispecial
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.is_bispecial() True
-
is_empty
()¶ Return whether the word associated to this extension type is empty.
EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E.is_empty() False
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.is_empty() True
sage: E = ExtensionTypeLong(L, (1,2,3), empty=False) sage: E.is_empty() False
-
is_equivalent
(other)¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.is_equivalent(E) True
-
is_neutral
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.is_neutral() True
-
is_ordinaire
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E.is_ordinaire() True
-
is_subset
(other)¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: F = ExtensionTypeLong(L, (1,2,3)) sage: E.is_subset(F) True sage: F.is_subset(E) False
-
left_extensions
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E.left_extensions() {1, 2, 3}
-
left_right_projection
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,2), (2,2), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: left, right = E.left_right_projection() sage: dict(left) {1: 1, 2: 1, 3: 3} sage: dict(right) {1: 1, 2: 3, 3: 1}
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: left, right = E.left_right_projection() sage: sorted(left.items()) [(word: 12, 3), (word: 21, 1), (word: 22, 1), (word: 23, 1), (word: 31, 1)] sage: sorted(right.items()) [(word: 1, 3), (word: 2, 3), (word: 3, 1)]
-
multiplicity
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.multiplicity() 0
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.multiplicity() 0
-
palindromic_valence
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.palindromic_valence() 1
-
rec_enum_set_under_language
(language, initial, substitutions_dict, keep_empty=False, label='history', growth_limit=inf)¶ Return the recursively enumerated set of extension type generated by a language of substitutions.
INPUT:
language
– the language of substitutionsinitial
– initial substitutionsubstitutions_dict
- dict of substitutionskeep_empty
– (default: False) whether to keep images that are emptylabel
– ‘history’ or ‘previous’ (default:'history'
), whether the vertices contain the whole history of the bispecial word or only the previous applied substitutiongrowth_limit
– integer (default:float('inf')
), the maximal growth in length of the bispecial extended images
EXAMPLES:
sage: from slabbe.mult_cont_frac import Brun sage: from slabbe.bispecial_extension_type import ExtensionType sage: from slabbe.language import languages sage: algo = Brun() sage: S = algo.substitutions() sage: L = languages.Brun() sage: v = algo.image((1,e,pi), 5) sage: prefix = algo.s_adic_word(v)[:100000] sage: E = ExtensionType.from_factor(prefix.parent()(), prefix, nleft=2) sage: E.rec_enum_set_under_language(L, 123, S) An enumerated set with a forest structure
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: from slabbe.language import languages sage: L = languages.Brun() sage: E = [E for E in E1.apply(S[123]) if E.factor().length() == 1][0] sage: R = E.rec_enum_set_under_language(L, 123, S, label='previous') sage: R A recursively enumerated set (breadth first search)
-
rec_enum_set_under_language_joined
(language, initial, substitutions_dict, keep_equal_length=False, keep_unique=False, label='history', growth_limit=inf)¶ Return the recursively enumerated set of extension type generated by a language of substitutions where the extension type of the same age and joined.
INPUT:
language
– the language of substitutionsinitial
– initial substitutionsubstitutions_dict
- dict of substitutionskeep_equal_length
– (default: False) whether to keep images that have equal lengthkeep_unique
– (default: False) whether to keep a unique copy of equal extension typeslabel
– ‘history’ or ‘previous’ (default:'history'
), whether the vertices contain the whole history of the bispecial word or only the previous applied substitutiongrowth_limit
– integer (default:float('inf')
), the maximal growth in length of the bispecial extended images
EXAMPLES:
sage: from slabbe.bispecial_extension_type import ExtensionType sage: from slabbe.mult_cont_frac import Brun sage: from slabbe.language import languages sage: algo = Brun() sage: S = algo.substitutions() sage: L = languages.Brun() sage: v = algo.image((1,e,pi), 5) sage: prefix = algo.s_adic_word(v)[:100000] sage: E = ExtensionType.from_factor(prefix.parent()(), prefix, nleft=2) sage: E.rec_enum_set_under_language_joined(L, 123, S) A recursively enumerated set (breadth first search) sage: E.rec_enum_set_under_language_joined(L, 123, S, label='previous') A recursively enumerated set (breadth first search)
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: from slabbe.language import languages sage: L = languages.Brun() sage: E = [E for E in E1.apply(S[123]) if E.factor().length() == 1][0] sage: R = E.rec_enum_set_under_language_joined(L, 123, S, label='previous') sage: R A recursively enumerated set (breadth first search)
-
rec_enum_set_under_sadic
(substitutions, substitutions_dict, keep_equal_length=False, growth_limit=inf)¶ Return the graded recursively enumerated set of all the extension type leading to those of age k generated by a finite sequence of substitutions of length k.
INPUT:
substitutions
– the sequence of substitutionssubstitutions_dict
- dict of substitutionskeep_equal_length
– (default: False) whether to keep images that have equal length, thus it will include all bispecial factors of age <= k on the highest graded component.growth_limit
– integer (default:float('inf')
), the maximal growth in length of the bispecial extended images
EXAMPLES:
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: R = E1.rec_enum_set_under_sadic([132]*2+[123]*6, S) sage: R A recursively enumerated set with a graded structure (breadth first search) sage: R.graded_component(0) {( E(w) 1 2 3 21 X 31 X 12 X X X 22 X 23 X m(w)=0, neutral, word: , ())} sage: [len(R.graded_component(i)) for i in range(9)] [1, 2, 2, 2, 2, 2, 2, 2, 3]
This used to be a bug in sage, it is now fixed:
sage: R.graded_component(9) set()
Including all younger bispecial factors:
sage: R = E1.rec_enum_set_under_sadic([132]*2+[123]*6, S, keep_equal_length=True) sage: [len(R.graded_component(i)) for i in range(9)] [1, 3, 4, 5, 6, 7, 8, 9, 16] sage: B = R.graded_component(8) sage: sorted((Z.factor(),Z.multiplicity()) for Z,_,_ in B) [(word: , 0), (word: 2, 0), (word: 22, 0), (word: 22322, 0), (word: 22322322, 0), (word: 22322322322, 0), (word: 22322322322322, 0), (word: 22322322322322322, 0), (word: 22322322322322322322, -1), (word: 2322, 0), (word: 2322322, 0), (word: 2322322322, 0), (word: 2322322322322, 0), (word: 2322322322322322, 0), (word: 2322322322322322322, 0), (word: 2322322322322322322, 1)]
-
rec_enum_set_under_sadic_joined
(substitutions, substitutions_dict, keep_equal_length=False, keep_unique=False, growth_limit=inf, filter_fn=None)¶ Return the recursively enumerated set of extension type generated by a language of substitutions where the extension type of the same age are joined.
INPUT:
substitutions
– the sequence of substitutionssubstitutions_dict
- dict of substitutionskeep_equal_length
– (default: False) whether to keep images that have equal lengthkeep_unique
– (default: False) whether to keep a unique copy of equal extension typesgrowth_limit
– integer (default:float('inf')
), the maximal growth in length of the bispecial extended imagesfilter_fn
– function (default:None
)
EXAMPLES:
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3))
sage: seq = [231,213,213,321]+[213,231,231,123]+[132,123] sage: R = E1.rec_enum_set_under_sadic_joined(seq, S, growth_limit=1) sage: R A recursively enumerated set with a graded structure (breadth first search)
sage: from slabbe.bispecial_extension_type import recursively_enumerated_set_to_digraph sage: G = recursively_enumerated_set_to_digraph(R) sage: G Looped multi-digraph on 11 vertices
-
right_extensions
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E.right_extensions() {1, 2, 3}
-
weakstrong_poset
(language, initial, substitutions_dict, depth)¶ Return the Poset of words of the language ending with initial letter that gives weak or strong bispecial factors with the “is suffix” relation.
INPUT:
language
– the language of substitutionsinitial
– initial substitutionsubstitutions_dict
- dict of substitutionsdepth
– depth
EXAMPLES:
sage: from slabbe.mult_cont_frac import Brun sage: from slabbe.bispecial_extension_type import ExtensionType sage: from slabbe.language import languages sage: algo = Brun() sage: S = algo.substitutions() sage: L = languages.Brun() sage: v = algo.image((1,e,pi), 5) sage: prefix = algo.s_adic_word(v)[:1000] sage: E = ExtensionType.from_factor(prefix.parent()(), prefix, nleft=2) sage: P = E.weakstrong_poset(L, 123, S, 4) sage: P Finite poset containing 2 elements
sage: from slabbe.tikz_picture import TikzPicture sage: tikz = TikzPicture.from_poset(P) # optional dot2tex sage: _ = tikz.pdf(view=False) # optional dot2tex
-
weakstrong_sublanguage
(language, initial, substitutions_dict, depth, keep_empty=False)¶ Return the word of length depth+1 ending with initial letter of the language that gives weak or strong bispecial factors.
INPUT:
language
– the language of substitutionsinitial
– initial substitutionsubstitutions_dict
- dict of substitutionsdepth
– depthkeep_empty
– (default: False) whether to keep images that are empty
EXAMPLES:
sage: from slabbe.mult_cont_frac import Brun sage: from slabbe.bispecial_extension_type import ExtensionType sage: from slabbe.language import languages sage: algo = Brun() sage: S = algo.substitutions() sage: L = languages.Brun() sage: v = algo.image((1,e,pi), 5) sage: prefix = algo.s_adic_word(v)[:100000] sage: E = ExtensionType.from_factor(prefix.parent()(), prefix, nleft=2) sage: E.weakstrong_sublanguage(L, 123, S, 2) set() sage: E.weakstrong_sublanguage(L, 123, S, 3) {(213, 213, 231, 123), (231, 213, 231, 123)} sage: E.weakstrong_sublanguage(L, 123, S, 4) # long time (8s) {(132, 213, 213, 231, 123), (213, 213, 213, 231, 123), (213, 213, 231, 231, 123), (213, 231, 213, 231, 123), (231, 213, 213, 231, 123), (231, 213, 231, 231, 123), (231, 231, 213, 231, 123), (312, 231, 213, 231, 123)}
-
-
class
slabbe.bispecial_extension_type.
ExtensionType1to1
(L, alphabet, chignons=('', ''), factor=word:, repr_options=None)¶ Bases:
slabbe.bispecial_extension_type.ExtensionType
INPUT:
L
- list of pairs of lettersalphabet
- the alphabetchignons
- optional (default: None), pair of words added to the left and to the right of the image of the previous bispecialfactor
- optional (default: empty word), the factorrepr_options
- dict (default:None
) representation options whether to include the factor and or the valence in the string or latex representation. The valueNone
is replaced bydict(factor=False,multiplicity=True,valence=False))
.
EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, ord.
With chignons:
sage: E = ExtensionType1to1(L, [1,2,3], ('a','b')) sage: E E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, ord.
-
apply
(m, growth_limit=inf)¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, ord. sage: ar = WordMorphism({1:[1,3],2:[2,3],3:[3]}) sage: E.apply(ar) ( E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, ord.,)
sage: ar = WordMorphism({1:[3,1],2:[3,2],3:[3]}) sage: E.apply(ar) ( E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, ord.,)
Creation of a pair of ordinaire bispecial words from an ordinaire word:
sage: e = ExtensionType1to1([(1,3),(2,3),(3,1),(3,2),(3,3)], [1,2,3]) sage: p0 = WordMorphism({1:[1,2,3],2:[2,3],3:[3]}) sage: e.apply(p0) ( E(w) 1 2 3 1 2 X 3 X X X m(w)=0, ord.,) sage: p3 = WordMorphism({1:[1,3,2],2:[2],3:[3,2]}) sage: e.apply(p3) ( E(w) 1 2 3 1 2 X 3 X X X m(w)=0, ord., E(w) 1 2 3 1 X 2 X X X 3 m(w)=0, ord.)
Creation of a strong-weak pair of bispecial words from a neutral not ordinaire word:
sage: p0 = WordMorphism({1:[1,2,3],2:[2,3],3:[3]}) sage: e = ExtensionType1to1([(1,2),(2,3),(3,1),(3,2),(3,3)], [1,2,3]) sage: e.apply(p0) ( E(w) 1 2 3 1 2 X X 3 X X X m(w)=1, strong, E(w) 1 2 3 1 X 2 3 X m(w)=-1, weak)
Creation of a pair of ordinaire bispecial words from an not ordinaire word:
sage: p1 = WordMorphism({1:[1,2],2:[2],3:[3,1,2]}) sage: e = ExtensionType1to1([(1,2),(2,3),(3,1),(3,2),(3,3)], [1,2,3]) sage: e.apply(p1) ( E(w) 1 2 3 1 X X X 2 X 3 m(w)=0, ord., E(w) 1 2 3 1 2 X 3 X X X m(w)=0, ord.)
This result is now fixed:
sage: e = ExtensionType1to1([(1,2), (3,3)], [1,2,3]) sage: p3 = WordMorphism({1:[1,3,2],2:[2],3:[3,2]}) sage: e.apply(p3) ( E(w) 1 2 3 1 X 2 X 3 m(w)=-1, weak,)
sage: e = ExtensionType1to1([(2,2),(2,3),(3,1),(3,2),(3,3)], [1,2,3]) sage: e.apply(p3) ( E(w) 1 2 3 1 2 X X 3 X X X m(w)=1, strong,)
This result is now fixed:
sage: e = ExtensionType1to1([(2,2),(2,3),(3,1),(3,2),(3,3)], [1,2,3]) sage: p2 = WordMorphism({1:[1],2:[2,3,1],3:[3,1]}) sage: e.apply(p2) ( E(w) 1 2 3 1 X X X 2 X X 3 m(w)=1, strong,)
sage: e = ExtensionType1to1([(1,2),(3,3)], [1,2,3]) sage: e.apply(p2) ( E(w) 1 2 3 1 X 2 3 X m(w)=-1, weak,)
TESTS:
sage: L = [(1,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E E(w) 1 2 3 1 X 2 3 m(w)=0, neutral sage: ar = WordMorphism({1:[1,3],2:[2,3],3:[3]}) sage: E.apply(ar) ()
POSSIBLE BUG:
sage: from slabbe import ExtensionType sage: b23 = WordMorphism({1:[1],2:[2,3],3:[3]}) sage: b13 = WordMorphism({1:[1,3],2:[2],3:[3]}) sage: b31 = WordMorphism({1:[1],2:[2],3:[3,1]}) sage: e = ExtensionType.from_morphism(b23) sage: r = e.apply(b23)[0] sage: r.apply(b13) () sage: r.apply(b31) ()
-
cardinality
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.cardinality() 5
-
chignons_multiplicity_tuple
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3], ('a', 'b')) sage: E.chignons_multiplicity_tuple() ('a', 'b', 0)
-
extension_digraph
()¶ Return the extension directed graph made of edges
(-1,a) -> (+1,b)for each pair (a,b) in the extension set.
EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E.extension_digraph() Bipartite graph on 6 vertices
-
extension_graph
(loops=False)¶ Return the extension graph made of edges (a,b) for each pair (a,b) in the extension set.
EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E.extension_graph() Graph on 3 vertices sage: E.extension_graph(loops=True) Looped graph on 3 vertices
sage: L = [(1,1), (1,2), (2,1), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: G = E.extension_graph() sage: G.is_connected() False
-
is_ordinaire
()¶ EXAMPLES:
ordinary:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, ord. sage: E.is_ordinaire() True
strong:
sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3), (1,1)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E.is_ordinaire() False
neutral but not ordinary:
sage: L = [(1,1), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, neutral sage: E.is_neutral() True sage: E.is_ordinaire() False
not neutral, not ordinaire:
sage: L = [(1,1), (2,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E E(w) 1 2 3 1 X 2 X 3 X X m(w)=-1, weak sage: E.is_neutral() False sage: E.is_ordinaire() False
-
left_extensions
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.left_extensions() {1, 2, 3}
-
left_valence
(length=1)¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.left_valence() 3
-
palindromic_extensions
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.palindromic_extensions() {3}
-
right_extensions
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.right_extensions() {1, 2, 3}
-
right_valence
(length=1)¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3]) sage: E.right_valence() 3
-
table
()¶ return a table representation of self.
EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, alphabet=(1,2,3)) sage: E.table() E(w) 1 2 3 1 X 2 X 3 X X X
sage: E = ExtensionType1to1(L, alphabet=(1,2,3), chignons=('a', 'b')) sage: E.table() E(w) 1 2 3 1 X 2 X 3 X X X
-
class
slabbe.bispecial_extension_type.
ExtensionTypeLong
(L, alphabet, chignons=('', ''), factor=word:, factors_length_k=None, empty=None, repr_options=None)¶ Bases:
slabbe.bispecial_extension_type.ExtensionType
Generalized to words.
INPUT:
L
- list of pairs of wordsalphabet
- the alphabetchignons
- optional (default: None), pair of words added to the left and to the right of the image of the previous bispecialfactor
- optional (default: empty word), the factorfactors_length_k
- list of factors of length 2. If None, they are computed from the provided extension assuming the bispecial factor is empty.empty
- bool, (optional, default: None), if None, then it is computed from the chignons and takes value True iff the chignons are empty.repr_options
- dict (default:None
) representation options whether to include the factor and or the valence in the string or latex representation. The valueNone
is replaced bydict(factor=False,multiplicity=True,valence=False))
.
EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E E(w) 1 2 3 21 X 31 X 12 X X X 22 X 23 X m(w)=0, neutral
-
apply
(m, l=2, r=1, growth_limit=inf)¶ The code works for Brun here because we take length 2 on the left and length 1 on the right.
On utilise les facteurs de longueur 2 pour completer l’info qui peut manquer.
TODO: bien corriger les facteurs de longueurs 2 de l’image!!!
INPUT:
m
- substitutionl
- integer, length of left extensionr
- integer, length of right extensiongrowth_limit
– integer (default:float('inf')
), the maximal growth in length of the bispecial extended images
OUTPUT:
list of Extension type of the bispecial images
POSSIBLE BUG:
sage: from slabbe import ExtensionType sage: b23 = WordMorphism({1:[1],2:[2,3],3:[3]}) sage: b13 = WordMorphism({1:[1,3],2:[2],3:[3]}) sage: b31 = WordMorphism({1:[1],2:[2],3:[3,1]}) sage: e = ExtensionType.from_morphism(b23) sage: r = e.apply(b23)[0] sage: r.apply(b13) () sage: r.apply(b31) ()
Ce bug se corrige avec de plus grandes extensions a gauche et en considérant les facteurs de longueur 2:
sage: from slabbe import ExtensionTypeLong sage: E = ExtensionTypeLong((([a],[b]) for a,b in e), (1,2,3)) sage: R = E.apply(b23, l=1)[0] sage: R.apply(b13, l=1) ( E(w) 1 2 3 1 X 2 X 3 X X X m(w)=0, ord.,) sage: R.apply(b31, l=1) ( E(w) 1 2 3 1 X X X 2 X 3 X m(w)=0, neutral, E(w) 1 2 3 1 X X X 3 X X X m(w)=2, strong)
EXAMPLES:
On imagine qu’on vient de faire b12:
sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E E(w) 1 2 3 21 X 31 X 12 X X X 22 X 23 X m(w)=0, neutral sage: b12 = WordMorphism({1:[1,2],2:[2],3:[3]}) sage: E.apply(b12) ( E(w) 1 2 3 21 X 31 X 12 X 22 X X X 23 X m(w)=0, neutral, E(w) 1 2 3 21 X 31 X 12 X X X 22 X m(w)=0, ord.)
sage: b21 = WordMorphism({1:[1],2:[2,1],3:[3]}) sage: E.apply(b21) ( E(w) 1 2 3 11 X 21 X X X 31 X 12 X 13 X m(w)=0, ord., E(w) 1 2 3 21 X 12 X X X 13 X m(w)=0, ord.) sage: b23 = WordMorphism({1:[1],2:[2,3],3:[3]}) sage: E.apply(b23) ( E(w) 1 2 3 31 X X X 23 X m(w)=0, ord., E(w) 1 2 3 31 X 12 X 32 X 23 X X X 33 X m(w)=0, neutral, E(w) 1 2 3 12 X X X 32 X 23 X m(w)=0, ord.)
Not letter is missing:
sage: data = [[(1, 1, 1), (3,)], [(1, 1, 1), (1,)], [(1, 1, 1), (2,)], [(1, 2), ....: (1,)], [(2, 1), (1,)], [(1, 3), (1,)], [(3, 1), (2,)]] sage: E5 = ExtensionTypeLong(data, (1,2,3)) sage: b21 = WordMorphism({1:[1],2:[2,1],3:[3]}) sage: E51, = [E for E in E5.apply(b21) if E.factor().length()==1] sage: b21 = WordMorphism({1:[1],2:[2,1],3:[3]}) sage: E51.apply(b21) ( E(w) 1 2 3 11 X X X 21 X 12 X 13 X m(w)=0, neutral, E(w) 1 2 3 11 X X X 21 X 12 X m(w)=0, ord.)
We check that 12 is a left extension of X because this can not be guessed only from the direct image of left extensions:
sage: b21 = WordMorphism({1:[1],2:[2,1],3:[3]}) sage: data = [((1, 1), (2,)), ((2, 1), (3,)), ((2, 1), (2,)), ....: ((1, 2), (1,)), ((2, 1), (1,)), ((1, 3), (2,))] sage: F = [(1,1,1), (1,2,1), (1,1,3), (3,1,2), (2,1,1), (1,1,2), (1,3,1)] sage: F = [Word(f) for f in F] sage: E4_1 = ExtensionTypeLong(data, (1,2,3), factor=Word([1]), ....: factors_length_k=F, empty=False) sage: X,Y = E4_1.apply(b21) sage: X E(w) 1 2 3 11 X X X 21 X 12 X 13 X m(w)=0, neutral
-
cardinality
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.cardinality() 5
-
chignons_multiplicity_tuple
()¶ EXAMPLES:
sage: from slabbe import ExtensionType1to1 sage: L = [(1,3), (2,3), (3,1), (3,2), (3,3)] sage: E = ExtensionType1to1(L, [1,2,3], ('a', 'b')) sage: E.chignons_multiplicity_tuple() ('a', 'b', 0)
-
extension_type_1to1
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.extension_type_1to1() E(w) 1 2 3 1 X 2 X X X 3 X m(w)=0, neutral
-
factors_length_k
(k=None)¶ Returns the set of factors of length k of the language.
This is computed from the extension type if it was not provided at the construction.
INPUT:
k
– integer or None, if None, return factors of length k already computed
EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: sorted(E.factors_length_k(2)) [word: 12, word: 21, word: 22, word: 23, word: 31] sage: sorted(E.factors_length_k()) [word: 12, word: 21, word: 22, word: 23, word: 31]
It stores the value and can not compute for other lengths:
sage: E = ExtensionTypeLong(L, (1,2,3)) sage: sorted(E.factors_length_k(3)) [word: 121, word: 122, word: 123, word: 212, word: 221, word: 231, word: 312] sage: sorted(E.factors_length_k()) [word: 121, word: 122, word: 123, word: 212, word: 221, word: 231, word: 312] sage: sorted(E.factors_length_k(4)) Traceback (most recent call last): ... NotImplementedError: can't compute factors of length k for this word
sage: L = [(1, 2), (3, 2), (1, 3), (3, 3), (3, 1), (2, 3), (1, 1)] sage: E = ExtensionTypeLong((([a], [b]) for a,b in L), (1,2,3)) sage: E.factors_length_k(2) {word: 11, word: 12, word: 13, word: 23, word: 31, word: 32, word: 33}
TESTS:
sage: L = [(1, 2), (3, 2), (1, 3), (3, 3), (3, 1), (2, 3), (1, 1)] sage: E = ExtensionTypeLong((([a], [b]) for a,b in L), (1,2,3), factors_length_k=set()) sage: E.factors_length_k(2) Traceback (most recent call last): ... NotImplementedError: can't compute factors of length k for this word
-
is_chignons_empty
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.is_chignons_empty() True
-
is_ordinaire
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.extension_type_1to1() E(w) 1 2 3 1 X 2 X X X 3 X m(w)=0, neutral sage: E.is_ordinaire() False
-
is_subset
(other)¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: F = ExtensionTypeLong(L, (1,2,3)) sage: E.is_subset(F) True sage: F.is_subset(E) False
With incomplete word extensions:
sage: L = [((3,), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: G = ExtensionTypeLong(L, (1,2,3)) sage: G E(w) 1 2 3 21 X 31 X 12 X X X 3 X m(w)=0, neutral sage: G.is_subset(E) True
-
is_valid
()¶ Return whether self is valid, i.e, each left and right extension is non empty.
EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.is_valid() True
-
left_extensions
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.left_extensions() {1, 2, 3}
-
left_valence
(length=1)¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.left_valence() 3 sage: E.left_valence(2) 5
-
left_word_extensions
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: sorted(E.left_word_extensions()) [word: 12, word: 21, word: 22, word: 23, word: 31]
-
letters_before_and_after
(factors)¶ Returns a pair of dict giving the words letters that goes before the left extensions and after the right extensions.
INPUT:
factors
– factors of length k
OUTPUT:
pair of dict
EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: F = sorted(E.factors_length_k(2)) sage: E.letters_before_and_after(F) ({word: 12: {word: 2, word: 3}, word: 21: {word: 1, word: 2}, word: 22: {word: 1, word: 2}, word: 23: {word: 1, word: 2}, word: 31: {word: 2}}, {word: 1: {word: 2}, word: 2: {word: 1, word: 2, word: 3}, word: 3: {word: 1}})
sage: E = ExtensionTypeLong(L, (1,2,3)) sage: F = sorted(E.factors_length_k(3)) sage: E.letters_before_and_after(F) ({word: 12: {word: 2, word: 3}, word: 21: {word: 1, word: 2}, word: 22: {word: 1}, word: 23: {word: 1}, word: 31: {word: 2}}, {word: 1: {word: 21, word: 22, word: 23}, word: 2: {word: 12, word: 21, word: 31}, word: 3: {word: 12}})
sage: data = [[(1, 1, 1), (3,)], [(1, 1, 1), (1,)], [(1, 1, 1), (2,)], [(1, 2), ....: (1,)], [(2, 1), (1,)], [(1, 3), (1,)], [(3, 1), (2,)]] sage: E5 = ExtensionTypeLong(data, (1,2,3)) sage: b21 = WordMorphism({1:[1],2:[2,1],3:[3]}) sage: E51, = [E for E in E5.apply(b21) if E.factor().length()==1] sage: F = sorted(E51.factors_length_k(3)) sage: F [word: 111, word: 112, word: 113, word: 121, word: 131, word: 211, word: 312] sage: before,after = E.letters_before_and_after(F) sage: before {word: 11: {word: 1, word: 2}, word: 12: {word: 1, word: 3}, word: 13: {word: 1}, word: 21: {word: 1}} sage: after {word: 1: {word: 11, word: 12, word: 13, word: 21, word: 31}, word: 2: {word: 11}, word: 3: {word: 12}}
-
palindromic_extensions
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.palindromic_extensions() {2}
-
right_extensions
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.right_extensions() {1, 2, 3}
-
right_valence
(length=1)¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E.right_valence() 3
-
right_word_extensions
()¶ EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: sorted(E.right_word_extensions()) [word: 1, word: 2, word: 3]
-
table
()¶ return a table representation of self.
EXAMPLES:
sage: from slabbe import ExtensionTypeLong sage: L = [((2, 2), (1,)), ((2, 3), (1,)), ((2, 1), (2,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((3, 1), (2,))] sage: E = ExtensionTypeLong(L, (1,2,3)) sage: E E(w) 1 2 3 21 X 31 X 12 X X X 22 X 23 X m(w)=0, neutral
-
slabbe.bispecial_extension_type.
longest_common_prefix
(L)¶ Return the longest common prefix of a list of words.
EXAMPLES:
sage: from slabbe.bispecial_extension_type import longest_common_prefix sage: longest_common_prefix((Word('ab'), Word('abc'), Word('abd'))) word: ab
-
slabbe.bispecial_extension_type.
longest_common_suffix
(L)¶ Return the longest common suffix of a list of words.
EXAMPLES:
sage: from slabbe.bispecial_extension_type import longest_common_suffix sage: longest_common_suffix((Word('abc'), Word('bc'), Word('xabc'))) word: bc
-
slabbe.bispecial_extension_type.
rec_enum_set_under_language_joined_from_pairs
(pairs, language, substitutions_dict, keep_equal_length=False, keep_unique=False, label='history', growth_limit=inf, filter_fn=None)¶ Return the recursively enumerated set of extension type generated by a language of substitutions where the extension type of the same age and joined.
INPUT:
pairs
– list of pairs of (extension type, previous substitution key)language
– the language of substitutionssubstitutions_dict
- dict of substitutionskeep_equal_length
– (default: False) whether to keep images that have equal lengthkeep_unique
– (default: False) whether to keep a unique copy of equal extension typeslabel
– ‘history’ or ‘previous’ (default:'history'
), whether the vertices contain the whole history of the bispecial word or only the previous applied substitutiongrowth_limit
– integer (default:float('inf')
), the maximal growth in length of the bispecial extended imagesfilter_fn
– function (default:None
)
EXAMPLES:
sage: from slabbe.bispecial_extension_type import rec_enum_set_under_language_joined_from_pairs sage: from slabbe.bispecial_extension_type import ExtensionType sage: from slabbe.mult_cont_frac import Brun sage: from slabbe.language import languages sage: algo = Brun() sage: S = algo.substitutions() sage: L = languages.Brun() sage: v = algo.image((1,e,pi), 5) sage: prefix = algo.s_adic_word(v)[:1000] sage: E = ExtensionType.from_factor(prefix.parent()(), prefix, nleft=2) sage: pairs = [(E,123)] sage: rec_enum_set_under_language_joined_from_pairs(pairs, L, S) A recursively enumerated set (breadth first search) sage: rec_enum_set_under_language_joined_from_pairs(pairs, L, S, label='previous') A recursively enumerated set (breadth first search)
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: from slabbe.language import languages sage: L = languages.Brun() sage: E = [E for E in E1.apply(S[123]) if E.factor().length() == 1][0] sage: pairs = [(E,123)] sage: rec_enum_set_under_language_joined_from_pairs(pairs, L, S, label='previous') A recursively enumerated set (breadth first search)
sage: from slabbe.mult_cont_frac import Brun sage: algo = Brun() sage: S = algo.substitutions() sage: from slabbe.language import languages sage: LBrun = languages.Brun() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: pairs = [(E1, 312)] #, (E2, 312), (E3, 312), (E4, 321), (E5, 321)] sage: f = lambda S:any(len(ext.left_word_extensions())>2 for ext in S) sage: from slabbe.bispecial_extension_type import rec_enum_set_under_language_joined_from_pairs sage: R = rec_enum_set_under_language_joined_from_pairs(pairs, ....: LBrun, S, keep_equal_length=False, label='previous', growth_limit=1, filter_fn=f) sage: R A recursively enumerated set (breadth first search) sage: from slabbe.bispecial_extension_type import recursively_enumerated_set_to_digraph sage: recursively_enumerated_set_to_digraph(R) # long time (12s) Looped multi-digraph on 127 vertices
Testing the keep_unique option (not a good example apparently?):
sage: from slabbe.mult_cont_frac import Brun sage: algo = Brun() sage: S = algo.substitutions() sage: from slabbe.language import languages sage: LBrun = languages.Brun() sage: data = [((1,1),(2,)),((2,1),(3,)),((2,1),(2,)), ....: ((1,2),(1,)),((2,1),(1,)),((1,3),(2,))] sage: factors = [Word(w) for w in [(1,1,1),(1,2,1),(1,1,3),(3,1,2),(2,1,1),(1,1,2),(1,3,1)]] sage: E4_1 = ExtensionTypeLong(data, (1,2,3), factor=Word([1]), factors_length_k=factors) sage: pairs = [(E4_1, 321)] sage: f = lambda S:any(len(ext.left_word_extensions())>2 for ext in S) sage: R = rec_enum_set_under_language_joined_from_pairs(pairs, ....: LBrun, S, keep_equal_length=False, ....: keep_unique=False, label='previous', growth_limit=1, filter_fn=f) sage: R.to_digraph() # long time (15s) Looped multi-digraph on 129 vertices
sage: R = rec_enum_set_under_language_joined_from_pairs(pairs, ....: LBrun, S, keep_equal_length=False, ....: keep_unique=True, label='previous', growth_limit=1, filter_fn=f) sage: R.to_digraph() # long time (15s) Looped multi-digraph on 129 vertices
-
slabbe.bispecial_extension_type.
recursively_enumerated_set_to_digraph
(R, max_depth=inf)¶ Return the graph of the recursively enumerated set.
TODO:
Move this to sage.EXAMPLES:
sage: from slabbe.bispecial_extension_type import recursively_enumerated_set_to_digraph sage: child = lambda i: [(i+3) % 10, (i+8)%10] sage: R = RecursivelyEnumeratedSet([0], child) sage: G = recursively_enumerated_set_to_digraph(R) sage: G Looped multi-digraph on 10 vertices
-
slabbe.bispecial_extension_type.
remove_extension_types_subsets
(extensions)¶ Remove the extension types that are subset of another one associated to the same factor.
INPUT:
extensions
– iterable for extension types
EXAMPLES:
sage: from slabbe.bispecial_extension_type import ExtensionTypeLong sage: from slabbe.mult_cont_frac import Brun sage: S = Brun().substitutions() sage: data = [((2, 1), (2,)), ((3, 1), (2,)), ((2, 2), (3,)), ((1, ....: 2), (1,)), ((1, 2), (2,)), ((1, 2), (3,)), ((2, 3), (1,))] sage: E1 = ExtensionTypeLong(data, (1,2,3)) sage: R = E1.rec_enum_set_under_sadic([132]*2+[123]*6, S) sage: A = [E for E,w,h in R.graded_component(8)] sage: A.sort(key=lambda a:(a.factor(), len(a.left_word_extensions()))) sage: [a.factor() for a in A] [word: 22322322322322322322, word: 2322322322322322322, word: 2322322322322322322] sage: A[1].is_subset(A[2]) True sage: from slabbe.bispecial_extension_type import remove_extension_types_subsets sage: B = remove_extension_types_subsets(A) sage: B [ E(w) 1 3 32 X 23 X m(w)=-1, weak, E(w) 1 2 3 21 X X X 22 X 32 X m(w)=1, strong] sage: [b.factor() for b in B] [word: 22322322322322322322, word: 2322322322322322322]
-
slabbe.bispecial_extension_type.
table_bispecial
(word, k, nleft=1, nright=1)¶ Return the table of the first k bispecial factors of a word.
INPUT:
word
– finite wordk
– integer
OUTPUT:
tableEXAMPLES:
sage: from slabbe.bispecial_extension_type import table_bispecial sage: w = words.FibonacciWord() sage: table_bispecial(w[:10000], 6) |w| word m(w) info d^-(w) d^+(w) +-----+---------------------+------+------+--------+--------+ 0 0 ord. 2 2 1 0 0 ord. 2 2 3 010 0 ord. 2 2 6 010010 0 ord. 2 2 11 01001010010 0 ord. 2 2 19 0100101001001010010 0 ord. 2 2
sage: w = words.FibonacciWord() sage: table_bispecial(w[:10000], 6, nleft=2) |w| word m(w) info d^-(w) d_2^-(w) d^+(w) +-----+---------------------+------+------+--------+----------+--------+ 0 0 ord. 2 3 2 1 0 0 ord. 2 2 2 3 010 0 ord. 2 2 2 6 010010 0 ord. 2 2 2 11 01001010010 0 ord. 2 2 2 19 0100101001001010010 0 ord. 2 2 2
sage: w = words.ThueMorseWord() sage: table_bispecial(w[:10000], 11) |w| word m(w) info d^-(w) d^+(w) +-----+--------+------+--------+--------+--------+ 0 1 strong 2 2 1 0 0 ord. 2 2 1 1 0 ord. 2 2 2 01 1 strong 2 2 2 10 1 strong 2 2 3 010 -1 weak 2 2 3 101 -1 weak 2 2 4 0110 1 strong 2 2 4 1001 1 strong 2 2 6 011001 -1 weak 2 2 6 100110 -1 weak 2 2