# 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 substitutions
• substitutions_dict - dict of substitutions
• keep_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))
|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 substitutions
• substitutions_dict - dict of substitutions
• keep_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: 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 factor
• word – the word describing the language
• nleft – 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 value None is replaced by dict(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 - endomorphim
• repr_options - dict (default:None) representation options whether to include the factor and or the valence in the string or latex representation. The value None is replaced by dict(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 substitutions
• initial – initial substitution
• substitutions_dict - dict of substitutions
• keep_empty – bool (default: False) whether to keep images that are empty
• max_depth – integer (default: float('inf')), max depth
• 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: 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 substitutions
• initial – initial substitution
• substitutions_dict - dict of substitutions
• keep_empty – bool (default: False) whether to keep images that are empty
• max_depth – integer (default: float('inf')), max depth
• 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: 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 substitutions
• substitutions_dict - dict of substitutions
• keep_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 information
• 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))
Looped multi-digraph on 9 vertices
Looped multi-digraph on 19 vertices
Looped multi-digraph on 18 vertices
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 substitutions
• substitutions_dict - dict of substitutions
• keep_equal_length – (default: False) whether to keep images that have equal length
• keep_unique – (default: False) whether to keep a unique copy of equal extension types
• growth_limit – integer (default: float('inf')), the maximal growth in length of the bispecial extended images
• filter_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]
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 substitutions
• initial – initial substitution
• substitutions_dict - dict of substitutions
• keep_empty – (default: False) whether to keep images that are empty
• label – ‘history’ or ‘previous’ (default: 'history'), whether the vertices contain the whole history of the bispecial word or only the previous applied substitution
• growth_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: 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 substitutions
• initial – initial substitution
• substitutions_dict - dict of substitutions
• keep_equal_length – (default: False) whether to keep images that have equal length
• keep_unique – (default: False) whether to keep a unique copy of equal extension types
• label – ‘history’ or ‘previous’ (default: 'history'), whether the vertices contain the whole history of the bispecial word or only the previous applied substitution
• growth_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: 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 substitutions
• substitutions_dict - dict of substitutions
• keep_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
{(  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: 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 substitutions
• substitutions_dict - dict of substitutions
• keep_equal_length – (default: False) whether to keep images that have equal length
• keep_unique – (default: False) whether to keep a unique copy of equal extension types
• growth_limit – integer (default: float('inf')), the maximal growth in length of the bispecial extended images
• filter_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

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 substitutions
• initial – initial substitution
• substitutions_dict - dict of substitutions
• depth – 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: 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 substitutions
• initial – initial substitution
• substitutions_dict - dict of substitutions
• depth – depth
• keep_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: 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)

INPUT:

• L - list of pairs of letters
• alphabet - the alphabet
• chignons - optional (default: None), pair of words added to the left and to the right of the image of the previous bispecial
• factor - optional (default: empty word), the factor
• repr_options - dict (default:None) representation options whether to include the factor and or the valence in the string or latex representation. The value None is replaced by dict(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)

Generalized to words.

INPUT:

• L - list of pairs of words
• alphabet - the alphabet
• chignons - optional (default: None), pair of words added to the left and to the right of the image of the previous bispecial
• factor - optional (default: empty word), the factor
• factors_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 value None is replaced by dict(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 - substitution
• l - integer, length of left extension
• r - integer, length of right extension
• growth_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 substitutions
• substitutions_dict - dict of substitutions
• keep_equal_length – (default: False) whether to keep images that have equal length
• keep_unique – (default: False) whether to keep a unique copy of equal extension types
• label – ‘history’ or ‘previous’ (default: 'history'), whether the vertices contain the whole history of the bispecial word or only the previous applied substitution
• growth_limit – integer (default: float('inf')), the maximal growth in length of the bispecial extended images
• filter_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: 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: 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 word
• k – integer

OUTPUT:

table

EXAMPLES:

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