# Factor complexity and Bispecial Extension Type¶

Factor complexity, Bispecial factors and Extension types

This module was developed for the article on the factor complexity of infinite sequences generated 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, dendric
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`

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         dendric
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
```

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, dendric
```
```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
```

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 import TikzPicture
sage: _ = TikzPicture.from_graph(G).pdf(view=False) # (9s)
doctest:...: FutureWarning: This class/method/function is marked as experimental.
It, its functionality or its interface might change without a formal deprecation.
See http://trac.sagemath.org/20343 for details.
```
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, dendric
```
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)
```

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, dendric, 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                               # known bug
Finite poset containing 2 elements
```
```sage: from slabbe import TikzPicture
sage: tikz = TikzPicture.from_poset(P)         # optional dot2tex # not tested
sage: _ = tikz.pdf(view=False)                 # optional dot2tex # not tested
```
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)   # known bug
{(213, 213, 231, 123), (231, 213, 231, 123)}
sage: E.weakstrong_sublanguage(L, 123, S, 4)   # long time (8s) # known bug
{(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, dendric
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_graph()

Return the bipartite extension 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_graph()
Bipartite graph on 6 vertices
```
is_dendric()

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_dendric()
True
```
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, dendric
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, dendric
```
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, dendric,
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, dendric
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, dendric,
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
12            X
32            X
23    X   X   X
33    X
m(w)=0, dendric,
E(w)   1   2   3
12    X   X   X
32    X
23    X
m(w)=0, ord.,
E(w)   1   2   3
31    X   X   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, dendric,
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, dendric
```
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, dendric
```
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_dendric()

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, dendric
sage: E.is_dendric()
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, dendric
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, dendric
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                             # known bug
{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, dendric
```
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
```