Finite word¶

AUTHORS:

Arnaud Bergeron
Amy Glen
Sébastien Labbé
Franco Saliola
Julien Leroy (March 2010): reduced_rauzy_graph

EXAMPLES:

Factors and Rauzy Graphs¶

Enumeration of factors, the successive values returned by next(it) can appear in a different order depending on hardware. Therefore we mark the three first results of the test random. The important test is that the iteration stops properly on the fourth call:

Sage

sage: w = Word([4,5,6])^7
sage: it = w.factor_iterator(4)
sage: next(it) # random
word: 6456
sage: next(it) # random
word: 5645
sage: next(it) # random
word: 4564
sage: next(it)
Traceback (most recent call last):
...
StopIteration

Python

>>> from sage.all import *
>>> w = Word([Integer(4),Integer(5),Integer(6)])**Integer(7)
>>> it = w.factor_iterator(Integer(4))
>>> next(it) # random
word: 6456
>>> next(it) # random
word: 5645
>>> next(it) # random
word: 4564
>>> next(it)
Traceback (most recent call last):
...
StopIteration

The set of factors:

Sage

sage: sorted(w.factor_set(3))
[word: 456, word: 564, word: 645]
sage: sorted(w.factor_set(4))
[word: 4564, word: 5645, word: 6456]
sage: w.factor_set().cardinality()
61

Python

>>> from sage.all import *
>>> sorted(w.factor_set(Integer(3)))
[word: 456, word: 564, word: 645]
>>> sorted(w.factor_set(Integer(4)))
[word: 4564, word: 5645, word: 6456]
>>> w.factor_set().cardinality()
61

Rauzy graphs:

Sage

sage: f = words.FibonacciWord()[:30]
sage: f.rauzy_graph(4)                                                              # needs sage.graphs
Looped digraph on 5 vertices
sage: f.reduced_rauzy_graph(4)                                                      # needs sage.graphs
Looped multi-digraph on 2 vertices

Python

>>> from sage.all import *
>>> f = words.FibonacciWord()[:Integer(30)]
>>> f.rauzy_graph(Integer(4))                                                              # needs sage.graphs
Looped digraph on 5 vertices
>>> f.reduced_rauzy_graph(Integer(4))                                                      # needs sage.graphs
Looped multi-digraph on 2 vertices

Left-special and bispecial factors:

Sage

sage: f.number_of_left_special_factors(7)
1
sage: f.bispecial_factors()
[word: , word: 0, word: 010, word: 010010, word: 01001010010]

Python

>>> from sage.all import *
>>> f.number_of_left_special_factors(Integer(7))
1
>>> f.bispecial_factors()
[word: , word: 0, word: 010, word: 010010, word: 01001010010]

class sage.combinat.words.finite_word.CallableFromListOfWords(words)[source]¶

Bases: tuple

A class to create a callable from a list of words. The concatenation of a list of words is obtained by creating a word from this callable.

class sage.combinat.words.finite_word.Factorization(iterable=(), /)[source]¶

Bases: list

A list subclass having a nicer representation for factorization of words.

class sage.combinat.words.finite_word.FiniteWord_class[source]¶

Bases: Word_class

BWT()[source]¶

Return the Burrows-Wheeler Transform (BWT) of self.

The Burrows-Wheeler transform of a finite word \(w\) is obtained from \(w\) by first listing the conjugates of \(w\) in lexicographic order and then concatenating the final letters of the conjugates in this order. See [BW1994].

EXAMPLES:

Sage

sage: Word('abaccaaba').BWT()
word: cbaabaaca
sage: Word('abaab').BWT()
word: bbaaa
sage: Word('bbabbaca').BWT()
word: cbbbbaaa
sage: Word('aabaab').BWT()
word: bbaaaa
sage: Word().BWT()
word:
sage: Word('a').BWT()
word: a

Python

>>> from sage.all import *
>>> Word('abaccaaba').BWT()
word: cbaabaaca
>>> Word('abaab').BWT()
word: bbaaa
>>> Word('bbabbaca').BWT()
word: cbbbbaaa
>>> Word('aabaab').BWT()
word: bbaaaa
>>> Word().BWT()
word:
>>> Word('a').BWT()
word: a

LZ_decomposition()[source]¶

Return the Crochemore factorization of self as an ordered list of factors.

The Crochemore factorization or the Lempel-Ziv decomposition of a finite word \(w\) is the unique factorization: \((x_1, x_2, \ldots, x_n)\) of \(w\) with each \(x_i\) satisfying either: C1. \(x_i\) is a letter that does not appear in \(u = x_1\ldots x_{i-1}\); C2. \(x_i\) is the longest prefix of \(v = x_i\ldots x_n\) that also has an occurrence beginning within \(u = x_1\ldots x_{i-1}\). See [Cro1983].

EXAMPLES:

Sage

sage: x = Word('abababb')
sage: x.crochemore_factorization()
(a, b, abab, b)
sage: mul(x.crochemore_factorization()) == x
True
sage: y = Word('abaababacabba')
sage: y.crochemore_factorization()
(a, b, a, aba, ba, c, ab, ba)
sage: mul(y.crochemore_factorization()) == y
True
sage: x = Word([0,1,0,1,0,1,1])
sage: x.crochemore_factorization()
(0, 1, 0101, 1)
sage: mul(x.crochemore_factorization()) == x
True

Python

>>> from sage.all import *
>>> x = Word('abababb')
>>> x.crochemore_factorization()
(a, b, abab, b)
>>> mul(x.crochemore_factorization()) == x
True
>>> y = Word('abaababacabba')
>>> y.crochemore_factorization()
(a, b, a, aba, ba, c, ab, ba)
>>> mul(y.crochemore_factorization()) == y
True
>>> x = Word([Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)])
>>> x.crochemore_factorization()
(0, 1, 0101, 1)
>>> mul(x.crochemore_factorization()) == x
True

abelian_complexity(n)[source]¶

Return the number of abelian vectors of factors of length n of self.

EXAMPLES:

Sage

sage: w = words.FibonacciWord()[:100]
sage: [w.abelian_complexity(i) for i in range(20)]
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Python

>>> from sage.all import *
>>> w = words.FibonacciWord()[:Integer(100)]
>>> [w.abelian_complexity(i) for i in range(Integer(20))]
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Sage

sage: w = words.ThueMorseWord()[:100]
sage: [w.abelian_complexity(i) for i in range(20)]
[1, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2]

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()[:Integer(100)]
>>> [w.abelian_complexity(i) for i in range(Integer(20))]
[1, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2]

abelian_vector()[source]¶

Return the abelian vector of self counting the occurrences of each letter.

The vector is defined w.r.t. the order of the alphabet of the parent. See also evaluation_dict().

INPUT:

self – word having a parent on a finite alphabet

OUTPUT: list

EXAMPLES:

Sage

sage: W = Words('ab')
sage: W('aaabbbbb').abelian_vector()
[3, 5]
sage: W('a').abelian_vector()
[1, 0]
sage: W().abelian_vector()
[0, 0]

Python

>>> from sage.all import *
>>> W = Words('ab')
>>> W('aaabbbbb').abelian_vector()
[3, 5]
>>> W('a').abelian_vector()
[1, 0]
>>> W().abelian_vector()
[0, 0]

The result depends on the alphabet of the parent:

Sage

sage: W = Words('abc')
sage: W('aabaa').abelian_vector()
[4, 1, 0]

Python

>>> from sage.all import *
>>> W = Words('abc')
>>> W('aabaa').abelian_vector()
[4, 1, 0]

abelian_vectors(n)[source]¶

Return the abelian vectors of factors of length n of self.

The vectors are defined w.r.t. the order of the alphabet of the parent.

OUTPUT: a set of tuples

EXAMPLES:

Sage

sage: W = Words([0,1,2])
sage: w = W([0,1,1,0,1,2,0,2,0,2])
sage: w.abelian_vectors(3)
{(1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1)}
sage: w[:5].abelian_vectors(3)
{(1, 2, 0)}
sage: w[5:].abelian_vectors(3)
{(1, 0, 2), (2, 0, 1)}

Python

>>> from sage.all import *
>>> W = Words([Integer(0),Integer(1),Integer(2)])
>>> w = W([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(2),Integer(0),Integer(2),Integer(0),Integer(2)])
>>> w.abelian_vectors(Integer(3))
{(1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1)}
>>> w[:Integer(5)].abelian_vectors(Integer(3))
{(1, 2, 0)}
>>> w[Integer(5):].abelian_vectors(Integer(3))
{(1, 0, 2), (2, 0, 1)}

Sage

sage: w = words.FibonacciWord()[:100]
sage: sorted(w.abelian_vectors(0))
[(0, 0)]
sage: sorted(w.abelian_vectors(1))
[(0, 1), (1, 0)]
sage: sorted(w.abelian_vectors(7))
[(4, 3), (5, 2)]

Python

>>> from sage.all import *
>>> w = words.FibonacciWord()[:Integer(100)]
>>> sorted(w.abelian_vectors(Integer(0)))
[(0, 0)]
>>> sorted(w.abelian_vectors(Integer(1)))
[(0, 1), (1, 0)]
>>> sorted(w.abelian_vectors(Integer(7)))
[(4, 3), (5, 2)]

The word must be defined with a parent on a finite alphabet:

Sage

sage: from itertools import count
sage: w = Word(count(), alphabet=NN)
sage: w[:2].abelian_vectors(2)
Traceback (most recent call last):
...
TypeError: The alphabet of the parent is infinite; define the
word with a parent on a finite alphabet

Python

>>> from sage.all import *
>>> from itertools import count
>>> w = Word(count(), alphabet=NN)
>>> w[:Integer(2)].abelian_vectors(Integer(2))
Traceback (most recent call last):
...
TypeError: The alphabet of the parent is infinite; define the
word with a parent on a finite alphabet

apply_permutation_to_letters(permutation)[source]¶

Return the word obtained by applying the permutation permutation of the alphabet of self to each letter of self.

EXAMPLES:

Sage

sage: w = Words('abcd')('abcd')
sage: p = [2,1,4,3]
sage: w.apply_permutation_to_letters(p)
word: badc
sage: u = Words('dabc')('abcd')
sage: u.apply_permutation_to_letters(p)
word: dcba
sage: w.apply_permutation_to_letters(Permutation(p))
word: badc
sage: w.apply_permutation_to_letters(PermutationGroupElement(p))            # needs sage.groups
word: badc

Python

>>> from sage.all import *
>>> w = Words('abcd')('abcd')
>>> p = [Integer(2),Integer(1),Integer(4),Integer(3)]
>>> w.apply_permutation_to_letters(p)
word: badc
>>> u = Words('dabc')('abcd')
>>> u.apply_permutation_to_letters(p)
word: dcba
>>> w.apply_permutation_to_letters(Permutation(p))
word: badc
>>> w.apply_permutation_to_letters(PermutationGroupElement(p))            # needs sage.groups
word: badc

apply_permutation_to_positions(permutation)[source]¶

Return the word obtained by permuting the positions of the letters in self according to the permutation permutation.

EXAMPLES:

Sage

sage: w = Words('abcd')('abcd')
sage: w.apply_permutation_to_positions([2,1,4,3])
word: badc
sage: u = Words('dabc')('abcd')
sage: u.apply_permutation_to_positions([2,1,4,3])
word: badc
sage: w.apply_permutation_to_positions(Permutation([2,1,4,3]))
word: badc
sage: w.apply_permutation_to_positions(PermutationGroupElement([2,1,4,3]))  # needs sage.groups
word: badc
sage: Word([1,2,3,4]).apply_permutation_to_positions([3,4,2,1])
word: 3421

Python

>>> from sage.all import *
>>> w = Words('abcd')('abcd')
>>> w.apply_permutation_to_positions([Integer(2),Integer(1),Integer(4),Integer(3)])
word: badc
>>> u = Words('dabc')('abcd')
>>> u.apply_permutation_to_positions([Integer(2),Integer(1),Integer(4),Integer(3)])
word: badc
>>> w.apply_permutation_to_positions(Permutation([Integer(2),Integer(1),Integer(4),Integer(3)]))
word: badc
>>> w.apply_permutation_to_positions(PermutationGroupElement([Integer(2),Integer(1),Integer(4),Integer(3)]))  # needs sage.groups
word: badc
>>> Word([Integer(1),Integer(2),Integer(3),Integer(4)]).apply_permutation_to_positions([Integer(3),Integer(4),Integer(2),Integer(1)])
word: 3421

balance()[source]¶

Return the balance of self.

The balance of a word is the smallest number \(q\) such that self is \(q\)-balanced [FV2002].

A finite or infinite word \(w\) is said to be \(q\)-balanced if for any two factors \(u\), \(v\) of \(w\) of the same length, the difference between the number of \(x\)’s in each of \(u\) and \(v\) is at most \(q\) for all letters \(x\) in the alphabet of \(w\). A \(1\)-balanced word is simply said to be balanced. See Chapter 2 of [Lot2002].

OUTPUT: integer

EXAMPLES:

Sage

sage: Word('1111111').balance()
0
sage: Word('001010101011').balance()
2
sage: Word('0101010101').balance()
1

Python

>>> from sage.all import *
>>> Word('1111111').balance()
0
>>> Word('001010101011').balance()
2
>>> Word('0101010101').balance()
1

Sage

sage: w = Word('11112222')
sage: w.is_balanced(2)
False
sage: w.is_balanced(3)
False
sage: w.is_balanced(4)
True
sage: w.is_balanced(5)
True
sage: w.balance()
4

Python

>>> from sage.all import *
>>> w = Word('11112222')
>>> w.is_balanced(Integer(2))
False
>>> w.is_balanced(Integer(3))
False
>>> w.is_balanced(Integer(4))
True
>>> w.is_balanced(Integer(5))
True
>>> w.balance()
4

bispecial_factors(n=None)[source]¶

Return the bispecial factors (of length n).

A factor \(u\) of a word \(w\) is bispecial if it is right special and left special.

INPUT:

n – integer (default: None); if None, it returns all bispecial factors

OUTPUT: list of words

EXAMPLES:

Sage

sage: w = words.FibonacciWord()[:30]
sage: w.bispecial_factors()
[word: , word: 0, word: 010, word: 010010, word: 01001010010]

Python

>>> from sage.all import *
>>> w = words.FibonacciWord()[:Integer(30)]
>>> w.bispecial_factors()
[word: , word: 0, word: 010, word: 010010, word: 01001010010]

Sage

sage: w = words.ThueMorseWord()[:30]
sage: for i in range(10):
....:     print("{} {}".format(i, sorted(w.bispecial_factors(i))))
[word: ]
[word: 0, word: 1]
[word: 01, word: 10]
[word: 010, word: 101]
[word: 0110, word: 1001]
[]
[word: 011001, word: 100110]
[]
[word: 10010110]
[]

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()[:Integer(30)]
>>> for i in range(Integer(10)):
...     print("{} {}".format(i, sorted(w.bispecial_factors(i))))
[word: ]
[word: 0, word: 1]
[word: 01, word: 10]
[word: 010, word: 101]
[word: 0110, word: 1001]
[]
[word: 011001, word: 100110]
[]
[word: 10010110]
[]

bispecial_factors_iterator(n=None)[source]¶

Return an iterator over the bispecial factors (of length n).

A factor \(u\) of a word \(w\) is bispecial if it is right special and left special.

INPUT:

n – integer (default: None); if None, it returns an iterator over all bispecial factors

EXAMPLES:

Sage

sage: w = words.ThueMorseWord()[:30]
sage: for i in range(10):
....:     for u in sorted(w.bispecial_factors_iterator(i)):
....:         print("{} {}".format(i,u))
0
1 0
1 1
2 01
2 10
3 010
3 101
4 0110
4 1001
6 011001
6 100110
8 10010110

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()[:Integer(30)]
>>> for i in range(Integer(10)):
...     for u in sorted(w.bispecial_factors_iterator(i)):
...         print("{} {}".format(i,u))
0
1 0
1 1
2 01
2 10
3 010
3 101
4 0110
4 1001
6 011001
6 100110
8 10010110

Sage

sage: key = lambda u : (len(u), u)
sage: for u in sorted(w.bispecial_factors_iterator(), key=key): u
word:
word: 0
word: 1
word: 01
word: 10
word: 010
word: 101
word: 0110
word: 1001
word: 011001
word: 100110
word: 10010110

Python

>>> from sage.all import *
>>> key = lambda u : (len(u), u)
>>> for u in sorted(w.bispecial_factors_iterator(), key=key): u
word:
word: 0
word: 1
word: 01
word: 10
word: 010
word: 101
word: 0110
word: 1001
word: 011001
word: 100110
word: 10010110

border()[source]¶

Return the longest word that is both a proper prefix and a proper suffix of self.

EXAMPLES:

Sage

sage: Word('121212').border()
word: 1212
sage: Word('12321').border()
word: 1
sage: Word().border() is None
True

Python

>>> from sage.all import *
>>> Word('121212').border()
word: 1212
>>> Word('12321').border()
word: 1
>>> Word().border() is None
True

charge(check=True)[source]¶

Return the charge of self. This is defined as follows.

If \(w\) is a permutation of length \(n\), (in other words, the evaluation of \(w\) is \((1, 1, \dots, 1)\)), the statistic charge(\(w\)) is given by \(\sum_{i=1}^n c_i(w)\) where \(c_1(w) = 0\) and \(c_i(w)\) is defined recursively by setting \(p_i\) equal to \(1\) if \(i\) appears to the right of \(i-1\) in \(w\) and \(0\) otherwise. Then we set \(c_i(w) = c_{i-1}(w) + p_i\).

EXAMPLES:

Sage

sage: Word([1, 2, 3]).charge()
3
sage: Word([3, 5, 1, 4, 2]).charge() == 0 + 1 + 1 + 2 + 2
True

Python

>>> from sage.all import *
>>> Word([Integer(1), Integer(2), Integer(3)]).charge()
3
>>> Word([Integer(3), Integer(5), Integer(1), Integer(4), Integer(2)]).charge() == Integer(0) + Integer(1) + Integer(1) + Integer(2) + Integer(2)
True

If \(w\) is not a permutation, but the evaluation of \(w\) is a partition, the charge of \(w\) is defined to be the sum of its charge subwords (each of which will be a permutation). The first charge subword is found by starting at the end of \(w\) and moving left until the first \(1\) is found. This is marked, and we continue to move to the left until the first \(2\) is found, wrapping around from the beginning of the word back to the end, if necessary. We mark this \(2\), and continue on until we have marked the largest letter in \(w\). The marked letters, with relative order preserved, form the first charge subword of \(w\). This subword is removed, and the next charge subword is found in the same manner from the remaining letters. In the following example, \(w1, w2, w3\) are the charge subwords of \(w\).

EXAMPLES:

Sage

sage: w = Word([5,2,3,4,4,1,1,1,2,2,3])
sage: w1 = Word([5, 2, 4, 1, 3])
sage: w2 = Word([3, 4, 1, 2])
sage: w3 = Word([1, 2])
sage: w.charge() == w1.charge() + w2.charge() + w3.charge()
True

Python

>>> from sage.all import *
>>> w = Word([Integer(5),Integer(2),Integer(3),Integer(4),Integer(4),Integer(1),Integer(1),Integer(1),Integer(2),Integer(2),Integer(3)])
>>> w1 = Word([Integer(5), Integer(2), Integer(4), Integer(1), Integer(3)])
>>> w2 = Word([Integer(3), Integer(4), Integer(1), Integer(2)])
>>> w3 = Word([Integer(1), Integer(2)])
>>> w.charge() == w1.charge() + w2.charge() + w3.charge()
True

Finally, if \(w\) does not have partition content, we apply the Lascoux-Schützenberger standardization operators \(s_i\) in such a manner as to obtain a word with partition content. (The word we obtain is independent of the choice of operators.) The charge is then defined to be the charge of this word:

Sage

sage: Word([3,3,2,1,1]).charge()
0
sage: Word([1,2,3,1,2]).charge()
2

Python

>>> from sage.all import *
>>> Word([Integer(3),Integer(3),Integer(2),Integer(1),Integer(1)]).charge()
0
>>> Word([Integer(1),Integer(2),Integer(3),Integer(1),Integer(2)]).charge()
2

Note that this differs from the definition of charge given in Macdonald’s book. The difference amounts to a choice of reading a word from left-to-right or right-to-left. The choice in Sage was made to agree with the definition of a reading word of a tableau in Sage, and seems to be the more common convention in the literature.

See [Mac1995], [LLM2003], and [LLT].

cocharge()[source]¶

Return the cocharge of self. For a word \(w\), this can be defined as \(n_{ev} - ch(w)\), where \(ch(w)\) is the charge of \(w\) and \(ev\) is the evaluation of \(w\), and \(n_{ev}\) is \(\sum_{i<j} min(ev_i, ev_j)\).

EXAMPLES:

Sage

sage: Word([1,2,3]).cocharge()
0
sage: Word([3,2,1]).cocharge()
3
sage: Word([1,1,2]).cocharge()
0
sage: Word([2,1,2]).cocharge()
1

Python

>>> from sage.all import *
>>> Word([Integer(1),Integer(2),Integer(3)]).cocharge()
0
>>> Word([Integer(3),Integer(2),Integer(1)]).cocharge()
3
>>> Word([Integer(1),Integer(1),Integer(2)]).cocharge()
0
>>> Word([Integer(2),Integer(1),Integer(2)]).cocharge()
1

coerce(other)[source]¶

Try to return a pair of words with a common parent; raise an exception if this is not possible.

This function begins by checking if both words have the same parent. If this is the case, then no work is done and both words are returned as-is.

Otherwise it will attempt to convert other to the domain of self. If that fails, it will attempt to convert self to the domain of other. If both attempts fail, it raises a TypeError to signal failure.

EXAMPLES:

Sage

sage: W1 = Words('abc'); W2 = Words('ab')
sage: w1 = W1('abc'); w2 = W2('abba'); w3 = W1('baab')
sage: w1.parent() is w2.parent()
False
sage: a, b = w1.coerce(w2)
sage: a.parent() is b.parent()
True
sage: w1.parent() is w2.parent()
False

Python

>>> from sage.all import *
>>> W1 = Words('abc'); W2 = Words('ab')
>>> w1 = W1('abc'); w2 = W2('abba'); w3 = W1('baab')
>>> w1.parent() is w2.parent()
False
>>> a, b = w1.coerce(w2)
>>> a.parent() is b.parent()
True
>>> w1.parent() is w2.parent()
False

colored_vector(x=0, y=0, width='default', height=1, cmap='hsv', thickness=1, label=None)[source]¶

Return a vector (Graphics object) illustrating self. Each letter is represented by a coloured rectangle.

If the parent of self is a class of words over a finite alphabet, then each letter in the alphabet is assigned a unique colour, and this colour will be the same every time this method is called. This is especially useful when plotting and comparing words defined on the same alphabet.

If the alphabet is infinite, then the letters appearing in the word are used as the alphabet.

INPUT:

x – (default: 0) bottom left x-coordinate of the vector
y – (default: 0) bottom left y-coordinate of the vector
width – (default: 'default') width of the vector. By default, the width is the length of self.
height – (default: 1) height of the vector
thickness – (default: 1) thickness of the contour
cmap – (default: 'hsv') color map; for available color map names type: import matplotlib.cm; list(matplotlib.cm.datad)
label – string (default: None); a label to add on the colored vector

OUTPUT: Graphics

EXAMPLES:

Sage

sage: # needs sage.plot
sage: Word(range(20)).colored_vector()
Graphics object consisting of 21 graphics primitives
sage: Word(range(100)).colored_vector(0,0,10,1)
Graphics object consisting of 101 graphics primitives
sage: Words(range(100))(range(10)).colored_vector()
Graphics object consisting of 11 graphics primitives
sage: w = Word('abbabaab')
sage: w.colored_vector()
Graphics object consisting of 9 graphics primitives
sage: w.colored_vector(cmap='autumn')
Graphics object consisting of 9 graphics primitives
sage: Word(range(20)).colored_vector(label='Rainbow')
Graphics object consisting of 23 graphics primitives

Python

>>> from sage.all import *
>>> # needs sage.plot
>>> Word(range(Integer(20))).colored_vector()
Graphics object consisting of 21 graphics primitives
>>> Word(range(Integer(100))).colored_vector(Integer(0),Integer(0),Integer(10),Integer(1))
Graphics object consisting of 101 graphics primitives
>>> Words(range(Integer(100)))(range(Integer(10))).colored_vector()
Graphics object consisting of 11 graphics primitives
>>> w = Word('abbabaab')
>>> w.colored_vector()
Graphics object consisting of 9 graphics primitives
>>> w.colored_vector(cmap='autumn')
Graphics object consisting of 9 graphics primitives
>>> Word(range(Integer(20))).colored_vector(label='Rainbow')
Graphics object consisting of 23 graphics primitives

When two words are defined under the same parent, same letters are mapped to same colors:

Sage

sage: W = Words(range(20))
sage: w = W(range(20))
sage: y = W(range(10,20))
sage: y.colored_vector(y=1, x=10) + w.colored_vector()                      # needs sage.plot
Graphics object consisting of 32 graphics primitives

Python

>>> from sage.all import *
>>> W = Words(range(Integer(20)))
>>> w = W(range(Integer(20)))
>>> y = W(range(Integer(10),Integer(20)))
>>> y.colored_vector(y=Integer(1), x=Integer(10)) + w.colored_vector()                      # needs sage.plot
Graphics object consisting of 32 graphics primitives

commutes_with(other)[source]¶

Return True if self commutes with other, and False otherwise.

EXAMPLES:

Sage

sage: Word('12').commutes_with(Word('12'))
True
sage: Word('12').commutes_with(Word('11'))
False
sage: Word().commutes_with(Word('21'))
True

Python

>>> from sage.all import *
>>> Word('12').commutes_with(Word('12'))
True
>>> Word('12').commutes_with(Word('11'))
False
>>> Word().commutes_with(Word('21'))
True

complete_return_words(fact)[source]¶

Return the set of complete return words of fact in self.

This is the set of all factors starting by the given factor and ending just after the next occurrence of this factor. See for instance [JV2000].

INPUT:

fact – a non-empty finite word

OUTPUT: a Python set of finite words

EXAMPLES:

Sage

sage: s = Word('21331233213231').complete_return_words(Word('2'))
sage: sorted(s)
[word: 2132, word: 213312, word: 2332]
sage: Word('').complete_return_words(Word('213'))
set()
sage: Word('121212').complete_return_words(Word('1212'))
{word: 121212}

Python

>>> from sage.all import *
>>> s = Word('21331233213231').complete_return_words(Word('2'))
>>> sorted(s)
[word: 2132, word: 213312, word: 2332]
>>> Word('').complete_return_words(Word('213'))
set()
>>> Word('121212').complete_return_words(Word('1212'))
{word: 121212}

concatenate(other)[source]¶

Return the concatenation of self and other.

INPUT:

other – a word over the same alphabet as self

EXAMPLES:

Concatenation may be made using + or * operations:

Sage

sage: w = Word('abadafd')
sage: y = Word([5,3,5,8,7])
sage: w * y
word: abadafd53587
sage: w + y
word: abadafd53587
sage: w.concatenate(y)
word: abadafd53587

Python

>>> from sage.all import *
>>> w = Word('abadafd')
>>> y = Word([Integer(5),Integer(3),Integer(5),Integer(8),Integer(7)])
>>> w * y
word: abadafd53587
>>> w + y
word: abadafd53587
>>> w.concatenate(y)
word: abadafd53587

Both words must be defined over the same alphabet:

Sage

sage: z = Word('12223', alphabet = '123')
sage: z + y
Traceback (most recent call last):
...
ValueError: 5 not in alphabet

Python

>>> from sage.all import *
>>> z = Word('12223', alphabet = '123')
>>> z + y
Traceback (most recent call last):
...
ValueError: 5 not in alphabet

Eventually, it should work:

Sage

sage: z = Word('12223', alphabet = '123')
sage: z + y                   #todo: not implemented
word: 1222353587

Python

>>> from sage.all import *
>>> z = Word('12223', alphabet = '123')
>>> z + y                   #todo: not implemented
word: 1222353587

conjugate(pos)[source]¶

Return the conjugate at pos of self.

pos can be any integer, the distance used is the modulo by the length of self.

EXAMPLES:

Sage

sage: Word('12112').conjugate(1)
word: 21121
sage: Word().conjugate(2)
word:
sage: Word('12112').conjugate(8)
word: 12121
sage: Word('12112').conjugate(-1)
word: 21211

Python

>>> from sage.all import *
>>> Word('12112').conjugate(Integer(1))
word: 21121
>>> Word().conjugate(Integer(2))
word:
>>> Word('12112').conjugate(Integer(8))
word: 12121
>>> Word('12112').conjugate(-Integer(1))
word: 21211

conjugate_position(other)[source]¶

Return the position where self is conjugate with other. Return None if there is no such position.

EXAMPLES:

Sage

sage: Word('12113').conjugate_position(Word('31211'))
1
sage: Word('12131').conjugate_position(Word('12113')) is None
True
sage: Word().conjugate_position(Word('123')) is None
True

Python

>>> from sage.all import *
>>> Word('12113').conjugate_position(Word('31211'))
1
>>> Word('12131').conjugate_position(Word('12113')) is None
True
>>> Word().conjugate_position(Word('123')) is None
True

conjugates()[source]¶

Return the list of unique conjugates of self.

EXAMPLES:

Sage

sage: Word(range(6)).conjugates()
[word: 012345,
 word: 123450,
 word: 234501,
 word: 345012,
 word: 450123,
 word: 501234]
sage: Word('cbbca').conjugates()
[word: cbbca, word: bbcac, word: bcacb, word: cacbb, word: acbbc]

Python

>>> from sage.all import *
>>> Word(range(Integer(6))).conjugates()
[word: 012345,
 word: 123450,
 word: 234501,
 word: 345012,
 word: 450123,
 word: 501234]
>>> Word('cbbca').conjugates()
[word: cbbca, word: bbcac, word: bcacb, word: cacbb, word: acbbc]

The result contains each conjugate only once:

Sage

sage: Word('abcabc').conjugates()
[word: abcabc, word: bcabca, word: cabcab]

Python

>>> from sage.all import *
>>> Word('abcabc').conjugates()
[word: abcabc, word: bcabca, word: cabcab]

conjugates_iterator()[source]¶

Return an iterator over the conjugates of self.

EXAMPLES:

Sage

sage: it = Word(range(4)).conjugates_iterator()
sage: for w in it: w
word: 0123
word: 1230
word: 2301
word: 3012

Python

>>> from sage.all import *
>>> it = Word(range(Integer(4))).conjugates_iterator()
>>> for w in it: w
word: 0123
word: 1230
word: 2301
word: 3012

content(n=None)[source]¶

Return content of self.

INPUT:

n – (optional) an integer specifying the maximal letter in the alphabet

OUTPUT: list where the \(i\)-th entry indicates the multiplicity of the \(i\)-th letter in the alphabet in self

EXAMPLES:

Sage

sage: w = Word([1,2,4,3,2,2,2])
sage: w.content()
[1, 4, 1, 1]
sage: w = Word([3,1])
sage: w.content()
[1, 1]
sage: w.content(n=3)
[1, 0, 1]
sage: w = Word([2,4],alphabet=[1,2,3,4])
sage: w.content(n=3)
[0, 1, 0]
sage: w.content()
[0, 1, 0, 1]

Python

>>> from sage.all import *
>>> w = Word([Integer(1),Integer(2),Integer(4),Integer(3),Integer(2),Integer(2),Integer(2)])
>>> w.content()
[1, 4, 1, 1]
>>> w = Word([Integer(3),Integer(1)])
>>> w.content()
[1, 1]
>>> w.content(n=Integer(3))
[1, 0, 1]
>>> w = Word([Integer(2),Integer(4)],alphabet=[Integer(1),Integer(2),Integer(3),Integer(4)])
>>> w.content(n=Integer(3))
[0, 1, 0]
>>> w.content()
[0, 1, 0, 1]

count(letter)[source]¶

Return the number of occurrences of letter in self.

INPUT:

letter – a letter

OUTPUT: integer

EXAMPLES:

Sage

sage: w = Word('abbabaab')
sage: w.number_of_letter_occurrences('a')
4
sage: w.number_of_letter_occurrences('ab')
0

Python

>>> from sage.all import *
>>> w = Word('abbabaab')
>>> w.number_of_letter_occurrences('a')
4
>>> w.number_of_letter_occurrences('ab')
0

This methods is equivalent to list(w).count(letter) and tuple(w).count(letter), thus count is an alias for the method number_of_letter_occurrences:

Sage

sage: list(w).count('a')
4
sage: w.count('a')
4

Python

>>> from sage.all import *
>>> list(w).count('a')
4
>>> w.count('a')
4

But notice that if s and w are strings, Word(s).count(w) counts the number occurrences of w as a letter in Word(s) which is not the same as s.count(w) which counts the number of occurrences of the string w inside s:

Sage

sage: s = 'abbabaab'
sage: s.count('ab')
3
sage: Word(s).count('ab')
0

Python

>>> from sage.all import *
>>> s = 'abbabaab'
>>> s.count('ab')
3
>>> Word(s).count('ab')
0

critical_exponent()[source]¶

Return the critical exponent of self.

The critical exponent of a word is the supremum of the order of all its (finite) factors. See [Dej1972].

Note

The implementation here uses the suffix tree to enumerate all the factors. It should be improved (especially when the critical exponent is larger than 2).

EXAMPLES:

Sage

sage: Word('aaba').critical_exponent()
2
sage: Word('aabaa').critical_exponent()
2
sage: Word('aabaaba').critical_exponent()
7/3
sage: Word('ab').critical_exponent()
1
sage: Word('aba').critical_exponent()
3/2
sage: words.ThueMorseWord()[:20].critical_exponent()
2

Python

>>> from sage.all import *
>>> Word('aaba').critical_exponent()
2
>>> Word('aabaa').critical_exponent()
2
>>> Word('aabaaba').critical_exponent()
7/3
>>> Word('ab').critical_exponent()
1
>>> Word('aba').critical_exponent()
3/2
>>> words.ThueMorseWord()[:Integer(20)].critical_exponent()
2

For the Fibonacci word, the critical exponent is known to be \((5+\sqrt(5))/2\). With a prefix of length 500, we obtain a lower bound:

Sage

sage: words.FibonacciWord()[:500].critical_exponent()
320/89

Python

>>> from sage.all import *
>>> words.FibonacciWord()[:Integer(500)].critical_exponent()
320/89

It is an error to compute the critical exponent of the empty word:

Sage

sage: Word('').critical_exponent()
Traceback (most recent call last):
...
ValueError: no critical exponent for empty word

Python

>>> from sage.all import *
>>> Word('').critical_exponent()
Traceback (most recent call last):
...
ValueError: no critical exponent for empty word

crochemore_factorization()[source]¶

Return the Crochemore factorization of self as an ordered list of factors.

EXAMPLES:

Sage

sage: x = Word('abababb')
sage: x.crochemore_factorization()
(a, b, abab, b)
sage: mul(x.crochemore_factorization()) == x
True
sage: y = Word('abaababacabba')
sage: y.crochemore_factorization()
(a, b, a, aba, ba, c, ab, ba)
sage: mul(y.crochemore_factorization()) == y
True
sage: x = Word([0,1,0,1,0,1,1])
sage: x.crochemore_factorization()
(0, 1, 0101, 1)
sage: mul(x.crochemore_factorization()) == x
True

Python

>>> from sage.all import *
>>> x = Word('abababb')
>>> x.crochemore_factorization()
(a, b, abab, b)
>>> mul(x.crochemore_factorization()) == x
True
>>> y = Word('abaababacabba')
>>> y.crochemore_factorization()
(a, b, a, aba, ba, c, ab, ba)
>>> mul(y.crochemore_factorization()) == y
True
>>> x = Word([Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)])
>>> x.crochemore_factorization()
(0, 1, 0101, 1)
>>> mul(x.crochemore_factorization()) == x
True

defect(f=None)[source]¶

Return the defect of self.

The defect of a finite word \(w\) is given by the difference between the maximum number of possible palindromic factors in a word of length \(|w|\) and the actual number of palindromic factors contained in \(w\). It is well known that the maximum number of palindromic factors in \(w\) is \(|w|+1\) (see [DJP2001]).

An optional involution on letters f can be given. In that case, the f-palindromic defect (or pseudopalindromic defect, or theta-palindromic defect) of \(w\) is returned. It is a generalization of defect to f-palindromes. More precisely, the defect is \(D(w)=|w|+1-g_f(w)-|PAL_f(w)|\), where \(PAL_f(w)\) denotes the set of f-palindromic factors of \(w\) (including the empty word) and \(g_f(w)\) is the number of pairs \(\{a, f(a)\}\) such that \(a\) is a letter, \(a\) is not equal to \(f(a)\), and \(a\) or \(f(a)\) occurs in \(w\). In the case of usual palindromes (i.e., for f not given or equal to the identity), \(g_f(w) = 0\) for all \(w\). See [BHNR2004] for usual palindromes and [Star2011] for f-palindromes.

INPUT:

f – involution (default: None) on the alphabet of self. It must be callable on letters as well as words (e.g. WordMorphism). The default value corresponds to usual palindromes, i.e., f equal to the identity.

OUTPUT:

an integer – If f is None, the palindromic defect of self; otherwise, the f-palindromic defect of self.

EXAMPLES:

Sage

sage: Word('ara').defect()
0
sage: Word('abcacba').defect()
1

Python

>>> from sage.all import *
>>> Word('ara').defect()
0
>>> Word('abcacba').defect()
1

It is known that Sturmian words (see [DJP2001]) have zero defect:

Sage

sage: words.FibonacciWord()[:100].defect()
0

sage: sa = WordMorphism('a->ab,b->b')
sage: sb = WordMorphism('a->a,b->ba')
sage: w = (sa*sb*sb*sa*sa*sa*sb).fixed_point('a')
sage: w[:30].defect()                                                       # needs sage.modules
0
sage: w[110:140].defect()                                                   # needs sage.modules
0

Python

>>> from sage.all import *
>>> words.FibonacciWord()[:Integer(100)].defect()
0

>>> sa = WordMorphism('a->ab,b->b')
>>> sb = WordMorphism('a->a,b->ba')
>>> w = (sa*sb*sb*sa*sa*sa*sb).fixed_point('a')
>>> w[:Integer(30)].defect()                                                       # needs sage.modules
0
>>> w[Integer(110):Integer(140)].defect()                                                   # needs sage.modules
0

It is even conjectured that the defect of an aperiodic word which is a fixed point of a primitive morphism is either \(0\) or infinite (see [BBGL2008]):

Sage

sage: w = words.ThueMorseWord()
sage: w[:50].defect()                                                       # needs sage.modules
12
sage: w[:100].defect()                                                      # needs sage.modules
16
sage: w[:300].defect()                                                      # needs sage.modules
52

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()
>>> w[:Integer(50)].defect()                                                       # needs sage.modules
12
>>> w[:Integer(100)].defect()                                                      # needs sage.modules
16
>>> w[:Integer(300)].defect()                                                      # needs sage.modules
52

For generalized defect with an involution different from the identity, there is always a letter which is not a palindrome! This is the reason for the modification of the definition:

Sage

sage: f = WordMorphism('a->b,b->a')
sage: Word('a').defect(f)
0
sage: Word('ab').defect(f)
0
sage: Word('aa').defect(f)
1
sage: Word('abbabaabbaababba').defect(f)
3

Python

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a')
>>> Word('a').defect(f)
0
>>> Word('ab').defect(f)
0
>>> Word('aa').defect(f)
1
>>> Word('abbabaabbaababba').defect(f)
3

Sage

sage: f = WordMorphism('a->b,b->a,c->c')
sage: Word('cabc').defect(f)
0
sage: Word('abcaab').defect(f)
2

Python

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a,c->c')
>>> Word('cabc').defect(f)
0
>>> Word('abcaab').defect(f)
2

Other examples:

Sage

sage: Word('000000000000').defect()
0
sage: Word('011010011001').defect()
2
sage: Word('0101001010001').defect()
0
sage: Word().defect()
0
sage: Word('abbabaabbaababba').defect()
2

Python

>>> from sage.all import *
>>> Word('000000000000').defect()
0
>>> Word('011010011001').defect()
2
>>> Word('0101001010001').defect()
0
>>> Word().defect()
0
>>> Word('abbabaabbaababba').defect()
2

deg_inv_lex_less(other, weights=None)[source]¶

Return True if the word self is degree inverse lexicographically less than other.

EXAMPLES:

Sage

sage: Word([1,2,4]).deg_inv_lex_less(Word([1,3,2]))
False
sage: Word([3,2,1]).deg_inv_lex_less(Word([1,2,3]))
True

Python

>>> from sage.all import *
>>> Word([Integer(1),Integer(2),Integer(4)]).deg_inv_lex_less(Word([Integer(1),Integer(3),Integer(2)]))
False
>>> Word([Integer(3),Integer(2),Integer(1)]).deg_inv_lex_less(Word([Integer(1),Integer(2),Integer(3)]))
True

deg_lex_less(other, weights=None)[source]¶

Return True if self is degree lexicographically less than other, and False otherwise. The weight of each letter in the ordered alphabet is given by weights, which defaults to [1, 2, 3, ...].

EXAMPLES:

Sage

sage: Word([1,2,3]).deg_lex_less(Word([1,3,2]))
True
sage: Word([3,2,1]).deg_lex_less(Word([1,2,3]))
False
sage: W = Words(range(5))
sage: W([1,2,4]).deg_lex_less(W([1,3,2]))
False
sage: Word("abba").deg_lex_less(Word("abbb"), dict(a=1,b=2))
True
sage: Word("abba").deg_lex_less(Word("baba"), dict(a=1,b=2))
True
sage: Word("abba").deg_lex_less(Word("aaba"), dict(a=1,b=2))
False
sage: Word("abba").deg_lex_less(Word("aaba"), dict(a=1,b=0))
True

Python

>>> from sage.all import *
>>> Word([Integer(1),Integer(2),Integer(3)]).deg_lex_less(Word([Integer(1),Integer(3),Integer(2)]))
True
>>> Word([Integer(3),Integer(2),Integer(1)]).deg_lex_less(Word([Integer(1),Integer(2),Integer(3)]))
False
>>> W = Words(range(Integer(5)))
>>> W([Integer(1),Integer(2),Integer(4)]).deg_lex_less(W([Integer(1),Integer(3),Integer(2)]))
False
>>> Word("abba").deg_lex_less(Word("abbb"), dict(a=Integer(1),b=Integer(2)))
True
>>> Word("abba").deg_lex_less(Word("baba"), dict(a=Integer(1),b=Integer(2)))
True
>>> Word("abba").deg_lex_less(Word("aaba"), dict(a=Integer(1),b=Integer(2)))
False
>>> Word("abba").deg_lex_less(Word("aaba"), dict(a=Integer(1),b=Integer(0)))
True

deg_rev_lex_less(other, weights=None)[source]¶

Return True if self is degree reverse lexicographically less than other.

EXAMPLES:

Sage

sage: Word([3,2,1]).deg_rev_lex_less(Word([1,2,3]))
False
sage: Word([1,2,4]).deg_rev_lex_less(Word([1,3,2]))
False
sage: Word([1,2,3]).deg_rev_lex_less(Word([1,2,4]))
True

Python

>>> from sage.all import *
>>> Word([Integer(3),Integer(2),Integer(1)]).deg_rev_lex_less(Word([Integer(1),Integer(2),Integer(3)]))
False
>>> Word([Integer(1),Integer(2),Integer(4)]).deg_rev_lex_less(Word([Integer(1),Integer(3),Integer(2)]))
False
>>> Word([Integer(1),Integer(2),Integer(3)]).deg_rev_lex_less(Word([Integer(1),Integer(2),Integer(4)]))
True

degree(weights=None)[source]¶

Return the weighted degree of self, where the weighted degree of each letter in the ordered alphabet is given by weights, which defaults to [1, 2, 3, ...].

INPUT:

weights – list or tuple, or dictionary keyed by the letters occurring in self

EXAMPLES:

Sage

sage: Word([1,2,3]).degree()
6
sage: Word([3,2,1]).degree()
6
sage: Words("ab")("abba").degree()
6
sage: Words("ab")("abba").degree([0,2])
4
sage: Words("ab")("abba").degree([-1,-1])
-4
sage: Words("ab")("aabba").degree([1,1])
5
sage: Words([1,2,4])([1,2,4]).degree()
6
sage: Word([1,2,4]).degree()
7
sage: Word("aabba").degree({'a':1,'b':2})
7
sage: Word([0,1,0]).degree({0:17,1:0})
34

Python

>>> from sage.all import *
>>> Word([Integer(1),Integer(2),Integer(3)]).degree()
6
>>> Word([Integer(3),Integer(2),Integer(1)]).degree()
6
>>> Words("ab")("abba").degree()
6
>>> Words("ab")("abba").degree([Integer(0),Integer(2)])
4
>>> Words("ab")("abba").degree([-Integer(1),-Integer(1)])
-4
>>> Words("ab")("aabba").degree([Integer(1),Integer(1)])
5
>>> Words([Integer(1),Integer(2),Integer(4)])([Integer(1),Integer(2),Integer(4)]).degree()
6
>>> Word([Integer(1),Integer(2),Integer(4)]).degree()
7
>>> Word("aabba").degree({'a':Integer(1),'b':Integer(2)})
7
>>> Word([Integer(0),Integer(1),Integer(0)]).degree({Integer(0):Integer(17),Integer(1):Integer(0)})
34

delta()[source]¶

Return the image of self under the delta morphism.

The delta morphism, also known as the run-length encoding, is the word composed of the length of consecutive runs of the same letter in a given word.

EXAMPLES:

Sage

sage: W = Words('0123456789')
sage: W('22112122').delta()
word: 22112
sage: W('555008').delta()
word: 321
sage: W().delta()
word:
sage: Word('aabbabaa').delta()
word: 22112

Python

>>> from sage.all import *
>>> W = Words('0123456789')
>>> W('22112122').delta()
word: 22112
>>> W('555008').delta()
word: 321
>>> W().delta()
word:
>>> Word('aabbabaa').delta()
word: 22112

delta_derivate(W=None)[source]¶

Return the derivative under delta for self.

EXAMPLES:

Sage

sage: W = Words('12')
sage: W('12211').delta_derivate()
word: 22
sage: W('1').delta_derivate(Words([1]))
word: 1
sage: W('2112').delta_derivate()
word: 2
sage: W('2211').delta_derivate()
word: 22
sage: W('112').delta_derivate()
word: 2
sage: W('11222').delta_derivate(Words([1, 2, 3]))
word: 3

Python

>>> from sage.all import *
>>> W = Words('12')
>>> W('12211').delta_derivate()
word: 22
>>> W('1').delta_derivate(Words([Integer(1)]))
word: 1
>>> W('2112').delta_derivate()
word: 2
>>> W('2211').delta_derivate()
word: 22
>>> W('112').delta_derivate()
word: 2
>>> W('11222').delta_derivate(Words([Integer(1), Integer(2), Integer(3)]))
word: 3

delta_derivate_left(W=None)[source]¶

Return the derivative under delta for self.

EXAMPLES:

Sage

sage: W = Words('12')
sage: W('12211').delta_derivate_left()
word: 22
sage: W('1').delta_derivate_left(Words([1]))
word: 1
sage: W('2112').delta_derivate_left()
word: 21
sage: W('2211').delta_derivate_left()
word: 22
sage: W('112').delta_derivate_left()
word: 21
sage: W('11222').delta_derivate_left(Words([1, 2, 3]))
word: 3

Python

>>> from sage.all import *
>>> W = Words('12')
>>> W('12211').delta_derivate_left()
word: 22
>>> W('1').delta_derivate_left(Words([Integer(1)]))
word: 1
>>> W('2112').delta_derivate_left()
word: 21
>>> W('2211').delta_derivate_left()
word: 22
>>> W('112').delta_derivate_left()
word: 21
>>> W('11222').delta_derivate_left(Words([Integer(1), Integer(2), Integer(3)]))
word: 3

delta_derivate_right(W=None)[source]¶

Return the right derivative under delta for self.

EXAMPLES:

Sage

sage: W = Words('12')
sage: W('12211').delta_derivate_right()
word: 122
sage: W('1').delta_derivate_right(Words([1]))
word: 1
sage: W('2112').delta_derivate_right()
word: 12
sage: W('2211').delta_derivate_right()
word: 22
sage: W('112').delta_derivate_right()
word: 2
sage: W('11222').delta_derivate_right(Words([1, 2, 3]))
word: 23

Python

>>> from sage.all import *
>>> W = Words('12')
>>> W('12211').delta_derivate_right()
word: 122
>>> W('1').delta_derivate_right(Words([Integer(1)]))
word: 1
>>> W('2112').delta_derivate_right()
word: 12
>>> W('2211').delta_derivate_right()
word: 22
>>> W('112').delta_derivate_right()
word: 2
>>> W('11222').delta_derivate_right(Words([Integer(1), Integer(2), Integer(3)]))
word: 23

delta_inv(W=None, s=None)[source]¶

Lift self via the delta operator to obtain a word containing the letters in alphabet (default: [0, 1]). The letters used in the construction start with s (default: alphabet[0]) and cycle through alphabet.

INPUT:

alphabet – an iterable
s – an object in the iterable

EXAMPLES:

Sage

sage: W = Words([1, 2])
sage: W([2, 2, 1, 1]).delta_inv()
word: 112212
sage: W([1, 1, 1, 1]).delta_inv(Words('123'))
word: 1231
sage: W([2, 2, 1, 1, 2]).delta_inv(s=2)
word: 22112122

Python

>>> from sage.all import *
>>> W = Words([Integer(1), Integer(2)])
>>> W([Integer(2), Integer(2), Integer(1), Integer(1)]).delta_inv()
word: 112212
>>> W([Integer(1), Integer(1), Integer(1), Integer(1)]).delta_inv(Words('123'))
word: 1231
>>> W([Integer(2), Integer(2), Integer(1), Integer(1), Integer(2)]).delta_inv(s=Integer(2))
word: 22112122

evaluation()[source]¶

Return the abelian vector of self counting the occurrences of each letter.

The vector is defined w.r.t. the order of the alphabet of the parent. See also evaluation_dict().

INPUT:

self – word having a parent on a finite alphabet

OUTPUT: list

EXAMPLES:

Sage

sage: W = Words('ab')
sage: W('aaabbbbb').abelian_vector()
[3, 5]
sage: W('a').abelian_vector()
[1, 0]
sage: W().abelian_vector()
[0, 0]

Python

>>> from sage.all import *
>>> W = Words('ab')
>>> W('aaabbbbb').abelian_vector()
[3, 5]
>>> W('a').abelian_vector()
[1, 0]
>>> W().abelian_vector()
[0, 0]

The result depends on the alphabet of the parent:

Sage

sage: W = Words('abc')
sage: W('aabaa').abelian_vector()
[4, 1, 0]

Python

>>> from sage.all import *
>>> W = Words('abc')
>>> W('aabaa').abelian_vector()
[4, 1, 0]

evaluation_dict()[source]¶

Return a dictionary keyed by the letters occurring in self with values the number of occurrences of the letter.

EXAMPLES:

Sage

sage: Word([2,1,4,2,3,4,2]).evaluation_dict()
{1: 1, 2: 3, 3: 1, 4: 2}
sage: Word('badbcdb').evaluation_dict()
{'a': 1, 'b': 3, 'c': 1, 'd': 2}
sage: Word().evaluation_dict()
{}

Python

>>> from sage.all import *
>>> Word([Integer(2),Integer(1),Integer(4),Integer(2),Integer(3),Integer(4),Integer(2)]).evaluation_dict()
{1: 1, 2: 3, 3: 1, 4: 2}
>>> Word('badbcdb').evaluation_dict()
{'a': 1, 'b': 3, 'c': 1, 'd': 2}
>>> Word().evaluation_dict()
{}

Sage

sage: f = Word('1213121').evaluation_dict() # keys appear in random order
{'1': 4, '2': 2, '3': 1}

Python

>>> from sage.all import *
>>> f = Word('1213121').evaluation_dict() # keys appear in random order
{'1': 4, '2': 2, '3': 1}

evaluation_partition()[source]¶

Return the evaluation of the word w as a partition.

EXAMPLES:

Sage

sage: Word("acdabda").evaluation_partition()
[3, 2, 1, 1]
sage: Word([2,1,4,2,3,4,2]).evaluation_partition()
[3, 2, 1, 1]

Python

>>> from sage.all import *
>>> Word("acdabda").evaluation_partition()
[3, 2, 1, 1]
>>> Word([Integer(2),Integer(1),Integer(4),Integer(2),Integer(3),Integer(4),Integer(2)]).evaluation_partition()
[3, 2, 1, 1]

evaluation_sparse()[source]¶

Return a list representing the evaluation of self. The entries of the list are two-element lists [a, n], where a is a letter occurring in self and n is the number of occurrences of a in self.

EXAMPLES:

Sage

sage: sorted(Word([4,4,2,5,2,1,4,1]).evaluation_sparse())
[(1, 2), (2, 2), (4, 3), (5, 1)]
sage: sorted(Word("abcaccab").evaluation_sparse())
[('a', 3), ('b', 2), ('c', 3)]

Python

>>> from sage.all import *
>>> sorted(Word([Integer(4),Integer(4),Integer(2),Integer(5),Integer(2),Integer(1),Integer(4),Integer(1)]).evaluation_sparse())
[(1, 2), (2, 2), (4, 3), (5, 1)]
>>> sorted(Word("abcaccab").evaluation_sparse())
[('a', 3), ('b', 2), ('c', 3)]

exponent()[source]¶

Return the exponent of self.

OUTPUT: integer; the exponent

EXAMPLES:

Sage

sage: Word('1231').exponent()
1
sage: Word('121212').exponent()
3
sage: Word().exponent()
0

Python

>>> from sage.all import *
>>> Word('1231').exponent()
1
>>> Word('121212').exponent()
3
>>> Word().exponent()
0

factor_complexity(n)[source]¶

Return the number of distinct factors of length n of self.

INPUT:

n – the length of the factors

EXAMPLES:

Sage

sage: w = words.FibonacciWord()[:100]
sage: [w.factor_complexity(i) for i in range(20)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Python

>>> from sage.all import *
>>> w = words.FibonacciWord()[:Integer(100)]
>>> [w.factor_complexity(i) for i in range(Integer(20))]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Sage

sage: w = words.ThueMorseWord()[:1000]
sage: [w.factor_complexity(i) for i in range(20)]
[1, 2, 4, 6, 10, 12, 16, 20, 22, 24, 28, 32, 36, 40, 42, 44, 46, 48, 52, 56]

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()[:Integer(1000)]
>>> [w.factor_complexity(i) for i in range(Integer(20))]
[1, 2, 4, 6, 10, 12, 16, 20, 22, 24, 28, 32, 36, 40, 42, 44, 46, 48, 52, 56]

factor_iterator(n=None)[source]¶

Generate distinct factors of self.

INPUT:

n – integer or None

OUTPUT:

If n is an integer, returns an iterator over all distinct factors of length n. If n is None, returns an iterator generating all distinct factors.

EXAMPLES:

Sage

sage: w = Word('1213121')
sage: sorted( w.factor_iterator(0) )
[word: ]
sage: sorted( w.factor_iterator(10) )
[]
sage: sorted( w.factor_iterator(1) )
[word: 1, word: 2, word: 3]
sage: sorted( w.factor_iterator(4) )
[word: 1213, word: 1312, word: 2131, word: 3121]
sage: sorted( w.factor_iterator() )
[word: , word: 1, word: 12, word: 121, word: 1213, word: 12131, word: 121312, word: 1213121, word: 13, word: 131, word: 1312, word: 13121, word: 2, word: 21, word: 213, word: 2131, word: 21312, word: 213121, word: 3, word: 31, word: 312, word: 3121]

Python

>>> from sage.all import *
>>> w = Word('1213121')
>>> sorted( w.factor_iterator(Integer(0)) )
[word: ]
>>> sorted( w.factor_iterator(Integer(10)) )
[]
>>> sorted( w.factor_iterator(Integer(1)) )
[word: 1, word: 2, word: 3]
>>> sorted( w.factor_iterator(Integer(4)) )
[word: 1213, word: 1312, word: 2131, word: 3121]
>>> sorted( w.factor_iterator() )
[word: , word: 1, word: 12, word: 121, word: 1213, word: 12131, word: 121312, word: 1213121, word: 13, word: 131, word: 1312, word: 13121, word: 2, word: 21, word: 213, word: 2131, word: 21312, word: 213121, word: 3, word: 31, word: 312, word: 3121]

Sage

sage: u = Word([1,2,1,2,3])
sage: sorted( u.factor_iterator(0) )
[word: ]
sage: sorted( u.factor_iterator(10) )
[]
sage: sorted( u.factor_iterator(1) )
[word: 1, word: 2, word: 3]
sage: sorted( u.factor_iterator(5) )
[word: 12123]
sage: sorted( u.factor_iterator() )
[word: , word: 1, word: 12, word: 121, word: 1212, word: 12123, word: 123, word: 2, word: 21, word: 212, word: 2123, word: 23, word: 3]

Python

>>> from sage.all import *
>>> u = Word([Integer(1),Integer(2),Integer(1),Integer(2),Integer(3)])
>>> sorted( u.factor_iterator(Integer(0)) )
[word: ]
>>> sorted( u.factor_iterator(Integer(10)) )
[]
>>> sorted( u.factor_iterator(Integer(1)) )
[word: 1, word: 2, word: 3]
>>> sorted( u.factor_iterator(Integer(5)) )
[word: 12123]
>>> sorted( u.factor_iterator() )
[word: , word: 1, word: 12, word: 121, word: 1212, word: 12123, word: 123, word: 2, word: 21, word: 212, word: 2123, word: 23, word: 3]

Sage

sage: xxx = Word("xxx")
sage: sorted( xxx.factor_iterator(0) )
[word: ]
sage: sorted( xxx.factor_iterator(4) )
[]
sage: sorted( xxx.factor_iterator(2) )
[word: xx]
sage: sorted( xxx.factor_iterator() )
[word: , word: x, word: xx, word: xxx]

Python

>>> from sage.all import *
>>> xxx = Word("xxx")
>>> sorted( xxx.factor_iterator(Integer(0)) )
[word: ]
>>> sorted( xxx.factor_iterator(Integer(4)) )
[]
>>> sorted( xxx.factor_iterator(Integer(2)) )
[word: xx]
>>> sorted( xxx.factor_iterator() )
[word: , word: x, word: xx, word: xxx]

Sage

sage: e = Word()
sage: sorted( e.factor_iterator(0) )
[word: ]
sage: sorted( e.factor_iterator(17) )
[]
sage: sorted( e.factor_iterator() )
[word: ]

Python

>>> from sage.all import *
>>> e = Word()
>>> sorted( e.factor_iterator(Integer(0)) )
[word: ]
>>> sorted( e.factor_iterator(Integer(17)) )
[]
>>> sorted( e.factor_iterator() )
[word: ]

factor_occurrences_in(other)[source]¶

Return an iterator over all occurrences (including overlapping ones) of self in other in their order of appearance.

Warning

This method is deprecated since 2020 and will be removed in a later version of SageMath. Use factor_occurrences_iterator() instead.

EXAMPLES:

Sage

sage: u = Word('121')
sage: w = Word('121213211213')
sage: list(u.factor_occurrences_in(w))
doctest:warning
...
DeprecationWarning: f.factor_occurrences_in(w) is deprecated.
Use w.factor_occurrences_iterator(f) instead.
See https://github.com/sagemath/sage/issues/30187 for details.
[0, 2, 8]

Python

>>> from sage.all import *
>>> u = Word('121')
>>> w = Word('121213211213')
>>> list(u.factor_occurrences_in(w))
doctest:warning
...
DeprecationWarning: f.factor_occurrences_in(w) is deprecated.
Use w.factor_occurrences_iterator(f) instead.
See https://github.com/sagemath/sage/issues/30187 for details.
[0, 2, 8]

factor_set(n=None, algorithm='suffix tree')[source]¶

Return the set of factors (of length n) of self.

INPUT:

n – integer or None (default: None)
algorithm – string (default: 'suffix tree'), takes the following values:
- 'suffix tree' – construct and use the suffix tree of the word
- 'naive' – algorithm uses a sliding window

OUTPUT:

If n is an integer, returns the set of all distinct factors of length n. If n is None, returns the set of all distinct factors.

EXAMPLES:

Sage

sage: w = Word('121')
sage: sorted(w.factor_set())
[word: , word: 1, word: 12, word: 121, word: 2, word: 21]
sage: sorted(w.factor_set(algorithm='naive'))
[word: , word: 1, word: 12, word: 121, word: 2, word: 21]

Python

>>> from sage.all import *
>>> w = Word('121')
>>> sorted(w.factor_set())
[word: , word: 1, word: 12, word: 121, word: 2, word: 21]
>>> sorted(w.factor_set(algorithm='naive'))
[word: , word: 1, word: 12, word: 121, word: 2, word: 21]

Sage

sage: w = Word('1213121')
sage: for i in range(w.length()): sorted(w.factor_set(i))
[word: ]
[word: 1, word: 2, word: 3]
[word: 12, word: 13, word: 21, word: 31]
[word: 121, word: 131, word: 213, word: 312]
[word: 1213, word: 1312, word: 2131, word: 3121]
[word: 12131, word: 13121, word: 21312]
[word: 121312, word: 213121]

Python

>>> from sage.all import *
>>> w = Word('1213121')
>>> for i in range(w.length()): sorted(w.factor_set(i))
[word: ]
[word: 1, word: 2, word: 3]
[word: 12, word: 13, word: 21, word: 31]
[word: 121, word: 131, word: 213, word: 312]
[word: 1213, word: 1312, word: 2131, word: 3121]
[word: 12131, word: 13121, word: 21312]
[word: 121312, word: 213121]

Sage

sage: w = Word([1,2,1,2,3])
sage: s = w.factor_set()
sage: sorted(s)
[word: , word: 1, word: 12, word: 121, word: 1212, word: 12123, word: 123, word: 2, word: 21, word: 212, word: 2123, word: 23, word: 3]

Python

>>> from sage.all import *
>>> w = Word([Integer(1),Integer(2),Integer(1),Integer(2),Integer(3)])
>>> s = w.factor_set()
>>> sorted(s)
[word: , word: 1, word: 12, word: 121, word: 1212, word: 12123, word: 123, word: 2, word: 21, word: 212, word: 2123, word: 23, word: 3]

find(sub, start=0, end=None)[source]¶

Return the index of the first occurrence of sub in self, such that sub is contained within self[start:end]. Return \(-1\) on failure.

INPUT:

sub – string, list, tuple or word to search for
start – nonnegative integer (default: \(0\)) specifying the position from which to start the search
end – nonnegative integer (default: None); specifying the position at which the search must stop. If None, then the search is performed up to the end of the string.

OUTPUT: nonnegative integer or \(-1\)

EXAMPLES:

Sage

sage: w = Word([0,1,0,0,1])
sage: w.find(Word([1,0]))
1

Python

>>> from sage.all import *
>>> w = Word([Integer(0),Integer(1),Integer(0),Integer(0),Integer(1)])
>>> w.find(Word([Integer(1),Integer(0)]))
1

The sub argument can also be a tuple or a list:

Sage

sage: w.find([1,0])
1
sage: w.find((1,0))
1

Python

>>> from sage.all import *
>>> w.find([Integer(1),Integer(0)])
1
>>> w.find((Integer(1),Integer(0)))
1

Examples using start and end:

Sage

sage: w.find(Word([0,1]), start=1)
3
sage: w.find(Word([0,1]), start=1, end=5)
3
sage: w.find(Word([0,1]), start=1, end=4) == -1
True
sage: w.find(Word([1,1])) == -1
True
sage: w.find("aa")
-1

Python

>>> from sage.all import *
>>> w.find(Word([Integer(0),Integer(1)]), start=Integer(1))
3
>>> w.find(Word([Integer(0),Integer(1)]), start=Integer(1), end=Integer(5))
3
>>> w.find(Word([Integer(0),Integer(1)]), start=Integer(1), end=Integer(4)) == -Integer(1)
True
>>> w.find(Word([Integer(1),Integer(1)])) == -Integer(1)
True
>>> w.find("aa")
-1

Instances of Word_str handle string inputs as well:

Sage

sage: w = Word('abac')
sage: w.find('a')
0
sage: w.find('ba')
1

Python

>>> from sage.all import *
>>> w = Word('abac')
>>> w.find('a')
0
>>> w.find('ba')
1

first_pos_in(other)[source]¶

Return the position of the first occurrence of self in other, or None if self is not a factor of other.

Warning

This method is deprecated since 2020 and will be removed in a later version of SageMath. Use first_occurrence() instead.

EXAMPLES:

Sage

sage: Word('12').first_pos_in(Word('131231'))
doctest:warning
...
DeprecationWarning: f.first_pos_in(w) is deprecated.
Use w.first_occurrence(f) instead.
See https://github.com/sagemath/sage/issues/30187 for details.
2
sage: Word('32').first_pos_in(Word('131231')) is None
True

Python

>>> from sage.all import *
>>> Word('12').first_pos_in(Word('131231'))
doctest:warning
...
DeprecationWarning: f.first_pos_in(w) is deprecated.
Use w.first_occurrence(f) instead.
See https://github.com/sagemath/sage/issues/30187 for details.
2
>>> Word('32').first_pos_in(Word('131231')) is None
True

foata_bijection()[source]¶

Return word self under the Foata bijection.

The Foata bijection \(\phi\) is a bijection on the set of words of given content (by a slight generalization of Section 2 in [FS1978]). It can be defined by induction on the size of the word: Given a word \(w_1 w_2 \cdots w_n\), start with \(\phi(w_1) = w_1\). At the \(i\)-th step, if \(\phi(w_1 w_2 \cdots w_i) = v_1 v_2 \cdots v_i\), we define \(\phi(w_1 w_2 \cdots w_i w_{i+1})\) by placing \(w_{i+1}\) on the end of the word \(v_1 v_2 \cdots v_i\) and breaking the word up into blocks as follows. If \(w_{i+1} \ge v_i\), place a vertical line to the right of each \(v_k\) for which \(w_{i+1} \ge v_k\). Otherwise, if \(w_{i+1} < v_i\), place a vertical line to the right of each \(v_k\) for which \(w_{i+1} < v_k\). In either case, place a vertical line at the start of the word as well. Now, within each block between vertical lines, cyclically shift the entries one place to the right.

For instance, to compute \(\phi([4,1,5,4,2,2,3])\), the sequence of words is

\(4\),
\(|4|1 \to 41\),
\(|4|1|5 \to 415\),
\(|415|4 \to 5414\),
\(|5|4|14|2 \to 54412\),
\(|5441|2|2 \to 154422\),
\(|1|5442|2|3 \to 1254423\).

So \(\phi([4,1,5,4,2,2,3]) = [1,2,5,4,4,2,3]\).

See also

Foata bijection on Permutations.

EXAMPLES:

Sage

sage: w = Word([2,2,2,1,1,1])
sage: w.foata_bijection()
word: 112221
sage: w = Word([2,2,1,2,2,2,1,1,2,1])
sage: w.foata_bijection()
word: 2122212211
sage: w = Word([4,1,5,4,2,2,3])
sage: w.foata_bijection()
word: 1254423

Python

>>> from sage.all import *
>>> w = Word([Integer(2),Integer(2),Integer(2),Integer(1),Integer(1),Integer(1)])
>>> w.foata_bijection()
word: 112221
>>> w = Word([Integer(2),Integer(2),Integer(1),Integer(2),Integer(2),Integer(2),Integer(1),Integer(1),Integer(2),Integer(1)])
>>> w.foata_bijection()
word: 2122212211
>>> w = Word([Integer(4),Integer(1),Integer(5),Integer(4),Integer(2),Integer(2),Integer(3)])
>>> w.foata_bijection()
word: 1254423

good_suffix_table()[source]¶

Return a table of the maximum skip you can do in order not to miss a possible occurrence of self in a word.

This is a part of the Boyer-Moore algorithm to find factors. See [BM1977].

EXAMPLES:

Sage

sage: Word('121321').good_suffix_table()
[5, 5, 5, 5, 3, 3, 1]
sage: Word('12412').good_suffix_table()
[3, 3, 3, 3, 3, 1]

Python

>>> from sage.all import *
>>> Word('121321').good_suffix_table()
[5, 5, 5, 5, 3, 3, 1]
>>> Word('12412').good_suffix_table()
[3, 3, 3, 3, 3, 1]

has_period(p)[source]¶

Return True if self has the period \(p\), False otherwise.

Note

By convention, integers greater than the length of self are periods of self.

INPUT:

p – integer to check if it is a period of self

EXAMPLES:

Sage

sage: w = Word('ababa')
sage: w.has_period(2)
True
sage: w.has_period(3)
False
sage: w.has_period(4)
True
sage: w.has_period(-1)
False
sage: w.has_period(5)
True
sage: w.has_period(6)
True

Python

>>> from sage.all import *
>>> w = Word('ababa')
>>> w.has_period(Integer(2))
True
>>> w.has_period(Integer(3))
False
>>> w.has_period(Integer(4))
True
>>> w.has_period(-Integer(1))
False
>>> w.has_period(Integer(5))
True
>>> w.has_period(Integer(6))
True

has_prefix(other)[source]¶

Test whether self has other as a prefix.

INPUT:

other – a word, or data describing a word

OUTPUT: boolean

EXAMPLES:

Sage

sage: w = Word("abbabaabababa")
sage: u = Word("abbab")
sage: w.has_prefix(u)
True
sage: u.has_prefix(w)
False
sage: u.has_prefix("abbab")
True

Python

>>> from sage.all import *
>>> w = Word("abbabaabababa")
>>> u = Word("abbab")
>>> w.has_prefix(u)
True
>>> u.has_prefix(w)
False
>>> u.has_prefix("abbab")
True

Sage

sage: w = Word([0,1,1,0,1,0,0,1,0,1,0,1,0])
sage: u = Word([0,1,1,0,1])
sage: w.has_prefix(u)
True
sage: u.has_prefix(w)
False
sage: u.has_prefix([0,1,1,0,1])
True

Python

>>> from sage.all import *
>>> w = Word([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)])
>>> u = Word([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1)])
>>> w.has_prefix(u)
True
>>> u.has_prefix(w)
False
>>> u.has_prefix([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1)])
True

has_suffix(other)[source]¶

Test whether self has other as a suffix.

Note

Some word datatype classes, like WordDatatype_str, override this method.

INPUT:

other – a word, or data describing a word

OUTPUT: boolean

EXAMPLES:

Sage

sage: w = Word("abbabaabababa")
sage: u = Word("ababa")
sage: w.has_suffix(u)
True
sage: u.has_suffix(w)
False
sage: u.has_suffix("ababa")
True

Python

>>> from sage.all import *
>>> w = Word("abbabaabababa")
>>> u = Word("ababa")
>>> w.has_suffix(u)
True
>>> u.has_suffix(w)
False
>>> u.has_suffix("ababa")
True

Sage

sage: w = Word([0,1,1,0,1,0,0,1,0,1,0,1,0])
sage: u = Word([0,1,0,1,0])
sage: w.has_suffix(u)
True
sage: u.has_suffix(w)
False
sage: u.has_suffix([0,1,0,1,0])
True

Python

>>> from sage.all import *
>>> w = Word([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)])
>>> u = Word([Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)])
>>> w.has_suffix(u)
True
>>> u.has_suffix(w)
False
>>> u.has_suffix([Integer(0),Integer(1),Integer(0),Integer(1),Integer(0)])
True

implicit_suffix_tree()[source]¶

Return the implicit suffix tree of self.

The suffix tree of a word \(w\) is a compactification of the suffix trie for \(w\). The compactification removes all nodes that have exactly one incoming edge and exactly one outgoing edge. It consists of two components: a tree and a word. Thus, instead of labelling the edges by factors of \(w\), we can label them by indices of the occurrence of the factors in \(w\).

Type sage.combinat.words.suffix_trees.ImplicitSuffixTree? for more information.

EXAMPLES:

Sage

sage: w = Word("cacao")
sage: w.implicit_suffix_tree()
Implicit Suffix Tree of the word: cacao

Python

>>> from sage.all import *
>>> w = Word("cacao")
>>> w.implicit_suffix_tree()
Implicit Suffix Tree of the word: cacao

Sage

sage: w = Word([0,1,0,1,1])
sage: w.implicit_suffix_tree()
Implicit Suffix Tree of the word: 01011

Python

>>> from sage.all import *
>>> w = Word([Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)])
>>> w.implicit_suffix_tree()
Implicit Suffix Tree of the word: 01011

inv_lex_less(other)[source]¶

Return True if self is inverse lexicographically less than other.

EXAMPLES:

Sage

sage: Word([1,2,4]).inv_lex_less(Word([1,3,2]))
False
sage: Word([3,2,1]).inv_lex_less(Word([1,2,3]))
True

Python

>>> from sage.all import *
>>> Word([Integer(1),Integer(2),Integer(4)]).inv_lex_less(Word([Integer(1),Integer(3),Integer(2)]))
False
>>> Word([Integer(3),Integer(2),Integer(1)]).inv_lex_less(Word([Integer(1),Integer(2),Integer(3)]))
True

inversions()[source]¶

Return a list of the inversions of self. An inversion is a pair \((i,j)\) of nonnegative integers \(i < j\) such that self[i] > self[j].

EXAMPLES:

Sage

sage: Word([1,2,3,2,2,1]).inversions()
[[1, 5], [2, 3], [2, 4], [2, 5], [3, 5], [4, 5]]
sage: Words([3,2,1])([1,2,3,2,2,1]).inversions()
[[0, 1], [0, 2], [0, 3], [0, 4], [1, 2]]
sage: Word('abbaba').inversions()
[[1, 3], [1, 5], [2, 3], [2, 5], [4, 5]]
sage: Words('ba')('abbaba').inversions()
[[0, 1], [0, 2], [0, 4], [3, 4]]

Python

>>> from sage.all import *
>>> Word([Integer(1),Integer(2),Integer(3),Integer(2),Integer(2),Integer(1)]).inversions()
[[1, 5], [2, 3], [2, 4], [2, 5], [3, 5], [4, 5]]
>>> Words([Integer(3),Integer(2),Integer(1)])([Integer(1),Integer(2),Integer(3),Integer(2),Integer(2),Integer(1)]).inversions()
[[0, 1], [0, 2], [0, 3], [0, 4], [1, 2]]
>>> Word('abbaba').inversions()
[[1, 3], [1, 5], [2, 3], [2, 5], [4, 5]]
>>> Words('ba')('abbaba').inversions()
[[0, 1], [0, 2], [0, 4], [3, 4]]

is_balanced(q=1)[source]¶

Return True if self is q-balanced, and False otherwise.

INPUT:

q – integer (default: \(1\)); the balance level

EXAMPLES:

Sage

sage: Word('1213121').is_balanced()
True
sage: Word('1122').is_balanced()
False
sage: Word('121333121').is_balanced()
False
sage: Word('121333121').is_balanced(2)
False
sage: Word('121333121').is_balanced(3)
True
sage: Word('121122121').is_balanced()
False
sage: Word('121122121').is_balanced(2)
True

Python

>>> from sage.all import *
>>> Word('1213121').is_balanced()
True
>>> Word('1122').is_balanced()
False
>>> Word('121333121').is_balanced()
False
>>> Word('121333121').is_balanced(Integer(2))
False
>>> Word('121333121').is_balanced(Integer(3))
True
>>> Word('121122121').is_balanced()
False
>>> Word('121122121').is_balanced(Integer(2))
True

is_cadence(seq)[source]¶

Return True if seq is a cadence of self, and False otherwise.

A cadence is an increasing sequence of indexes that all map to the same letter.

EXAMPLES:

Sage

sage: Word('121132123').is_cadence([0, 2, 6])
True
sage: Word('121132123').is_cadence([0, 1, 2])
False
sage: Word('121132123').is_cadence([])
True

Python

>>> from sage.all import *
>>> Word('121132123').is_cadence([Integer(0), Integer(2), Integer(6)])
True
>>> Word('121132123').is_cadence([Integer(0), Integer(1), Integer(2)])
False
>>> Word('121132123').is_cadence([])
True

is_christoffel()[source]¶

Return True if self is a Christoffel word, and False otherwise.

The Christoffel word of slope \(p/q\) is obtained from the Cayley graph of \(\ZZ/(p+q)\ZZ\) with generator \(q\) as follows. If \(u \rightarrow v\) is an edge in the Cayley graph, then, \(v = u + p \mod{p+q}\). Let \(a\),`b` be the alphabet of \(w\). Label the edge \(u \rightarrow v\) by \(a\) if \(u < v\) and \(b\) otherwise. The Christoffel word is the word obtained by reading the edge labels along the cycle beginning from \(0\).

Equivalently, \(w\) is a Christoffel word iff \(w\) is a symmetric non-empty word and \(w[1:n-1]\) is a palindrome.

See for instance [Ber2007] and [BLRS2009].

INPUT:

self – word

OUTPUT: boolean; True if self is a Christoffel word, False otherwise

EXAMPLES:

Sage

sage: Word('00100101').is_christoffel()
True
sage: Word('aab').is_christoffel()
True
sage: Word().is_christoffel()
False
sage: Word('123123123').is_christoffel()
False
sage: Word('00100').is_christoffel()
False
sage: Word('0').is_christoffel()
True

Python

>>> from sage.all import *
>>> Word('00100101').is_christoffel()
True
>>> Word('aab').is_christoffel()
True
>>> Word().is_christoffel()
False
>>> Word('123123123').is_christoffel()
False
>>> Word('00100').is_christoffel()
False
>>> Word('0').is_christoffel()
True

is_conjugate_with(other)[source]¶

Return True if self is a conjugate of other, and False otherwise.

INPUT:

other – a finite word

OUTPUT: boolean

EXAMPLES:

Sage

sage: w = Word([0..20])
sage: z = Word([7..20] + [0..6])
sage: w
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
sage: z
word: 7,8,9,10,11,12,13,14,15,16,17,18,19,20,0,1,2,3,4,5,6
sage: w.is_conjugate_with(z)
True
sage: z.is_conjugate_with(w)
True
sage: u = Word([4]*21)
sage: u.is_conjugate_with(w)
False
sage: u.is_conjugate_with(z)
False

Python

>>> from sage.all import *
>>> w = Word((ellipsis_range(Integer(0),Ellipsis,Integer(20))))
>>> z = Word((ellipsis_range(Integer(7),Ellipsis,Integer(20))) + (ellipsis_range(Integer(0),Ellipsis,Integer(6))))
>>> w
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
>>> z
word: 7,8,9,10,11,12,13,14,15,16,17,18,19,20,0,1,2,3,4,5,6
>>> w.is_conjugate_with(z)
True
>>> z.is_conjugate_with(w)
True
>>> u = Word([Integer(4)]*Integer(21))
>>> u.is_conjugate_with(w)
False
>>> u.is_conjugate_with(z)
False

Both words must be finite:

Sage

sage: w = Word(iter([2]*100),length='unknown')
sage: z = Word([2]*100)
sage: z.is_conjugate_with(w) #TODO: Not implemented for word of unknown length
True
sage: wf = Word(iter([2]*100),length='finite')
sage: z.is_conjugate_with(wf)
True
sage: wf.is_conjugate_with(z)
True

Python

>>> from sage.all import *
>>> w = Word(iter([Integer(2)]*Integer(100)),length='unknown')
>>> z = Word([Integer(2)]*Integer(100))
>>> z.is_conjugate_with(w) #TODO: Not implemented for word of unknown length
True
>>> wf = Word(iter([Integer(2)]*Integer(100)),length='finite')
>>> z.is_conjugate_with(wf)
True
>>> wf.is_conjugate_with(z)
True

is_cube()[source]¶

Return True if self is a cube, and False otherwise.

EXAMPLES:

Sage

sage: Word('012012012').is_cube()
True
sage: Word('01010101').is_cube()
False
sage: Word().is_cube()
True
sage: Word('012012').is_cube()
False

Python

>>> from sage.all import *
>>> Word('012012012').is_cube()
True
>>> Word('01010101').is_cube()
False
>>> Word().is_cube()
True
>>> Word('012012').is_cube()
False

is_cube_free()[source]¶

Return True if self does not contain cubes, and False otherwise.

EXAMPLES:

Sage

sage: Word('12312').is_cube_free()
True
sage: Word('32221').is_cube_free()
False
sage: Word().is_cube_free()
True

Python

>>> from sage.all import *
>>> Word('12312').is_cube_free()
True
>>> Word('32221').is_cube_free()
False
>>> Word().is_cube_free()
True

is_empty()[source]¶

Return True if the length of self is zero, and False otherwise.

EXAMPLES:

Sage

sage: Word([]).is_empty()
True
sage: Word('a').is_empty()
False

Python

>>> from sage.all import *
>>> Word([]).is_empty()
True
>>> Word('a').is_empty()
False

is_factor(other)[source]¶

Return True if self is a factor of other, and False otherwise.

A finite word \(u\in A^*\) is a factor of a finite word \(v\in A^*\) if there exists \(p,s\in A^*\) such that \(v=pus\).

EXAMPLES:

Sage

sage: u = Word('2113')
sage: w = Word('123121332131233121132123')
sage: u.is_factor(w)
True
sage: u = Word('321')
sage: w = Word('1231241231312312312')
sage: u.is_factor(w)
False

Python

>>> from sage.all import *
>>> u = Word('2113')
>>> w = Word('123121332131233121132123')
>>> u.is_factor(w)
True
>>> u = Word('321')
>>> w = Word('1231241231312312312')
>>> u.is_factor(w)
False

The empty word is factor of another word:

Sage

sage: Word().is_factor(Word())
True
sage: Word().is_factor(Word('a'))
True
sage: Word().is_factor(Word([1,2,3]))
True
sage: Word().is_factor(Word(lambda n:n, length=5))
True

Python

>>> from sage.all import *
>>> Word().is_factor(Word())
True
>>> Word().is_factor(Word('a'))
True
>>> Word().is_factor(Word([Integer(1),Integer(2),Integer(3)]))
True
>>> Word().is_factor(Word(lambda n:n, length=Integer(5)))
True

is_finite()[source]¶

Return True.

EXAMPLES:

Sage

sage: Word([]).is_finite()
True
sage: Word('a').is_finite()
True

Python

>>> from sage.all import *
>>> Word([]).is_finite()
True
>>> Word('a').is_finite()
True

is_full(f=None)[source]¶

Return True if self has defect \(0\), and False otherwise.

A word is full (or rich) if its defect is zero (see [BHNR2004]).

If f is given, then the f-palindromic defect is used (see [PeSt2011]).

INPUT:

f – involution (default: None) on the alphabet of self; it must be callable on letters as well as words (e.g. WordMorphism)

OUTPUT:

boolean – If f is None, whether self is full; otherwise, whether self is full of f-palindromes.

EXAMPLES:

Sage

sage: words.ThueMorseWord()[:100].is_full()
False
sage: words.FibonacciWord()[:100].is_full()
True
sage: Word('000000000000000').is_full()
True
sage: Word('011010011001').is_full()
False
sage: Word('2194').is_full()
True
sage: Word().is_full()
True

Python

>>> from sage.all import *
>>> words.ThueMorseWord()[:Integer(100)].is_full()
False
>>> words.FibonacciWord()[:Integer(100)].is_full()
True
>>> Word('000000000000000').is_full()
True
>>> Word('011010011001').is_full()
False
>>> Word('2194').is_full()
True
>>> Word().is_full()
True

Sage

sage: f = WordMorphism('a->b,b->a')
sage: Word().is_full(f)
True
sage: w = Word('ab')
sage: w.is_full()
True
sage: w.is_full(f)
True

Python

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a')
>>> Word().is_full(f)
True
>>> w = Word('ab')
>>> w.is_full()
True
>>> w.is_full(f)
True

Sage

sage: f = WordMorphism('a->b,b->a')
sage: Word('abab').is_full(f)
True
sage: Word('abba').is_full(f)
False

Python

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a')
>>> Word('abab').is_full(f)
True
>>> Word('abba').is_full(f)
False

A simple example of an infinite word full of f-palindromes:

Sage

sage: p = WordMorphism({0:'abc',1:'ab'})
sage: f = WordMorphism('a->b,b->a,c->c')
sage: p(words.FibonacciWord()[:50]).is_full(f)
True
sage: p(words.FibonacciWord()[:150]).is_full(f)
True

Python

>>> from sage.all import *
>>> p = WordMorphism({Integer(0):'abc',Integer(1):'ab'})
>>> f = WordMorphism('a->b,b->a,c->c')
>>> p(words.FibonacciWord()[:Integer(50)]).is_full(f)
True
>>> p(words.FibonacciWord()[:Integer(150)]).is_full(f)
True

is_lyndon()[source]¶

Return True if self is a Lyndon word, and False otherwise.

A Lyndon word is a non-empty word that is lexicographically smaller than each of its proper suffixes (for the given order on its alphabet). That is, \(w\) is a Lyndon word if \(w\) is non-empty and for each factorization \(w = uv\) (with \(u\), \(v\) both non-empty), we have \(w < v\).

Equivalently, \(w\) is a Lyndon word iff \(w\) is a non-empty word that is lexicographically smaller than each of its proper conjugates for the given order on its alphabet.

See for instance [Lot1983].

EXAMPLES:

Sage

sage: Word('123132133').is_lyndon()
True
sage: Word().is_lyndon()
False
sage: Word('122112').is_lyndon()
False

Python

>>> from sage.all import *
>>> Word('123132133').is_lyndon()
True
>>> Word().is_lyndon()
False
>>> Word('122112').is_lyndon()
False

is_overlap()[source]¶

Return True if self is an overlap, and False otherwise.

EXAMPLES:

Sage

sage: Word('12121').is_overlap()
True
sage: Word('123').is_overlap()
False
sage: Word('1231').is_overlap()
False
sage: Word('123123').is_overlap()
False
sage: Word('1231231').is_overlap()
True
sage: Word().is_overlap()
False

Python

>>> from sage.all import *
>>> Word('12121').is_overlap()
True
>>> Word('123').is_overlap()
False
>>> Word('1231').is_overlap()
False
>>> Word('123123').is_overlap()
False
>>> Word('1231231').is_overlap()
True
>>> Word().is_overlap()
False

is_palindrome(f=None)[source]¶

Return True if self is a palindrome (or a f-palindrome), and False otherwise.

Let \(f : \Sigma \rightarrow \Sigma\) be an involution that extends to a morphism on \(\Sigma^*\). We say that \(w\in\Sigma^*\) is a `f`-palindrome if \(w=f(\tilde{w})\) [Lab2008]. Also called `f`-pseudo-palindrome [AZZ2005].

INPUT:

f – involution (default: None) on the alphabet of self. It must be callable on letters as well as words (e.g. WordMorphism). The default value corresponds to usual palindromes, i.e., f equal to the identity.

EXAMPLES:

Sage

sage: Word('esope reste ici et se repose').is_palindrome()
False
sage: Word('esoperesteicietserepose').is_palindrome()
True
sage: Word('I saw I was I').is_palindrome()
True
sage: Word('abbcbba').is_palindrome()
True
sage: Word('abcbdba').is_palindrome()
False

Python

>>> from sage.all import *
>>> Word('esope reste ici et se repose').is_palindrome()
False
>>> Word('esoperesteicietserepose').is_palindrome()
True
>>> Word('I saw I was I').is_palindrome()
True
>>> Word('abbcbba').is_palindrome()
True
>>> Word('abcbdba').is_palindrome()
False

Some \(f\)-palindromes:

Sage

sage: f = WordMorphism('a->b,b->a')
sage: Word('aababb').is_palindrome(f)
True

Python

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a')
>>> Word('aababb').is_palindrome(f)
True

Sage

sage: f = WordMorphism('a->b,b->a,c->c')
sage: Word('abacbacbab').is_palindrome(f)
True

Python

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a,c->c')
>>> Word('abacbacbab').is_palindrome(f)
True

Sage

sage: f = WordMorphism({'a':'b','b':'a'})
sage: Word('aababb').is_palindrome(f)
True

Python

>>> from sage.all import *
>>> f = WordMorphism({'a':'b','b':'a'})
>>> Word('aababb').is_palindrome(f)
True

Sage

sage: f = WordMorphism({0:[1],1:[0]})
sage: w = words.ThueMorseWord()[:8]; w
word: 01101001
sage: w.is_palindrome(f)
True

Python

>>> from sage.all import *
>>> f = WordMorphism({Integer(0):[Integer(1)],Integer(1):[Integer(0)]})
>>> w = words.ThueMorseWord()[:Integer(8)]; w
word: 01101001
>>> w.is_palindrome(f)
True

The word must be in the domain of the involution:

Sage

sage: f = WordMorphism('a->a')
sage: Word('aababb').is_palindrome(f)
Traceback (most recent call last):
...
KeyError: 'b'

Python

>>> from sage.all import *
>>> f = WordMorphism('a->a')
>>> Word('aababb').is_palindrome(f)
Traceback (most recent call last):
...
KeyError: 'b'

is_prefix(other)[source]¶

Return True if self is a prefix of other, and False otherwise.

EXAMPLES:

Sage

sage: w = Word('0123456789')
sage: y = Word('012345')
sage: y.is_prefix(w)
True
sage: w.is_prefix(y)
False
sage: w.is_prefix(Word())
False
sage: Word().is_prefix(w)
True
sage: Word().is_prefix(Word())
True

Python

>>> from sage.all import *
>>> w = Word('0123456789')
>>> y = Word('012345')
>>> y.is_prefix(w)
True
>>> w.is_prefix(y)
False
>>> w.is_prefix(Word())
False
>>> Word().is_prefix(w)
True
>>> Word().is_prefix(Word())
True

is_primitive()[source]¶

Return True if self is primitive, and False otherwise.

A finite word \(w\) is primitive if it is not a positive integer power of a shorter word.

EXAMPLES:

Sage

sage: Word('1231').is_primitive()
True
sage: Word('111').is_primitive()
False

Python

>>> from sage.all import *
>>> Word('1231').is_primitive()
True
>>> Word('111').is_primitive()
False

is_proper_prefix(other)[source]¶

Return True if self is a proper prefix of other, and False otherwise.

EXAMPLES:

Sage

sage: Word('12').is_proper_prefix(Word('123'))
True
sage: Word('12').is_proper_prefix(Word('12'))
False
sage: Word().is_proper_prefix(Word('123'))
True
sage: Word('123').is_proper_prefix(Word('12'))
False
sage: Word().is_proper_prefix(Word())
False

Python

>>> from sage.all import *
>>> Word('12').is_proper_prefix(Word('123'))
True
>>> Word('12').is_proper_prefix(Word('12'))
False
>>> Word().is_proper_prefix(Word('123'))
True
>>> Word('123').is_proper_prefix(Word('12'))
False
>>> Word().is_proper_prefix(Word())
False

is_proper_suffix(other)[source]¶

Return True if self is a proper suffix of other, and False otherwise.

EXAMPLES:

Sage

sage: Word('23').is_proper_suffix(Word('123'))
True
sage: Word('12').is_proper_suffix(Word('12'))
False
sage: Word().is_proper_suffix(Word('123'))
True
sage: Word('123').is_proper_suffix(Word('12'))
False

Python

>>> from sage.all import *
>>> Word('23').is_proper_suffix(Word('123'))
True
>>> Word('12').is_proper_suffix(Word('12'))
False
>>> Word().is_proper_suffix(Word('123'))
True
>>> Word('123').is_proper_suffix(Word('12'))
False

is_quasiperiodic()[source]¶

Return True if self is quasiperiodic, and False otherwise.

A finite or infinite word \(w\) is quasiperiodic if it can be constructed by concatenations and superpositions of one of its proper factors \(u\), which is called a quasiperiod of \(w\). See for instance [AE1993], [Mar2004], and [GLR2008].

EXAMPLES:

Sage

sage: Word('abaababaabaababaaba').is_quasiperiodic()
True
sage: Word('abacaba').is_quasiperiodic()
False
sage: Word('a').is_quasiperiodic()
False
sage: Word().is_quasiperiodic()
False
sage: Word('abaaba').is_quasiperiodic()
True

Python

>>> from sage.all import *
>>> Word('abaababaabaababaaba').is_quasiperiodic()
True
>>> Word('abacaba').is_quasiperiodic()
False
>>> Word('a').is_quasiperiodic()
False
>>> Word().is_quasiperiodic()
False
>>> Word('abaaba').is_quasiperiodic()
True

is_rich(f=None)[source]¶

Return True if self has defect \(0\), and False otherwise.

A word is full (or rich) if its defect is zero (see [BHNR2004]).

If f is given, then the f-palindromic defect is used (see [PeSt2011]).

INPUT:

f – involution (default: None) on the alphabet of self; it must be callable on letters as well as words (e.g. WordMorphism)

OUTPUT:

boolean – If f is None, whether self is full; otherwise, whether self is full of f-palindromes.

EXAMPLES:

Sage

sage: words.ThueMorseWord()[:100].is_full()
False
sage: words.FibonacciWord()[:100].is_full()
True
sage: Word('000000000000000').is_full()
True
sage: Word('011010011001').is_full()
False
sage: Word('2194').is_full()
True
sage: Word().is_full()
True

Python

>>> from sage.all import *
>>> words.ThueMorseWord()[:Integer(100)].is_full()
False
>>> words.FibonacciWord()[:Integer(100)].is_full()
True
>>> Word('000000000000000').is_full()
True
>>> Word('011010011001').is_full()
False
>>> Word('2194').is_full()
True
>>> Word().is_full()
True

Sage

sage: f = WordMorphism('a->b,b->a')
sage: Word().is_full(f)
True
sage: w = Word('ab')
sage: w.is_full()
True
sage: w.is_full(f)
True

Python

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a')
>>> Word().is_full(f)
True
>>> w = Word('ab')
>>> w.is_full()
True
>>> w.is_full(f)
True

Sage

sage: f = WordMorphism('a->b,b->a')
sage: Word('abab').is_full(f)
True
sage: Word('abba').is_full(f)
False

Python

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a')
>>> Word('abab').is_full(f)
True
>>> Word('abba').is_full(f)
False

A simple example of an infinite word full of f-palindromes:

Sage

sage: p = WordMorphism({0:'abc',1:'ab'})
sage: f = WordMorphism('a->b,b->a,c->c')
sage: p(words.FibonacciWord()[:50]).is_full(f)
True
sage: p(words.FibonacciWord()[:150]).is_full(f)
True

Python

>>> from sage.all import *
>>> p = WordMorphism({Integer(0):'abc',Integer(1):'ab'})
>>> f = WordMorphism('a->b,b->a,c->c')
>>> p(words.FibonacciWord()[:Integer(50)]).is_full(f)
True
>>> p(words.FibonacciWord()[:Integer(150)]).is_full(f)
True

is_smooth_prefix()[source]¶

Return True if self is the prefix of a smooth word, and False otherwise.

Let \(A_k = \{1, \ldots ,k\}\), \(k \geq 2\). An infinite word \(w\) in \(A_k^\omega\) is said to be smooth if and only if for all positive integers \(m\), \(\Delta^m(w)\) is in \(A_k^\omega\), where \(\Delta(w)\) is the word obtained from \(w\) by composing the length of consecutive runs of the same letter in \(w\). See for instance [BL2003] and [BDLV2006].

INPUT:

self – must be a word over the integers to get something other than False

OUTPUT: boolean; whether self is a smooth prefix or not

EXAMPLES:

Sage

sage: W = Words([1, 2])
sage: W([1, 1, 2, 2, 1, 2, 1, 1]).is_smooth_prefix()
True
sage: W([1, 2, 1, 2, 1, 2]).is_smooth_prefix()
False

Python

>>> from sage.all import *
>>> W = Words([Integer(1), Integer(2)])
>>> W([Integer(1), Integer(1), Integer(2), Integer(2), Integer(1), Integer(2), Integer(1), Integer(1)]).is_smooth_prefix()
True
>>> W([Integer(1), Integer(2), Integer(1), Integer(2), Integer(1), Integer(2)]).is_smooth_prefix()
False

is_square()[source]¶

Return True if self is a square, and False otherwise.

EXAMPLES:

Sage

sage: Word([1,0,0,1]).is_square()
False
sage: Word('1212').is_square()
True
sage: Word('1213').is_square()
False
sage: Word('12123').is_square()
False
sage: Word().is_square()
True

Python

>>> from sage.all import *
>>> Word([Integer(1),Integer(0),Integer(0),Integer(1)]).is_square()
False
>>> Word('1212').is_square()
True
>>> Word('1213').is_square()
False
>>> Word('12123').is_square()
False
>>> Word().is_square()
True

is_square_free()[source]¶

Return True if self does not contain squares, and False otherwise.

EXAMPLES:

Sage

sage: Word('12312').is_square_free()
True
sage: Word('31212').is_square_free()
False
sage: Word().is_square_free()
True

Python

>>> from sage.all import *
>>> Word('12312').is_square_free()
True
>>> Word('31212').is_square_free()
False
>>> Word().is_square_free()
True

is_sturmian_factor()[source]¶

Tell whether self is a factor of a Sturmian word.

The finite word self must be defined on a two-letter alphabet.

Equivalently, tells whether self is balanced. The advantage over the is_balanced method is that this one runs in linear time whereas is_balanced runs in quadratic time.

OUTPUT: boolean

EXAMPLES:

Sage

sage: w = Word('0111011011011101101',alphabet='01')
sage: w.is_sturmian_factor()
True

Python

>>> from sage.all import *
>>> w = Word('0111011011011101101',alphabet='01')
>>> w.is_sturmian_factor()
True

Sage

sage: words.LowerMechanicalWord(random(),alphabet='01')[:100].is_sturmian_factor()
True
sage: words.CharacteristicSturmianWord(random())[:100].is_sturmian_factor()             # needs sage.rings.real_mpfr
True

Python

>>> from sage.all import *
>>> words.LowerMechanicalWord(random(),alphabet='01')[:Integer(100)].is_sturmian_factor()
True
>>> words.CharacteristicSturmianWord(random())[:Integer(100)].is_sturmian_factor()             # needs sage.rings.real_mpfr
True

Sage

sage: w = Word('aabb',alphabet='ab')
sage: w.is_sturmian_factor()
False

sage: s1 = WordMorphism('a->ab,b->b')
sage: s2 = WordMorphism('a->ba,b->b')
sage: s3 = WordMorphism('a->a,b->ba')
sage: s4 = WordMorphism('a->a,b->ab')
sage: W = Words('ab')
sage: w = W('ab')
sage: for i in range(8): w = choice([s1,s2,s3,s4])(w)
sage: w.is_sturmian_factor()
True

Python

>>> from sage.all import *
>>> w = Word('aabb',alphabet='ab')
>>> w.is_sturmian_factor()
False

>>> s1 = WordMorphism('a->ab,b->b')
>>> s2 = WordMorphism('a->ba,b->b')
>>> s3 = WordMorphism('a->a,b->ba')
>>> s4 = WordMorphism('a->a,b->ab')
>>> W = Words('ab')
>>> w = W('ab')
>>> for i in range(Integer(8)): w = choice([s1,s2,s3,s4])(w)
>>> w.is_sturmian_factor()
True

Famous words:

Sage

sage: words.FibonacciWord()[:100].is_sturmian_factor()
True
sage: words.ThueMorseWord()[:1000].is_sturmian_factor()
False
sage: words.KolakoskiWord()[:1000].is_sturmian_factor()
False

Python

>>> from sage.all import *
>>> words.FibonacciWord()[:Integer(100)].is_sturmian_factor()
True
>>> words.ThueMorseWord()[:Integer(1000)].is_sturmian_factor()
False
>>> words.KolakoskiWord()[:Integer(1000)].is_sturmian_factor()
False

See [Arn2002], [Ser1985], and [SU2009].

AUTHOR:

Thierry Monteil

is_subword_of(other)[source]¶

Return True if self is a subword of other, and False otherwise.

A finite word \(u\) is a subword of a finite word \(v\) if \(u\) is a subsequence of \(v\). See Chapter 6 on Subwords in [Lot1997].

Some references define subword as a consecutive subsequence. Use is_factor() if this is what you need.

INPUT:

other – a finite word

EXAMPLES:

Sage

sage: Word('bb').is_subword_of(Word('ababa'))
True
sage: Word('bbb').is_subword_of(Word('ababa'))
False

Python

>>> from sage.all import *
>>> Word('bb').is_subword_of(Word('ababa'))
True
>>> Word('bbb').is_subword_of(Word('ababa'))
False

Sage

sage: Word().is_subword_of(Word('123'))
True
sage: Word('123').is_subword_of(Word('3211333213233321'))
True
sage: Word('321').is_subword_of(Word('11122212112122133111222332'))
False

Python

>>> from sage.all import *
>>> Word().is_subword_of(Word('123'))
True
>>> Word('123').is_subword_of(Word('3211333213233321'))
True
>>> Word('321').is_subword_of(Word('11122212112122133111222332'))
False

is_suffix(other)[source]¶

Return True if self is a suffix of other, and False otherwise.

EXAMPLES:

Sage

sage: w = Word('0123456789')
sage: y = Word('56789')
sage: y.is_suffix(w)
True
sage: w.is_suffix(y)
False
sage: Word('579').is_suffix(w)
False
sage: Word().is_suffix(y)
True
sage: w.is_suffix(Word())
False
sage: Word().is_suffix(Word())
True

Python

>>> from sage.all import *
>>> w = Word('0123456789')
>>> y = Word('56789')
>>> y.is_suffix(w)
True
>>> w.is_suffix(y)
False
>>> Word('579').is_suffix(w)
False
>>> Word().is_suffix(y)
True
>>> w.is_suffix(Word())
False
>>> Word().is_suffix(Word())
True

is_symmetric(f=None)[source]¶

Return True if self is symmetric (or f-symmetric), and False otherwise.

A word is symmetric (resp. \(f\)-symmetric) if it is the product of two palindromes (resp. \(f\)-palindromes). See [BHNR2004] and [DeLuca2006].

INPUT:

f – involution (default: None) on the alphabet of self; it must be callable on letters as well as words (e.g. WordMorphism)

EXAMPLES:

Sage

sage: Word('abbabab').is_symmetric()
True
sage: Word('ababa').is_symmetric()
True
sage: Word('aababaabba').is_symmetric()
False
sage: Word('aabbbaababba').is_symmetric()
False
sage: f = WordMorphism('a->b,b->a')
sage: Word('aabbbaababba').is_symmetric(f)
True

Python

>>> from sage.all import *
>>> Word('abbabab').is_symmetric()
True
>>> Word('ababa').is_symmetric()
True
>>> Word('aababaabba').is_symmetric()
False
>>> Word('aabbbaababba').is_symmetric()
False
>>> f = WordMorphism('a->b,b->a')
>>> Word('aabbbaababba').is_symmetric(f)
True

is_tangent()[source]¶

Tell whether self is a tangent word.

The finite word self must be defined on a two-letter alphabet.

A binary word is said to be tangent if it can appear in infinitely many cutting sequences of a smooth curve, where each cutting sequence is observed on a progressively smaller grid.

This class of words strictly contains the class of \(1\)-balanced words, and is strictly contained in the class of \(2\)-balanced words.

This method runs in linear time.

OUTPUT: boolean

EXAMPLES:

Sage

sage: w = Word('01110110110111011101',alphabet='01')
sage: w.is_tangent()
True

Python

>>> from sage.all import *
>>> w = Word('01110110110111011101',alphabet='01')
>>> w.is_tangent()
True

Some tangent words may not be balanced:

Sage

sage: Word('aabb',alphabet='ab').is_balanced()
False
sage: Word('aabb',alphabet='ab').is_tangent()
True

Python

>>> from sage.all import *
>>> Word('aabb',alphabet='ab').is_balanced()
False
>>> Word('aabb',alphabet='ab').is_tangent()
True

Some \(2\)-balanced words may not be tangent:

Sage

sage: Word('aaabb',alphabet='ab').is_tangent()
False
sage: Word('aaabb',alphabet='ab').is_balanced(2)
True

Python

>>> from sage.all import *
>>> Word('aaabb',alphabet='ab').is_tangent()
False
>>> Word('aaabb',alphabet='ab').is_balanced(Integer(2))
True

Famous words:

Sage

sage: words.FibonacciWord()[:100].is_tangent()
True
sage: words.ThueMorseWord()[:1000].is_tangent()
True
sage: words.KolakoskiWord()[:1000].is_tangent()
False

Python

>>> from sage.all import *
>>> words.FibonacciWord()[:Integer(100)].is_tangent()
True
>>> words.ThueMorseWord()[:Integer(1000)].is_tangent()
True
>>> words.KolakoskiWord()[:Integer(1000)].is_tangent()
False

See [Mon2010].

AUTHOR:

Thierry Monteil

is_yamanouchi(n=None)[source]¶

Return whether self is Yamanouchi.

A word \(w\) is Yamanouchi if, when read from right to left, it always has weakly more \(i\)’s than \(i+1\)’s for all \(i\) that appear in \(w\).

INPUT:

n – (optional) an integer specifying the maximal letter in the alphabet

EXAMPLES:

Sage

sage: w = Word([1,2,4,3,2,2,2])
sage: w.is_yamanouchi()
False
sage: w = Word([2,3,4,3,1,2,1,1,2,1])
sage: w.is_yamanouchi()
True
sage: w = Word([3,1])
sage: w.is_yamanouchi(n=3)
False
sage: w.is_yamanouchi()
True
sage: w = Word([3,1],alphabet=[1,2,3])
sage: w.is_yamanouchi()
False
sage: w = Word([2,1,1,2])
sage: w.is_yamanouchi()
False

Python

>>> from sage.all import *
>>> w = Word([Integer(1),Integer(2),Integer(4),Integer(3),Integer(2),Integer(2),Integer(2)])
>>> w.is_yamanouchi()
False
>>> w = Word([Integer(2),Integer(3),Integer(4),Integer(3),Integer(1),Integer(2),Integer(1),Integer(1),Integer(2),Integer(1)])
>>> w.is_yamanouchi()
True
>>> w = Word([Integer(3),Integer(1)])
>>> w.is_yamanouchi(n=Integer(3))
False
>>> w.is_yamanouchi()
True
>>> w = Word([Integer(3),Integer(1)],alphabet=[Integer(1),Integer(2),Integer(3)])
>>> w.is_yamanouchi()
False
>>> w = Word([Integer(2),Integer(1),Integer(1),Integer(2)])
>>> w.is_yamanouchi()
False

iterated_left_palindromic_closure(f=None)[source]¶

Return the iterated left (f-)palindromic closure of self.

INPUT:

f – involution (default: None) on the alphabet of self; it must be callable on letters as well as words (e.g. WordMorphism)

OUTPUT: word; the left iterated f-palindromic closure of self

EXAMPLES:

Sage

sage: Word('123').iterated_left_palindromic_closure()
word: 3231323
sage: f = WordMorphism('a->b,b->a')
sage: Word('ab').iterated_left_palindromic_closure(f=f)
word: abbaab
sage: Word('aab').iterated_left_palindromic_closure(f=f)
word: abbaabbaab

Python

>>> from sage.all import *
>>> Word('123').iterated_left_palindromic_closure()
word: 3231323
>>> f = WordMorphism('a->b,b->a')
>>> Word('ab').iterated_left_palindromic_closure(f=f)
word: abbaab
>>> Word('aab').iterated_left_palindromic_closure(f=f)
word: abbaabbaab

lacunas(f=None)[source]¶

Return the list of all the lacunas of self.

A lacuna is a position in a word where the longest (\(f\)-)palindromic suffix is not unioccurrent (see [BMBL2008]).

INPUT:

f – involution (default: None) on the alphabet of self. It must be callable on letters as well as words (e.g. WordMorphism). The default value corresponds to usual palindromes, i.e., f equal to the identity.

OUTPUT: list of all the lacunas of self

EXAMPLES:

Sage

sage: w = Word([0,1,1,2,3,4,5,1,13,3])
sage: w.lacunas()
[7, 9]
sage: words.ThueMorseWord()[:100].lacunas()
[8, 9, 24, 25, 32, 33, 34, 35, 36, 37, 38, 39, 96, 97, 98, 99]
sage: f = WordMorphism({0:[1],1:[0]})
sage: words.ThueMorseWord()[:50].lacunas(f)
[0, 2, 4, 12, 16, 17, 18, 19, 48, 49]

Python

>>> from sage.all import *
>>> w = Word([Integer(0),Integer(1),Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(1),Integer(13),Integer(3)])
>>> w.lacunas()
[7, 9]
>>> words.ThueMorseWord()[:Integer(100)].lacunas()
[8, 9, 24, 25, 32, 33, 34, 35, 36, 37, 38, 39, 96, 97, 98, 99]
>>> f = WordMorphism({Integer(0):[Integer(1)],Integer(1):[Integer(0)]})
>>> words.ThueMorseWord()[:Integer(50)].lacunas(f)
[0, 2, 4, 12, 16, 17, 18, 19, 48, 49]

last_position_dict()[source]¶

Return a dictionary that contains the last position of each letter in self.

EXAMPLES:

Sage

sage: Word('1231232').last_position_dict()
{'1': 3, '2': 6, '3': 5}

Python

>>> from sage.all import *
>>> Word('1231232').last_position_dict()
{'1': 3, '2': 6, '3': 5}

left_special_factors(n=None)[source]¶

Return the left special factors (of length n).

A factor \(u\) of a word \(w\) is left special if there are two distinct letters \(a\) and \(b\) such that \(au\) and \(bu\) are factors of \(w\).

INPUT:

n – integer (default: None); if None, it returns all left special factors

OUTPUT: list of words

EXAMPLES:

Sage

sage: alpha, beta, x = 0.54, 0.294, 0.1415
sage: w = words.CodingOfRotationWord(alpha, beta, x)[:40]
sage: for i in range(5):
....:     print("{} {}".format(i, sorted(w.left_special_factors(i))))
0 [word: ]
1 [word: 0]
2 [word: 00, word: 01]
3 [word: 000, word: 010]
4 [word: 0000, word: 0101]

Python

>>> from sage.all import *
>>> alpha, beta, x = RealNumber('0.54'), RealNumber('0.294'), RealNumber('0.1415')
>>> w = words.CodingOfRotationWord(alpha, beta, x)[:Integer(40)]
>>> for i in range(Integer(5)):
...     print("{} {}".format(i, sorted(w.left_special_factors(i))))
0 [word: ]
1 [word: 0]
2 [word: 00, word: 01]
3 [word: 000, word: 010]
4 [word: 0000, word: 0101]

left_special_factors_iterator(n=None)[source]¶

Return an iterator over the left special factors (of length n).

A factor \(u\) of a word \(w\) is left special if there are two distinct letters \(a\) and \(b\) such that \(au\) and \(bu\) are factors of \(w\).

INPUT:

n – integer (default: None); if None, it returns an iterator over all left special factors

EXAMPLES:

Sage

sage: alpha, beta, x = 0.54, 0.294, 0.1415
sage: w = words.CodingOfRotationWord(alpha, beta, x)[:40]
sage: sorted(w.left_special_factors_iterator(3))
[word: 000, word: 010]
sage: sorted(w.left_special_factors_iterator(4))
[word: 0000, word: 0101]
sage: sorted(w.left_special_factors_iterator(5))
[word: 00000, word: 01010]

Python

>>> from sage.all import *
>>> alpha, beta, x = RealNumber('0.54'), RealNumber('0.294'), RealNumber('0.1415')
>>> w = words.CodingOfRotationWord(alpha, beta, x)[:Integer(40)]
>>> sorted(w.left_special_factors_iterator(Integer(3)))
[word: 000, word: 010]
>>> sorted(w.left_special_factors_iterator(Integer(4)))
[word: 0000, word: 0101]
>>> sorted(w.left_special_factors_iterator(Integer(5)))
[word: 00000, word: 01010]

length()[source]¶: Return the length of self.

length_border()[source]¶

Return the length of the border of self.

The border of a word is the longest word that is both a proper prefix and a proper suffix of self.

EXAMPLES:

Sage

sage: Word('121').length_border()
1
sage: Word('1').length_border()
0
sage: Word('1212').length_border()
2
sage: Word('111').length_border()
2
sage: Word().length_border() is None
True

Python

>>> from sage.all import *
>>> Word('121').length_border()
1
>>> Word('1').length_border()
0
>>> Word('1212').length_border()
2
>>> Word('111').length_border()
2
>>> Word().length_border() is None
True

length_maximal_palindrome(j, m=None, f=None)[source]¶

Return the length of the longest palindrome centered at position j.

INPUT:

j – rational; position of the symmetry axis of the palindrome. Must return an integer when doubled. It is an integer when the center of the palindrome is a letter.
m – integer (default: None); minimal length of palindrome, if known. The parity of m can’t be the same as the parity of 2j.
f – involution (default: None) on the alphabet; it must be callable on letters as well as words (e.g. WordMorphism)

OUTPUT: length of the longest f-palindrome centered at position j

EXAMPLES:

Sage

sage: Word('01001010').length_maximal_palindrome(3/2)
0
sage: Word('01101001').length_maximal_palindrome(3/2)
4
sage: Word('01010').length_maximal_palindrome(j=3, f='0->1,1->0')
0
sage: Word('01010').length_maximal_palindrome(j=2.5, f='0->1,1->0')
4
sage: Word('0222220').length_maximal_palindrome(3, f='0->1,1->0,2->2')
5

Python

>>> from sage.all import *
>>> Word('01001010').length_maximal_palindrome(Integer(3)/Integer(2))
0
>>> Word('01101001').length_maximal_palindrome(Integer(3)/Integer(2))
4
>>> Word('01010').length_maximal_palindrome(j=Integer(3), f='0->1,1->0')
0
>>> Word('01010').length_maximal_palindrome(j=RealNumber('2.5'), f='0->1,1->0')
4
>>> Word('0222220').length_maximal_palindrome(Integer(3), f='0->1,1->0,2->2')
5

Sage

sage: w = Word('abcdcbaxyzzyx')
sage: w.length_maximal_palindrome(3)
7
sage: w.length_maximal_palindrome(3, 3)
7
sage: w.length_maximal_palindrome(3.5)
0
sage: w.length_maximal_palindrome(9.5)
6
sage: w.length_maximal_palindrome(9.5, 2)
6

Python

>>> from sage.all import *
>>> w = Word('abcdcbaxyzzyx')
>>> w.length_maximal_palindrome(Integer(3))
7
>>> w.length_maximal_palindrome(Integer(3), Integer(3))
7
>>> w.length_maximal_palindrome(RealNumber('3.5'))
0
>>> w.length_maximal_palindrome(RealNumber('9.5'))
6
>>> w.length_maximal_palindrome(RealNumber('9.5'), Integer(2))
6

lengths_maximal_palindromes(f=None)[source]¶

Return the length of maximal palindromes centered at each position.

INPUT:

f – involution (default: None) on the alphabet of self; it must be callable on letters as well as words (e.g. WordMorphism)

OUTPUT: list; the length of the maximal palindrome (or f-palindrome) with a given symmetry axis (letter or space between two letters)

EXAMPLES:

Sage

sage: Word('01101001').lengths_maximal_palindromes()
[0, 1, 0, 1, 4, 1, 0, 3, 0, 3, 0, 1, 4, 1, 0, 1, 0]
sage: Word('00000').lengths_maximal_palindromes()
[0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0]
sage: Word('0').lengths_maximal_palindromes()
[0, 1, 0]
sage: Word('').lengths_maximal_palindromes()
[0]
sage: Word().lengths_maximal_palindromes()
[0]
sage: f = WordMorphism('a->b,b->a')
sage: Word('abbabaab').lengths_maximal_palindromes(f)
[0, 0, 2, 0, 0, 0, 2, 0, 8, 0, 2, 0, 0, 0, 2, 0, 0]

Python

>>> from sage.all import *
>>> Word('01101001').lengths_maximal_palindromes()
[0, 1, 0, 1, 4, 1, 0, 3, 0, 3, 0, 1, 4, 1, 0, 1, 0]
>>> Word('00000').lengths_maximal_palindromes()
[0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0]
>>> Word('0').lengths_maximal_palindromes()
[0, 1, 0]
>>> Word('').lengths_maximal_palindromes()
[0]
>>> Word().lengths_maximal_palindromes()
[0]
>>> f = WordMorphism('a->b,b->a')
>>> Word('abbabaab').lengths_maximal_palindromes(f)
[0, 0, 2, 0, 0, 0, 2, 0, 8, 0, 2, 0, 0, 0, 2, 0, 0]

lengths_unioccurrent_lps(f=None)[source]¶

Return the list of the lengths of the unioccurrent longest (f)-palindromic suffixes (lps) for each non-empty prefix of self. No unioccurrent lps are indicated by None.

It corresponds to the function \(H_w\) defined in [BMBL2008] and [BMBFLR2008].

INPUT:

f – involution (default: None) on the alphabet of self. It must be callable on letters as well as words (e.g. WordMorphism). The default value corresponds to usual palindromes, i.e., f equal to the identity.

OUTPUT:

a list – list of the length of the unioccurrent longest palindromic suffix (lps) for each non-empty prefix of self. No unioccurrent lps are indicated by None.

EXAMPLES:

Sage

sage: w = Word([0,1,1,2,3,4,5,1,13,3])
sage: w.lengths_unioccurrent_lps()
[1, 1, 2, 1, 1, 1, 1, None, 1, None]
sage: f = words.FibonacciWord()[:20]
sage: f.lengths_unioccurrent_lps() == f.lps_lengths()[1:]
True
sage: t = words.ThueMorseWord()
sage: t[:20].lengths_unioccurrent_lps()
[1, 1, 2, 4, 3, 3, 2, 4, None, None, 6, 8, 10, 12, 14, 16, 6, 8, 10, 12]
sage: f = WordMorphism({1:[0],0:[1]})
sage: t[:15].lengths_unioccurrent_lps(f)
[None, 2, None, 2, None, 4, 6, 8, 4, 6, 4, 6, None, 4, 6]

Python

>>> from sage.all import *
>>> w = Word([Integer(0),Integer(1),Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(1),Integer(13),Integer(3)])
>>> w.lengths_unioccurrent_lps()
[1, 1, 2, 1, 1, 1, 1, None, 1, None]
>>> f = words.FibonacciWord()[:Integer(20)]
>>> f.lengths_unioccurrent_lps() == f.lps_lengths()[Integer(1):]
True
>>> t = words.ThueMorseWord()
>>> t[:Integer(20)].lengths_unioccurrent_lps()
[1, 1, 2, 4, 3, 3, 2, 4, None, None, 6, 8, 10, 12, 14, 16, 6, 8, 10, 12]
>>> f = WordMorphism({Integer(1):[Integer(0)],Integer(0):[Integer(1)]})
>>> t[:Integer(15)].lengths_unioccurrent_lps(f)
[None, 2, None, 2, None, 4, 6, 8, 4, 6, 4, 6, None, 4, 6]

letters()[source]¶

Return the list of letters that appear in this word, listed in the order of first appearance.

EXAMPLES:

Sage

sage: Word([0,1,1,0,1,0,0,1]).letters()
[0, 1]
sage: Word("cacao").letters()
['c', 'a', 'o']

Python

>>> from sage.all import *
>>> Word([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1)]).letters()
[0, 1]
>>> Word("cacao").letters()
['c', 'a', 'o']

longest_backward_extension(x, y)[source]¶

Compute the length of the longest factor of self that ends at x and that matches a factor that ends at y.

INPUT:

x, y – positions in self

EXAMPLES:

Sage

sage: w = Word('0011001')
sage: w.longest_backward_extension(6, 2)
3
sage: w.longest_backward_extension(1, 4)
1
sage: w.longest_backward_extension(1, 3)
0

Python

>>> from sage.all import *
>>> w = Word('0011001')
>>> w.longest_backward_extension(Integer(6), Integer(2))
3
>>> w.longest_backward_extension(Integer(1), Integer(4))
1
>>> w.longest_backward_extension(Integer(1), Integer(3))
0

The method also accepts negative positions indicating the distance from the end of the word (in order to be consist with how negative indices work with lists). For instance, for a word of length \(7\), using positions \(6\) and \(-5\) is the same as using positions \(6\) and \(2\):

Sage

sage: w.longest_backward_extension(6, -5)
3
sage: w.longest_backward_extension(-6, 4)
1

Python

>>> from sage.all import *
>>> w.longest_backward_extension(Integer(6), -Integer(5))
3
>>> w.longest_backward_extension(-Integer(6), Integer(4))
1

longest_common_subword(other)[source]¶

Return a longest subword of self and other.

A subword of a word is a subset of the word’s letters, read in the order in which they appear in the word.

For more information, see Wikipedia article Longest_common_subsequence_problem.

INPUT:

other – a word

ALGORITHM:

For any indices \(i,j\), we compute the longest common subword lcs[i,j] of self[:i] and other[:j]. This can be easily obtained as the longest of

lcs[i-1,j]
lcs[i,j-1]
lcs[i-1,j-1]+self[i] if self[i]==other[j]

EXAMPLES:

Sage

sage: v1 = Word("abc")
sage: v2 = Word("ace")
sage: v1.longest_common_subword(v2)
word: ac

sage: w1 = Word("1010101010101010101010101010101010101010")
sage: w2 = Word("0011001100110011001100110011001100110011")
sage: w1.longest_common_subword(w2)
word: 00110011001100110011010101010

Python

>>> from sage.all import *
>>> v1 = Word("abc")
>>> v2 = Word("ace")
>>> v1.longest_common_subword(v2)
word: ac

>>> w1 = Word("1010101010101010101010101010101010101010")
>>> w2 = Word("0011001100110011001100110011001100110011")
>>> w1.longest_common_subword(w2)
word: 00110011001100110011010101010

See also

is_subword_of()

longest_common_suffix(other)[source]¶

Return the longest common suffix of self and other.

EXAMPLES:

Sage

sage: w = Word('112345678')
sage: u = Word('1115678')
sage: w.longest_common_suffix(u)
word: 5678
sage: u.longest_common_suffix(u)
word: 1115678
sage: u.longest_common_suffix(w)
word: 5678
sage: w.longest_common_suffix(w)
word: 112345678
sage: y = Word('549332345')
sage: w.longest_common_suffix(y)
word:

Python

>>> from sage.all import *
>>> w = Word('112345678')
>>> u = Word('1115678')
>>> w.longest_common_suffix(u)
word: 5678
>>> u.longest_common_suffix(u)
word: 1115678
>>> u.longest_common_suffix(w)
word: 5678
>>> w.longest_common_suffix(w)
word: 112345678
>>> y = Word('549332345')
>>> w.longest_common_suffix(y)
word:

longest_forward_extension(x, y)[source]¶

Compute the length of the longest factor of self that starts at x and that matches a factor that starts at y.

INPUT:

x, y – positions in self

EXAMPLES:

Sage

sage: w = Word('0011001')
sage: w.longest_forward_extension(0, 4)
3
sage: w.longest_forward_extension(0, 2)
0

Python

>>> from sage.all import *
>>> w = Word('0011001')
>>> w.longest_forward_extension(Integer(0), Integer(4))
3
>>> w.longest_forward_extension(Integer(0), Integer(2))
0

The method also accepts negative positions indicating the distance from the end of the word (in order to be consist with how negative indices work with lists). For instance, for a word of length \(7\), using positions \(-3\) and \(2\) is the same as using positions \(4\) and \(2\):

Sage

sage: w.longest_forward_extension(1, -2)
2
sage: w.longest_forward_extension(4, -3)
3

Python

>>> from sage.all import *
>>> w.longest_forward_extension(Integer(1), -Integer(2))
2
>>> w.longest_forward_extension(Integer(4), -Integer(3))
3

lps(f=None, l=None)[source]¶

Return the longest palindromic (or f-palindromic) suffix of self.

INPUT:

f – involution (default: None) on the alphabet of self. It must be callable on letters as well as words (e.g. WordMorphism)
l – integer (default: None); the length of the longest palindrome suffix of self[:-1], if known

OUTPUT: word; if f is None, the longest palindromic suffix of self. Otherwise, the longest f-palindromic suffix of self.

EXAMPLES:

Sage

sage: Word('0111').lps()
word: 111
sage: Word('011101').lps()
word: 101
sage: Word('6667').lps()
word: 7
sage: Word('abbabaab').lps()
word: baab
sage: Word().lps()
word:
sage: f = WordMorphism('a->b,b->a')
sage: Word('abbabaab').lps(f=f)
word: abbabaab
sage: w = Word('33412321')
sage: w.lps(l=3)
word: 12321
sage: Y = Word
sage: w = Y('01101001')
sage: w.lps(l=2)
word: 1001
sage: w.lps()
word: 1001
sage: w.lps(l=None)
word: 1001
sage: Y().lps(l=2)
Traceback (most recent call last):
...
IndexError: list index out of range
sage: v = Word('abbabaab')
sage: pal = v[:0]
sage: for i in range(1, v.length()+1):
....:   pal = v[:i].lps(l=pal.length())
....:   pal
word: a
word: b
word: bb
word: abba
word: bab
word: aba
word: aa
word: baab
sage: f = WordMorphism('a->b,b->a')
sage: v = Word('abbabaab')
sage: pal = v[:0]
sage: for i in range(1, v.length()+1):
....:   pal = v[:i].lps(f=f, l=pal.length())
....:   pal
word:
word: ab
word:
word: ba
word: ab
word: baba
word: bbabaa
word: abbabaab

Python

>>> from sage.all import *
>>> Word('0111').lps()
word: 111
>>> Word('011101').lps()
word: 101
>>> Word('6667').lps()
word: 7
>>> Word('abbabaab').lps()
word: baab
>>> Word().lps()
word:
>>> f = WordMorphism('a->b,b->a')
>>> Word('abbabaab').lps(f=f)
word: abbabaab
>>> w = Word('33412321')
>>> w.lps(l=Integer(3))
word: 12321
>>> Y = Word
>>> w = Y('01101001')
>>> w.lps(l=Integer(2))
word: 1001
>>> w.lps()
word: 1001
>>> w.lps(l=None)
word: 1001
>>> Y().lps(l=Integer(2))
Traceback (most recent call last):
...
IndexError: list index out of range
>>> v = Word('abbabaab')
>>> pal = v[:Integer(0)]
>>> for i in range(Integer(1), v.length()+Integer(1)):
...   pal = v[:i].lps(l=pal.length())
...   pal
word: a
word: b
word: bb
word: abba
word: bab
word: aba
word: aa
word: baab
>>> f = WordMorphism('a->b,b->a')
>>> v = Word('abbabaab')
>>> pal = v[:Integer(0)]
>>> for i in range(Integer(1), v.length()+Integer(1)):
...   pal = v[:i].lps(f=f, l=pal.length())
...   pal
word:
word: ab
word:
word: ba
word: ab
word: baba
word: bbabaa
word: abbabaab

lps_lengths(f=None)[source]¶

Return the length of the longest palindromic suffix of each prefix.

INPUT:

f – involution (default: None) on the alphabet of self. It must be callable on letters as well as words (e.g. WordMorphism).

OUTPUT: list; the length of the longest palindromic (or f-palindromic) suffix of each prefix of self

EXAMPLES:

Sage

sage: Word('01101001').lps_lengths()
[0, 1, 1, 2, 4, 3, 3, 2, 4]
sage: Word('00000').lps_lengths()
[0, 1, 2, 3, 4, 5]
sage: Word('0').lps_lengths()
[0, 1]
sage: Word('').lps_lengths()
[0]
sage: Word().lps_lengths()
[0]
sage: f = WordMorphism('a->b,b->a')
sage: Word('abbabaab').lps_lengths(f)
[0, 0, 2, 0, 2, 2, 4, 6, 8]

Python

>>> from sage.all import *
>>> Word('01101001').lps_lengths()
[0, 1, 1, 2, 4, 3, 3, 2, 4]
>>> Word('00000').lps_lengths()
[0, 1, 2, 3, 4, 5]
>>> Word('0').lps_lengths()
[0, 1]
>>> Word('').lps_lengths()
[0]
>>> Word().lps_lengths()
[0]
>>> f = WordMorphism('a->b,b->a')
>>> Word('abbabaab').lps_lengths(f)
[0, 0, 2, 0, 2, 2, 4, 6, 8]

lyndon_factorization()[source]¶

Return the Lyndon factorization of self.

The Lyndon factorization of a finite word \(w\) is the unique factorization of \(w\) as a non-increasing product of Lyndon words, i.e., \(w = l_1\cdots l_n\) where each \(l_i\) is a Lyndon word and \(l_1\geq \cdots \geq l_n\). See for instance [Duv1983].

OUTPUT: the list \([l_1, \ldots, l_n]\) of factors obtained

EXAMPLES:

Sage

sage: Word('010010010001000').lyndon_factorization()
(01, 001, 001, 0001, 0, 0, 0)
sage: Words('10')('010010010001000').lyndon_factorization()
(0, 10010010001000)
sage: Word('abbababbaababba').lyndon_factorization()
(abb, ababb, aababb, a)
sage: Words('ba')('abbababbaababba').lyndon_factorization()
(a, bbababbaaba, bba)
sage: Word([1,2,1,3,1,2,1]).lyndon_factorization()
(1213, 12, 1)

Python

>>> from sage.all import *
>>> Word('010010010001000').lyndon_factorization()
(01, 001, 001, 0001, 0, 0, 0)
>>> Words('10')('010010010001000').lyndon_factorization()
(0, 10010010001000)
>>> Word('abbababbaababba').lyndon_factorization()
(abb, ababb, aababb, a)
>>> Words('ba')('abbababbaababba').lyndon_factorization()
(a, bbababbaaba, bba)
>>> Word([Integer(1),Integer(2),Integer(1),Integer(3),Integer(1),Integer(2),Integer(1)]).lyndon_factorization()
(1213, 12, 1)

major_index(final_descent=False)[source]¶

Return the major index of self.

The major index of a word \(w\) is the sum of the descents of \(w\).

With the final_descent option, the last position of a non-empty word is also considered as a descent.

See also

major index on Permutations.

EXAMPLES:

Sage

sage: w = Word([2,1,3,3,2])
sage: w.major_index()
5
sage: w = Word([2,1,3,3,2])
sage: w.major_index(final_descent=True)
10

Python

>>> from sage.all import *
>>> w = Word([Integer(2),Integer(1),Integer(3),Integer(3),Integer(2)])
>>> w.major_index()
5
>>> w = Word([Integer(2),Integer(1),Integer(3),Integer(3),Integer(2)])
>>> w.major_index(final_descent=True)
10

minimal_conjugate()[source]¶

Return the lexicographically minimal conjugate of this word (see Wikipedia article Lexicographically_minimal_string_rotation).

EXAMPLES:

Sage

sage: Word('213').minimal_conjugate()
word: 132
sage: Word('11').minimal_conjugate()
word: 11
sage: Word('12112').minimal_conjugate()
word: 11212
sage: Word('211').minimal_conjugate()
word: 112
sage: Word('211211211').minimal_conjugate()
word: 112112112

Python

>>> from sage.all import *
>>> Word('213').minimal_conjugate()
word: 132
>>> Word('11').minimal_conjugate()
word: 11
>>> Word('12112').minimal_conjugate()
word: 11212
>>> Word('211').minimal_conjugate()
word: 112
>>> Word('211211211').minimal_conjugate()
word: 112112112

minimal_period()[source]¶

Return the period of self.

Let \(A\) be an alphabet. An integer \(p\geq 1\) is a period of a word \(w=a_1a_2\cdots a_n\) where \(a_i\in A\) if \(a_i=a_{i+p}\) for \(i=1,\ldots,n-p\). The smallest period of \(w\) is called the period of \(w\). See Chapter 1 of [Lot2002].

EXAMPLES:

Sage

sage: Word('aba').minimal_period()
2
sage: Word('abab').minimal_period()
2
sage: Word('ababa').minimal_period()
2
sage: Word('ababaa').minimal_period()
5
sage: Word('ababac').minimal_period()
6
sage: Word('aaaaaa').minimal_period()
1
sage: Word('a').minimal_period()
1
sage: Word().minimal_period()
1

Python

>>> from sage.all import *
>>> Word('aba').minimal_period()
2
>>> Word('abab').minimal_period()
2
>>> Word('ababa').minimal_period()
2
>>> Word('ababaa').minimal_period()
5
>>> Word('ababac').minimal_period()
6
>>> Word('aaaaaa').minimal_period()
1
>>> Word('a').minimal_period()
1
>>> Word().minimal_period()
1

nb_factor_occurrences_in(other)[source]¶

Return the number of times self appears as a factor in other.

Warning

This method is deprecated since 2020 and will be removed in a later version of SageMath. Use number_of_factor_occurrences() instead.

EXAMPLES:

Sage

sage: Word('123').nb_factor_occurrences_in(Word('112332312313112332121123'))
doctest:warning
...
DeprecationWarning: f.nb_factor_occurrences_in(w) is deprecated.
Use w.number_of_factor_occurrences(f) instead.
See https://github.com/sagemath/sage/issues/30187 for details.
4
sage: Word('321').nb_factor_occurrences_in(Word('11233231231311233221123'))
0

Python

>>> from sage.all import *
>>> Word('123').nb_factor_occurrences_in(Word('112332312313112332121123'))
doctest:warning
...
DeprecationWarning: f.nb_factor_occurrences_in(w) is deprecated.
Use w.number_of_factor_occurrences(f) instead.
See https://github.com/sagemath/sage/issues/30187 for details.
4
>>> Word('321').nb_factor_occurrences_in(Word('11233231231311233221123'))
0

An error is raised for the empty word:

Sage

sage: Word().nb_factor_occurrences_in(Word('123'))
Traceback (most recent call last):
...
NotImplementedError: The factor must be non empty

Python

>>> from sage.all import *
>>> Word().nb_factor_occurrences_in(Word('123'))
Traceback (most recent call last):
...
NotImplementedError: The factor must be non empty

nb_subword_occurrences_in(other)[source]¶

Return the number of times self appears in other as a subword.

This corresponds to the notion of \(binomial coefficient\) of two finite words whose properties are presented in the chapter of Lothaire’s book written by Sakarovitch and Simon [Lot1997].

Warning

This method is deprecated since 2020 and will be removed in a later version of SageMath. Use number_of_subword_occurrences() instead.

INPUT:

other – finite word

EXAMPLES:

Sage

sage: tm = words.ThueMorseWord()

sage: u = Word([0,1,0,1])
sage: u.nb_subword_occurrences_in(tm[:1000])
doctest:warning
...
DeprecationWarning: f.nb_subword_occurrences_in(w) is deprecated.
Use w.number_of_subword_occurrences(f) instead.
See https://github.com/sagemath/sage/issues/30187 for details.
2604124996

sage: u = Word([0,1,0,1,1,0])
sage: u.nb_subword_occurrences_in(tm[:100])
20370432

Python

>>> from sage.all import *
>>> tm = words.ThueMorseWord()

>>> u = Word([Integer(0),Integer(1),Integer(0),Integer(1)])
>>> u.nb_subword_occurrences_in(tm[:Integer(1000)])
doctest:warning
...
DeprecationWarning: f.nb_subword_occurrences_in(w) is deprecated.
Use w.number_of_subword_occurrences(f) instead.
See https://github.com/sagemath/sage/issues/30187 for details.
2604124996

>>> u = Word([Integer(0),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0)])
>>> u.nb_subword_occurrences_in(tm[:Integer(100)])
20370432

Note

This code, based on [MSSY2001], actually compute the number of occurrences of all prefixes of self as subwords in all prefixes of other. In particular, its complexity is bounded by len(self) * len(other).

number_of_factor_occurrences(other)[source]¶

Return the number of times other appears as a factor in self.

INPUT:

other – a non empty word

EXAMPLES:

Sage

sage: w = Word('112332312313112332121123')
sage: w.number_of_factor_occurrences(Word('123'))
4
sage: w = Word('11233231231311233221123')
sage: w.number_of_factor_occurrences(Word('321'))
0

Python

>>> from sage.all import *
>>> w = Word('112332312313112332121123')
>>> w.number_of_factor_occurrences(Word('123'))
4
>>> w = Word('11233231231311233221123')
>>> w.number_of_factor_occurrences(Word('321'))
0

Sage

sage: Word().number_of_factor_occurrences(Word('123'))
0

Python

>>> from sage.all import *
>>> Word().number_of_factor_occurrences(Word('123'))
0

An error is raised for the empty word:

Sage

sage: Word('123').number_of_factor_occurrences(Word())
Traceback (most recent call last):
...
NotImplementedError: The factor must be non empty

Python

>>> from sage.all import *
>>> Word('123').number_of_factor_occurrences(Word())
Traceback (most recent call last):
...
NotImplementedError: The factor must be non empty

number_of_factors(n=None, algorithm='suffix tree')[source]¶

Count the number of distinct factors of self.

INPUT:

n – integer or None
algorithm – string (default: 'suffix tree'); takes the following values:
- 'suffix tree' – construct and use the suffix tree of the word
- 'naive' – algorithm uses a sliding window

OUTPUT:

If n is an integer, returns the number of distinct factors of length n. If n is None, returns the total number of distinct factors.

EXAMPLES:

Sage

sage: w = Word([1,2,1,2,3])
sage: w.number_of_factors()
13
sage: [w.number_of_factors(i) for i in range(6)]
[1, 3, 3, 3, 2, 1]

Python

>>> from sage.all import *
>>> w = Word([Integer(1),Integer(2),Integer(1),Integer(2),Integer(3)])
>>> w.number_of_factors()
13
>>> [w.number_of_factors(i) for i in range(Integer(6))]
[1, 3, 3, 3, 2, 1]

Sage

sage: w = words.ThueMorseWord()[:100]
sage: [w.number_of_factors(i) for i in range(10)]
[1, 2, 4, 6, 10, 12, 16, 20, 22, 24]

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()[:Integer(100)]
>>> [w.number_of_factors(i) for i in range(Integer(10))]
[1, 2, 4, 6, 10, 12, 16, 20, 22, 24]

Sage

sage: Word('1213121').number_of_factors()
22
sage: Word('1213121').number_of_factors(1)
3

Python

>>> from sage.all import *
>>> Word('1213121').number_of_factors()
22
>>> Word('1213121').number_of_factors(Integer(1))
3

Sage

sage: Word('a'*100).number_of_factors()
101
sage: Word('a'*100).number_of_factors(77)
1

Python

>>> from sage.all import *
>>> Word('a'*Integer(100)).number_of_factors()
101
>>> Word('a'*Integer(100)).number_of_factors(Integer(77))
1

Sage

sage: Word().number_of_factors()
1
sage: Word().number_of_factors(17)
0

Python

>>> from sage.all import *
>>> Word().number_of_factors()
1
>>> Word().number_of_factors(Integer(17))
0

Sage

sage: blueberry = Word("blueberry")
sage: blueberry.number_of_factors()
43
sage: [blueberry.number_of_factors(i) for i in range(10)]
[1, 6, 8, 7, 6, 5, 4, 3, 2, 1]

Python

>>> from sage.all import *
>>> blueberry = Word("blueberry")
>>> blueberry.number_of_factors()
43
>>> [blueberry.number_of_factors(i) for i in range(Integer(10))]
[1, 6, 8, 7, 6, 5, 4, 3, 2, 1]

number_of_inversions()[source]¶

Return the number of inversions in self.

An inversion of a word \(w = w_1 \ldots w_n\) is a pair of indices \((i, j)\) with \(i < j\) and \(w_i > w_j\).

See also

number of inversions on Permutations.

EXAMPLES:

Sage

sage: w = Word([2,1,3,3,2])
sage: w.number_of_inversions()
3

Python

>>> from sage.all import *
>>> w = Word([Integer(2),Integer(1),Integer(3),Integer(3),Integer(2)])
>>> w.number_of_inversions()
3

number_of_left_special_factors(n)[source]¶

Return the number of left special factors of length \(n\).

A factor \(u\) of a word \(w\) is left special if there are two distinct letters \(a\) and \(b\) such that \(au\) and \(bu\) are factors of \(w\).

INPUT:

n – integer

OUTPUT: nonnegative integer

EXAMPLES:

Sage

sage: w = words.FibonacciWord()[:100]
sage: [w.number_of_left_special_factors(i) for i in range(10)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Python

>>> from sage.all import *
>>> w = words.FibonacciWord()[:Integer(100)]
>>> [w.number_of_left_special_factors(i) for i in range(Integer(10))]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Sage

sage: w = words.ThueMorseWord()[:100]
sage: [w.number_of_left_special_factors(i) for i in range(10)]
[1, 2, 2, 4, 2, 4, 4, 2, 2, 4]

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()[:Integer(100)]
>>> [w.number_of_left_special_factors(i) for i in range(Integer(10))]
[1, 2, 2, 4, 2, 4, 4, 2, 2, 4]

number_of_letter_occurrences(letter)[source]¶

Return the number of occurrences of letter in self.

INPUT:

letter – a letter

OUTPUT: integer

EXAMPLES:

Sage

sage: w = Word('abbabaab')
sage: w.number_of_letter_occurrences('a')
4
sage: w.number_of_letter_occurrences('ab')
0

Python

>>> from sage.all import *
>>> w = Word('abbabaab')
>>> w.number_of_letter_occurrences('a')
4
>>> w.number_of_letter_occurrences('ab')
0

This methods is equivalent to list(w).count(letter) and tuple(w).count(letter), thus count is an alias for the method number_of_letter_occurrences:

Sage

sage: list(w).count('a')
4
sage: w.count('a')
4

Python

>>> from sage.all import *
>>> list(w).count('a')
4
>>> w.count('a')
4

Sage

sage: s = 'abbabaab'
sage: s.count('ab')
3
sage: Word(s).count('ab')
0

Python

>>> from sage.all import *
>>> s = 'abbabaab'
>>> s.count('ab')
3
>>> Word(s).count('ab')
0

number_of_right_special_factors(n)[source]¶

Return the number of right special factors of length n.

A factor \(u\) of a word \(w\) is right special if there are two distinct letters \(a\) and \(b\) such that \(ua\) and \(ub\) are factors of \(w\).

INPUT:

n – integer

OUTPUT: nonnegative integer

EXAMPLES:

Sage

sage: w = words.FibonacciWord()[:100]
sage: [w.number_of_right_special_factors(i) for i in range(10)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Python

>>> from sage.all import *
>>> w = words.FibonacciWord()[:Integer(100)]
>>> [w.number_of_right_special_factors(i) for i in range(Integer(10))]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Sage

sage: w = words.ThueMorseWord()[:100]
sage: [w.number_of_right_special_factors(i) for i in range(10)]
[1, 2, 2, 4, 2, 4, 4, 2, 2, 4]

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()[:Integer(100)]
>>> [w.number_of_right_special_factors(i) for i in range(Integer(10))]
[1, 2, 2, 4, 2, 4, 4, 2, 2, 4]

number_of_subword_occurrences(other)[source]¶

Return the number of times other appears in self as a subword.

This corresponds to the notion of \(binomial coefficient\) of two finite words whose properties are presented in the chapter of Lothaire’s book written by Sakarovitch and Simon [Lot1997].

INPUT:

other – finite word

EXAMPLES:

Sage

sage: tm = words.ThueMorseWord()
sage: u = Word([0,1,0,1])
sage: tm[:1000].number_of_subword_occurrences(u)
2604124996

sage: u = Word([0,1,0,1,1,0])
sage: tm[:100].number_of_subword_occurrences(u)
20370432

Python

>>> from sage.all import *
>>> tm = words.ThueMorseWord()
>>> u = Word([Integer(0),Integer(1),Integer(0),Integer(1)])
>>> tm[:Integer(1000)].number_of_subword_occurrences(u)
2604124996

>>> u = Word([Integer(0),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0)])
>>> tm[:Integer(100)].number_of_subword_occurrences(u)
20370432

Note

order()[source]¶

Return the order of self.

Let \(p(w)\) be the period of a word \(w\). The positive rational number \(|w|/p(w)\) is the order of \(w\). See Chapter 8 of [Lot2002].

OUTPUT: rational; the order

EXAMPLES:

Sage

sage: Word('abaaba').order()
2
sage: Word('ababaaba').order()
8/5
sage: Word('a').order()
1
sage: Word('aa').order()
2
sage: Word().order()
0

Python

>>> from sage.all import *
>>> Word('abaaba').order()
2
>>> Word('ababaaba').order()
8/5
>>> Word('a').order()
1
>>> Word('aa').order()
2
>>> Word().order()
0

overlap_partition(other, delay=0, p=None, involution=None)[source]¶

Return the partition of the alphabet induced by the overlap of self and other with the given delay.

The partition of the alphabet is given by the equivalence relation obtained from the symmetric, reflexive and transitive closure of the set of pairs of letters \(R_{u,v,d} = \{ (u_k, v_{k-d}) : 0 \leq k < n, 0\leq k-d < m \}\) where \(u = u_0 u_1 \cdots u_{n-1}\), \(v = v_0v_1\cdots v_{m-1}\) are two words on the alphabet \(A\) and \(d\) is an integer.

The equivalence relation defined by \(R\) is inspired from [Lab2008].

INPUT:

other – word on the same alphabet as self
delay – integer (default: \(0\))
p – disjoint sets data structure (default: None), a partition of the alphabet into disjoint sets to start with. If None, each letter start in distinct equivalence classes.
involution – callable (default: None); an involution on the alphabet. If involution is not None, the relation \(R_{u,v,d} \cup R_{involution(u),involution(v),d}\) is considered.

OUTPUT: a disjoint set data structure

EXAMPLES:

Sage

sage: W = Words(list('abc012345'))
sage: u = W('abc')
sage: v = W('01234')
sage: u.overlap_partition(v)
{{'0', 'a'}, {'1', 'b'}, {'2', 'c'}, {'3'}, {'4'}, {'5'}}
sage: u.overlap_partition(v, 2)
{{'0', 'c'}, {'1'}, {'2'}, {'3'}, {'4'}, {'5'}, {'a'}, {'b'}}
sage: u.overlap_partition(v, -1)
{{'0'}, {'1', 'a'}, {'2', 'b'}, {'3', 'c'}, {'4'}, {'5'}}

Python

>>> from sage.all import *
>>> W = Words(list('abc012345'))
>>> u = W('abc')
>>> v = W('01234')
>>> u.overlap_partition(v)
{{'0', 'a'}, {'1', 'b'}, {'2', 'c'}, {'3'}, {'4'}, {'5'}}
>>> u.overlap_partition(v, Integer(2))
{{'0', 'c'}, {'1'}, {'2'}, {'3'}, {'4'}, {'5'}, {'a'}, {'b'}}
>>> u.overlap_partition(v, -Integer(1))
{{'0'}, {'1', 'a'}, {'2', 'b'}, {'3', 'c'}, {'4'}, {'5'}}

You can re-use the same disjoint set and do more than one overlap:

Sage

sage: p = u.overlap_partition(v, 2)
sage: p
{{'0', 'c'}, {'1'}, {'2'}, {'3'}, {'4'}, {'5'}, {'a'}, {'b'}}
sage: u.overlap_partition(v, 1, p)
{{'0', '1', 'b', 'c'}, {'2'}, {'3'}, {'4'}, {'5'}, {'a'}}

Python

>>> from sage.all import *
>>> p = u.overlap_partition(v, Integer(2))
>>> p
{{'0', 'c'}, {'1'}, {'2'}, {'3'}, {'4'}, {'5'}, {'a'}, {'b'}}
>>> u.overlap_partition(v, Integer(1), p)
{{'0', '1', 'b', 'c'}, {'2'}, {'3'}, {'4'}, {'5'}, {'a'}}

The function overlap_partition can be used to study equations on words. For example, if a word \(w\) overlaps itself with delay \(d\), then \(d\) is a period of \(w\):

Sage

sage: W = Words(range(20))
sage: w = W(range(14)); w
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13
sage: d = 5
sage: p = w.overlap_partition(w, d)
sage: m = WordMorphism(p.element_to_root_dict())
sage: w2 = m(w); w2
word: 56789567895678
sage: w2.minimal_period() == d
True

Python

>>> from sage.all import *
>>> W = Words(range(Integer(20)))
>>> w = W(range(Integer(14))); w
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13
>>> d = Integer(5)
>>> p = w.overlap_partition(w, d)
>>> m = WordMorphism(p.element_to_root_dict())
>>> w2 = m(w); w2
word: 56789567895678
>>> w2.minimal_period() == d
True

If a word is equal to its reversal, then it is a palindrome:

Sage

sage: W = Words(range(20))
sage: w = W(range(17)); w
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
sage: p = w.overlap_partition(w.reversal(), 0)
sage: m = WordMorphism(p.element_to_root_dict())
sage: w2 = m(w); w2
word: 01234567876543210
sage: w2.parent()
Finite words over {0, 1, 2, 3, 4, 5, 6, 7, 8, 17, 18, 19}
sage: w2.is_palindrome()
True

Python

>>> from sage.all import *
>>> W = Words(range(Integer(20)))
>>> w = W(range(Integer(17))); w
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
>>> p = w.overlap_partition(w.reversal(), Integer(0))
>>> m = WordMorphism(p.element_to_root_dict())
>>> w2 = m(w); w2
word: 01234567876543210
>>> w2.parent()
Finite words over {0, 1, 2, 3, 4, 5, 6, 7, 8, 17, 18, 19}
>>> w2.is_palindrome()
True

If the reversal of a word \(w\) is factor of its square \(w^2\), then \(w\) is symmetric, i.e. the product of two palindromes:

Sage

sage: W = Words(range(10))
sage: w = W(range(10)); w
word: 0123456789
sage: p = (w*w).overlap_partition(w.reversal(), 4)
sage: m = WordMorphism(p.element_to_root_dict())
sage: w2 = m(w); w2
word: 0110456654
sage: w2.is_symmetric()
True

Python

>>> from sage.all import *
>>> W = Words(range(Integer(10)))
>>> w = W(range(Integer(10))); w
word: 0123456789
>>> p = (w*w).overlap_partition(w.reversal(), Integer(4))
>>> m = WordMorphism(p.element_to_root_dict())
>>> w2 = m(w); w2
word: 0110456654
>>> w2.is_symmetric()
True

If the image of the reversal of a word \(w\) under an involution \(f\) is factor of its square \(w^2\), then \(w\) is \(f\)-symmetric:

Sage

sage: W = Words([-11,-9,..,11])
sage: w = W([1,3,..,11])
sage: w
word: 1,3,5,7,9,11
sage: inv = lambda x:-x
sage: f = WordMorphism(dict( (a, inv(a)) for a in W.alphabet()))
sage: p = (w*w).overlap_partition(f(w).reversal(), 2, involution=f)
sage: m = WordMorphism(p.element_to_root_dict())
sage: m(w)
word: 1,-1,5,7,-7,-5
sage: m(w).is_symmetric(f)
True

Python

>>> from sage.all import *
>>> W = Words((ellipsis_range(-Integer(11),-Integer(9),Ellipsis,Integer(11))))
>>> w = W((ellipsis_range(Integer(1),Integer(3),Ellipsis,Integer(11))))
>>> w
word: 1,3,5,7,9,11
>>> inv = lambda x:-x
>>> f = WordMorphism(dict( (a, inv(a)) for a in W.alphabet()))
>>> p = (w*w).overlap_partition(f(w).reversal(), Integer(2), involution=f)
>>> m = WordMorphism(p.element_to_root_dict())
>>> m(w)
word: 1,-1,5,7,-7,-5
>>> m(w).is_symmetric(f)
True

palindrome_prefixes()[source]¶

Return a list of all palindrome prefixes of self.

EXAMPLES:

Sage

sage: w = Word('abaaba')
sage: w.palindrome_prefixes()
[word: , word: a, word: aba, word: abaaba]
sage: w = Word('abbbbbbbbbb')
sage: w.palindrome_prefixes()
[word: , word: a]

Python

>>> from sage.all import *
>>> w = Word('abaaba')
>>> w.palindrome_prefixes()
[word: , word: a, word: aba, word: abaaba]
>>> w = Word('abbbbbbbbbb')
>>> w.palindrome_prefixes()
[word: , word: a]

palindromes(f=None)[source]¶

Return the set of all palindromic (or f-palindromic) factors of self.

INPUT:

f – involution (default: None) on the alphabet of self; it must be callable on letters as well as words (e.g. WordMorphism).

OUTPUT: a set – If f is None, the set of all palindromic factors of self; otherwise, the set of all f-palindromic factors of self

EXAMPLES:

Sage

sage: sorted(Word('01101001').palindromes())
[word: , word: 0, word: 00, word: 010, word: 0110, word: 1, word: 1001, word: 101, word: 11]
sage: sorted(Word('00000').palindromes())
[word: , word: 0, word: 00, word: 000, word: 0000, word: 00000]
sage: sorted(Word('0').palindromes())
[word: , word: 0]
sage: sorted(Word('').palindromes())
[word: ]
sage: sorted(Word().palindromes())
[word: ]
sage: f = WordMorphism('a->b,b->a')
sage: sorted(Word('abbabaab').palindromes(f))
[word: , word: ab, word: abbabaab, word: ba, word: baba, word: bbabaa]

Python

>>> from sage.all import *
>>> sorted(Word('01101001').palindromes())
[word: , word: 0, word: 00, word: 010, word: 0110, word: 1, word: 1001, word: 101, word: 11]
>>> sorted(Word('00000').palindromes())
[word: , word: 0, word: 00, word: 000, word: 0000, word: 00000]
>>> sorted(Word('0').palindromes())
[word: , word: 0]
>>> sorted(Word('').palindromes())
[word: ]
>>> sorted(Word().palindromes())
[word: ]
>>> f = WordMorphism('a->b,b->a')
>>> sorted(Word('abbabaab').palindromes(f))
[word: , word: ab, word: abbabaab, word: ba, word: baba, word: bbabaa]

palindromic_closure(side='right', f=None)[source]¶

Return the shortest palindrome having self as a prefix (or as a suffix if side is 'left').

See [DeLuca2006].

INPUT:

side – 'right' or 'left' (default: 'right') the direction of the closure
f – involution (default: None) on the alphabet of self; it must be callable on letters as well as words (e.g. WordMorphism)

OUTPUT:

a word – If f is None, the right palindromic closure of self; otherwise, the right f-palindromic closure of self. If side is 'left', the left palindromic closure.

EXAMPLES:

Sage

sage: Word('1233').palindromic_closure()
word: 123321
sage: Word('12332').palindromic_closure()
word: 123321
sage: Word('0110343').palindromic_closure()
word: 01103430110
sage: Word('0110343').palindromic_closure(side='left')
word: 3430110343
sage: Word('01105678').palindromic_closure(side='left')
word: 876501105678
sage: w = Word('abbaba')
sage: w.palindromic_closure()
word: abbababba

Python

>>> from sage.all import *
>>> Word('1233').palindromic_closure()
word: 123321
>>> Word('12332').palindromic_closure()
word: 123321
>>> Word('0110343').palindromic_closure()
word: 01103430110
>>> Word('0110343').palindromic_closure(side='left')
word: 3430110343
>>> Word('01105678').palindromic_closure(side='left')
word: 876501105678
>>> w = Word('abbaba')
>>> w.palindromic_closure()
word: abbababba

Sage

sage: f = WordMorphism('a->b,b->a')
sage: w.palindromic_closure(f=f)
word: abbabaab
sage: w.palindromic_closure(f=f, side='left')
word: babaabbaba

Python

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a')
>>> w.palindromic_closure(f=f)
word: abbabaab
>>> w.palindromic_closure(f=f, side='left')
word: babaabbaba

palindromic_complexity(n)[source]¶

Return the number of distinct palindromic factors of length n of self.

INPUT:

n – the length of the factors

EXAMPLES:

Sage

sage: w = words.FibonacciWord()[:100]
sage: [w.palindromic_complexity(i) for i in range(20)]
[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]

Python

>>> from sage.all import *
>>> w = words.FibonacciWord()[:Integer(100)]
>>> [w.palindromic_complexity(i) for i in range(Integer(20))]
[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]

Sage

sage: w = words.ThueMorseWord()[:1000]
sage: [w.palindromic_complexity(i) for i in range(20)]
[1, 2, 2, 2, 2, 0, 4, 0, 4, 0, 4, 0, 4, 0, 2, 0, 2, 0, 4, 0]

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()[:Integer(1000)]
>>> [w.palindromic_complexity(i) for i in range(Integer(20))]
[1, 2, 2, 2, 2, 0, 4, 0, 4, 0, 4, 0, 4, 0, 2, 0, 2, 0, 4, 0]

palindromic_lacunas_study(f=None)[source]¶

Return interesting statistics about longest (f-)palindromic suffixes and lacunas of self (see [BMBL2008] and [BMBFLR2008]).

Note that a word \(w\) has at most \(|w| + 1\) different palindromic factors (see [DJP2001]). For \(f\)-palindromes (or pseudopalindromes or theta-palindromes), the maximum number of \(f\)-palindromic factors is \(|w|+1-g_f(w)\), where \(g_f(w)\) is the number of pairs \(\{a, f(a)\}\) such that \(a\) is a letter, \(a\) is not equal to \(f(a)\), and \(a\) or \(f(a)\) occurs in \(w\), see [Star2011].

INPUT:

f – involution (default: None) on the alphabet of self. It must be callable on letters as well as words (e.g. WordMorphism). The default value corresponds to usual palindromes, i.e., f equal to the identity.

OUTPUT:

list – list of the length of the longest palindromic suffix (lps) for each non-empty prefix of self
list – list of all the lacunas, i.e. positions where there is no unioccurrent lps
set – set of palindromic factors of self

EXAMPLES:

Sage

sage: a,b,c = Word('abbabaabbaab').palindromic_lacunas_study()
sage: a
[1, 1, 2, 4, 3, 3, 2, 4, 2, 4, 6, 8]
sage: b
[8, 9]
sage: c          # random order
set([word: , word: b, word: bab, word: abba, word: bb, word: aa, word: baabbaab, word: baab, word: aba, word: aabbaa, word: a])

Python

>>> from sage.all import *
>>> a,b,c = Word('abbabaabbaab').palindromic_lacunas_study()
>>> a
[1, 1, 2, 4, 3, 3, 2, 4, 2, 4, 6, 8]
>>> b
[8, 9]
>>> c          # random order
set([word: , word: b, word: bab, word: abba, word: bb, word: aa, word: baabbaab, word: baab, word: aba, word: aabbaa, word: a])

Sage

sage: f = WordMorphism('a->b,b->a')
sage: a,b,c = Word('abbabaab').palindromic_lacunas_study(f=f)
sage: a
[0, 2, 0, 2, 2, 4, 6, 8]
sage: b
[0, 2, 4]
sage: c           # random order
set([word: , word: ba, word: baba, word: ab, word: bbabaa, word: abbabaab])
sage: c == set([Word(), Word('ba'), Word('baba'), Word('ab'), Word('bbabaa'), Word('abbabaab')])
True

Python

>>> from sage.all import *
>>> f = WordMorphism('a->b,b->a')
>>> a,b,c = Word('abbabaab').palindromic_lacunas_study(f=f)
>>> a
[0, 2, 0, 2, 2, 4, 6, 8]
>>> b
[0, 2, 4]
>>> c           # random order
set([word: , word: ba, word: baba, word: ab, word: bbabaa, word: abbabaab])
>>> c == set([Word(), Word('ba'), Word('baba'), Word('ab'), Word('bbabaa'), Word('abbabaab')])
True

periods(divide_length=False)[source]¶

Return a list containing the periods of self between \(1\) and \(n - 1\), where \(n\) is the length of self.

INPUT:

divide_length – boolean (default: False); when set to True, then only periods that divide the length of self are considered

OUTPUT: list of positive integers

EXAMPLES:

Sage

sage: w = Word('ababab')
sage: w.periods()
[2, 4]
sage: w.periods(divide_length=True)
[2]
sage: w = Word('ababa')
sage: w.periods()
[2, 4]
sage: w.periods(divide_length=True)
[]

Python

>>> from sage.all import *
>>> w = Word('ababab')
>>> w.periods()
[2, 4]
>>> w.periods(divide_length=True)
[2]
>>> w = Word('ababa')
>>> w.periods()
[2, 4]
>>> w.periods(divide_length=True)
[]

phi()[source]¶

Apply the phi function to self and return the result. This is the word obtained by taking the first letter of the words obtained by iterating delta on self.

OUTPUT: a word – the result of the phi function

EXAMPLES:

Sage

sage: W = Words([1, 2])
sage: W([2,2,1,1,2,1,2,2,1,2,2,1,1,2]).phi()
word: 222222
sage: W([2,1,2,2,1,2,2,1,2,1]).phi()
word: 212113
sage: W().phi()
word:
sage: Word([2,1,2,2,1,2,2,1,2,1]).phi()
word: 212113
sage: Word([2,3,1,1,2,1,2,3,1,2,2,3,1,2]).phi()
word: 21215
sage: Word("aabbabaabaabba").phi()
word: a22222
sage: w = Word([2,3,1,1,2,1,2,3,1,2,2,3,1,2])

Python

>>> from sage.all import *
>>> W = Words([Integer(1), Integer(2)])
>>> W([Integer(2),Integer(2),Integer(1),Integer(1),Integer(2),Integer(1),Integer(2),Integer(2),Integer(1),Integer(2),Integer(2),Integer(1),Integer(1),Integer(2)]).phi()
word: 222222
>>> W([Integer(2),Integer(1),Integer(2),Integer(2),Integer(1),Integer(2),Integer(2),Integer(1),Integer(2),Integer(1)]).phi()
word: 212113
>>> W().phi()
word:
>>> Word([Integer(2),Integer(1),Integer(2),Integer(2),Integer(1),Integer(2),Integer(2),Integer(1),Integer(2),Integer(1)]).phi()
word: 212113
>>> Word([Integer(2),Integer(3),Integer(1),Integer(1),Integer(2),Integer(1),Integer(2),Integer(3),Integer(1),Integer(2),Integer(2),Integer(3),Integer(1),Integer(2)]).phi()
word: 21215
>>> Word("aabbabaabaabba").phi()
word: a22222
>>> w = Word([Integer(2),Integer(3),Integer(1),Integer(1),Integer(2),Integer(1),Integer(2),Integer(3),Integer(1),Integer(2),Integer(2),Integer(3),Integer(1),Integer(2)])

See [BL2003] and [BDLV2006].

phi_inv(W=None)[source]¶

Apply the inverse of the phi function to self.

INPUT:

self – a word over the integers
W – a parent object of words defined over integers

OUTPUT: a word – the inverse of the phi function

EXAMPLES:

Sage

sage: W = Words([1, 2])
sage: W([2, 2, 2, 2, 1, 2]).phi_inv()
word: 22112122
sage: W([2, 2, 2]).phi_inv(Words([2, 3]))
word: 2233

Python

>>> from sage.all import *
>>> W = Words([Integer(1), Integer(2)])
>>> W([Integer(2), Integer(2), Integer(2), Integer(2), Integer(1), Integer(2)]).phi_inv()
word: 22112122
>>> W([Integer(2), Integer(2), Integer(2)]).phi_inv(Words([Integer(2), Integer(3)]))
word: 2233

prefix_function_table()[source]¶

Return a vector containing the length of the proper prefix-suffixes for all the non-empty prefixes of self.

EXAMPLES:

Sage

sage: Word('121321').prefix_function_table()
[0, 0, 1, 0, 0, 1]
sage: Word('1241245').prefix_function_table()
[0, 0, 0, 1, 2, 3, 0]
sage: Word().prefix_function_table()
[]

Python

>>> from sage.all import *
>>> Word('121321').prefix_function_table()
[0, 0, 1, 0, 0, 1]
>>> Word('1241245').prefix_function_table()
[0, 0, 0, 1, 2, 3, 0]
>>> Word().prefix_function_table()
[]

primitive()[source]¶

Return the primitive of self.

EXAMPLES:

Sage

sage: Word('12312').primitive()
word: 12312
sage: Word('121212').primitive()
word: 12

Python

>>> from sage.all import *
>>> Word('12312').primitive()
word: 12312
>>> Word('121212').primitive()
word: 12

primitive_length()[source]¶

Return the length of the primitive of self.

EXAMPLES:

Sage

sage: Word('1231').primitive_length()
4
sage: Word('121212').primitive_length()
2

Python

>>> from sage.all import *
>>> Word('1231').primitive_length()
4
>>> Word('121212').primitive_length()
2

quasiperiods()[source]¶

Return the quasiperiods of self as a list ordered from shortest to longest.

Let \(w\) be a finite or infinite word. A quasiperiod of \(w\) is a proper factor \(u\) of \(w\) such that the occurrences of \(u\) in \(w\) entirely cover \(w\), i.e., every position of \(w\) falls within some occurrence of \(u\) in \(w\). See for instance [AE1993], [Mar2004], and [GLR2008].

EXAMPLES:

Sage

sage: Word('abaababaabaababaaba').quasiperiods()
[word: aba, word: abaaba, word: abaababaaba]
sage: Word('abaaba').quasiperiods()
[word: aba]
sage: Word('abacaba').quasiperiods()
[]

Python

>>> from sage.all import *
>>> Word('abaababaabaababaaba').quasiperiods()
[word: aba, word: abaaba, word: abaababaaba]
>>> Word('abaaba').quasiperiods()
[word: aba]
>>> Word('abacaba').quasiperiods()
[]

rauzy_graph(n)[source]¶

Return the Rauzy graph of the factors of length n of self.

The vertices are the factors of length \(n\) and there is an edge from \(u\) to \(v\) if \(ua = bv\) is a factor of length \(n+1\) for some letters \(a\) and \(b\).

INPUT:

n – integer

EXAMPLES:

Sage

sage: w = Word(range(10)); w
word: 0123456789
sage: g = w.rauzy_graph(3); g                                               # needs sage.graphs
Looped digraph on 8 vertices
sage: WordOptions(identifier='')
sage: g.vertices(sort=True)                                                 # needs sage.graphs
[012, 123, 234, 345, 456, 567, 678, 789]
sage: g.edges(sort=True)                                                    # needs sage.graphs
[(012, 123, 3),
 (123, 234, 4),
 (234, 345, 5),
 (345, 456, 6),
 (456, 567, 7),
 (567, 678, 8),
 (678, 789, 9)]
sage: WordOptions(identifier='word: ')

Python

>>> from sage.all import *
>>> w = Word(range(Integer(10))); w
word: 0123456789
>>> g = w.rauzy_graph(Integer(3)); g                                               # needs sage.graphs
Looped digraph on 8 vertices
>>> WordOptions(identifier='')
>>> g.vertices(sort=True)                                                 # needs sage.graphs
[012, 123, 234, 345, 456, 567, 678, 789]
>>> g.edges(sort=True)                                                    # needs sage.graphs
[(012, 123, 3),
 (123, 234, 4),
 (234, 345, 5),
 (345, 456, 6),
 (456, 567, 7),
 (567, 678, 8),
 (678, 789, 9)]
>>> WordOptions(identifier='word: ')

Sage

sage: f = words.FibonacciWord()[:100]
sage: f.rauzy_graph(8)                                                      # needs sage.graphs
Looped digraph on 9 vertices

Python

>>> from sage.all import *
>>> f = words.FibonacciWord()[:Integer(100)]
>>> f.rauzy_graph(Integer(8))                                                      # needs sage.graphs
Looped digraph on 9 vertices

Sage

sage: w = Word('1111111')
sage: g = w.rauzy_graph(3)                                                  # needs sage.graphs
sage: g.edges(sort=True)                                                    # needs sage.graphs
[(word: 111, word: 111, word: 1)]

Python

>>> from sage.all import *
>>> w = Word('1111111')
>>> g = w.rauzy_graph(Integer(3))                                                  # needs sage.graphs
>>> g.edges(sort=True)                                                    # needs sage.graphs
[(word: 111, word: 111, word: 1)]

Sage

sage: w = Word('111')
sage: for i in range(5): w.rauzy_graph(i)                                   # needs sage.graphs
Looped multi-digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 0 vertices

Python

>>> from sage.all import *
>>> w = Word('111')
>>> for i in range(Integer(5)): w.rauzy_graph(i)                                   # needs sage.graphs
Looped multi-digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 0 vertices

Multi-edges are allowed for the empty word:

Sage

sage: W = Words('abcde')
sage: w = W('abc')
sage: w.rauzy_graph(0)                                                      # needs sage.graphs
Looped multi-digraph on 1 vertex
sage: _.edges(sort=True)                                                    # needs sage.graphs
[(word: , word: , word: a),
 (word: , word: , word: b),
 (word: , word: , word: c)]

Python

>>> from sage.all import *
>>> W = Words('abcde')
>>> w = W('abc')
>>> w.rauzy_graph(Integer(0))                                                      # needs sage.graphs
Looped multi-digraph on 1 vertex
>>> _.edges(sort=True)                                                    # needs sage.graphs
[(word: , word: , word: a),
 (word: , word: , word: b),
 (word: , word: , word: c)]

reduced_rauzy_graph(n)[source]¶

Return the reduced Rauzy graph of order n of self.

INPUT:

n – nonnegative integer; every vertex of a reduced Rauzy graph of order n is a factor of length n of self

OUTPUT: a looped multi-digraph

DEFINITION:

For infinite periodic words (resp. for finite words of type \(u^i u[0:j]\)), the reduced Rauzy graph of order \(n\) (resp. for \(n\) smaller or equal to \((i-1)|u|+j\)) is the directed graph whose unique vertex is the prefix \(p\) of length \(n\) of self and which has an only edge which is a loop on \(p\) labelled by \(w[n+1:|w|] p\) where \(w\) is the unique return word to \(p\).

In other cases, it is the directed graph defined as followed. Let \(G_n\) be the Rauzy graph of order \(n\) of self. The vertices are the vertices of \(G_n\) that are either special or not prolongable to the right or to the left. For each couple (\(u\), \(v\)) of such vertices and each directed path in \(G_n\) from \(u\) to \(v\) that contains no other vertices that are special, there is an edge from \(u\) to \(v\) in the reduced Rauzy graph of order \(n\) whose label is the label of the path in \(G_n\).

Note

In the case of infinite recurrent non-periodic words, this definition corresponds to the following one that can be found in [BDLGZ2009] and [BPS2008] where a simple path is a path that begins with a special factor, ends with a special factor and contains no other vertices that are special:

The reduced Rauzy graph of factors of length \(n\) is obtained from \(G_n\) by replacing each simple path \(P=v_1 v_2 ... v_{\ell}\) with an edge \(v_1 v_{\ell}\) whose label is the concatenation of the labels of the edges of \(P\).

EXAMPLES:

Sage

sage: w = Word(range(10)); w
word: 0123456789
sage: g = w.reduced_rauzy_graph(3); g                                       # needs sage.graphs
Looped multi-digraph on 2 vertices
sage: g.vertices(sort=True)                                                 # needs sage.graphs
[word: 012, word: 789]
sage: g.edges(sort=True)                                                    # needs sage.graphs
[(word: 012, word: 789, word: 3456789)]

Python

>>> from sage.all import *
>>> w = Word(range(Integer(10))); w
word: 0123456789
>>> g = w.reduced_rauzy_graph(Integer(3)); g                                       # needs sage.graphs
Looped multi-digraph on 2 vertices
>>> g.vertices(sort=True)                                                 # needs sage.graphs
[word: 012, word: 789]
>>> g.edges(sort=True)                                                    # needs sage.graphs
[(word: 012, word: 789, word: 3456789)]

For the Fibonacci word:

Sage

sage: f = words.FibonacciWord()[:100]
sage: g = f.reduced_rauzy_graph(8);g                                        # needs sage.graphs
Looped multi-digraph on 2 vertices
sage: g.vertices(sort=True)                                                 # needs sage.graphs
[word: 01001010, word: 01010010]
sage: g.edges(sort=True)                                                    # needs sage.graphs
[(word: 01001010, word: 01010010, word: 010),
 (word: 01010010, word: 01001010, word: 01010),
 (word: 01010010, word: 01001010, word: 10)]

Python

>>> from sage.all import *
>>> f = words.FibonacciWord()[:Integer(100)]
>>> g = f.reduced_rauzy_graph(Integer(8));g                                        # needs sage.graphs
Looped multi-digraph on 2 vertices
>>> g.vertices(sort=True)                                                 # needs sage.graphs
[word: 01001010, word: 01010010]
>>> g.edges(sort=True)                                                    # needs sage.graphs
[(word: 01001010, word: 01010010, word: 010),
 (word: 01010010, word: 01001010, word: 01010),
 (word: 01010010, word: 01001010, word: 10)]

For periodic words:

Sage

sage: from itertools import cycle
sage: w = Word(cycle('abcd'))[:100]
sage: g = w.reduced_rauzy_graph(3)                                          # needs sage.graphs
sage: g.edges(sort=True)                                                    # needs sage.graphs
[(word: abc, word: abc, word: dabc)]

Python

>>> from sage.all import *
>>> from itertools import cycle
>>> w = Word(cycle('abcd'))[:Integer(100)]
>>> g = w.reduced_rauzy_graph(Integer(3))                                          # needs sage.graphs
>>> g.edges(sort=True)                                                    # needs sage.graphs
[(word: abc, word: abc, word: dabc)]

Sage

sage: w = Word('111')
sage: for i in range(5): w.reduced_rauzy_graph(i)                           # needs sage.graphs
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped multi-digraph on 1 vertex
Looped multi-digraph on 0 vertices

Python

>>> from sage.all import *
>>> w = Word('111')
>>> for i in range(Integer(5)): w.reduced_rauzy_graph(i)                           # needs sage.graphs
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped multi-digraph on 1 vertex
Looped multi-digraph on 0 vertices

For ultimately periodic words:

Sage

sage: sigma = WordMorphism('a->abcd,b->cd,c->cd,d->cd')
sage: w = sigma.fixed_point('a')[:100]; w                                   # needs sage.modules
word: abcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd...
sage: g = w.reduced_rauzy_graph(5)                                          # needs sage.graphs
sage: g.vertices(sort=True)                                                 # needs sage.graphs
[word: abcdc, word: cdcdc]
sage: g.edges(sort=True)                                                    # needs sage.graphs
[(word: abcdc, word: cdcdc, word: dc), (word: cdcdc, word: cdcdc, word: dc)]

Python

>>> from sage.all import *
>>> sigma = WordMorphism('a->abcd,b->cd,c->cd,d->cd')
>>> w = sigma.fixed_point('a')[:Integer(100)]; w                                   # needs sage.modules
word: abcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd...
>>> g = w.reduced_rauzy_graph(Integer(5))                                          # needs sage.graphs
>>> g.vertices(sort=True)                                                 # needs sage.graphs
[word: abcdc, word: cdcdc]
>>> g.edges(sort=True)                                                    # needs sage.graphs
[(word: abcdc, word: cdcdc, word: dc), (word: cdcdc, word: cdcdc, word: dc)]

AUTHOR:

Julien Leroy (March 2010): initial version

return_words(fact)[source]¶

Return the set of return words of fact in self.

This is the set of all factors starting by the given factor and ending just before the next occurrence of this factor. See [Dur1998] and [HZ1999].

INPUT:

fact – a non-empty finite word

OUTPUT: a Python set of finite words

EXAMPLES:

Sage

sage: Word('21331233213231').return_words(Word('2'))
{word: 213, word: 21331, word: 233}
sage: Word().return_words(Word('213'))
set()
sage: Word('121212').return_words(Word('1212'))
{word: 12}

Python

>>> from sage.all import *
>>> Word('21331233213231').return_words(Word('2'))
{word: 213, word: 21331, word: 233}
>>> Word().return_words(Word('213'))
set()
>>> Word('121212').return_words(Word('1212'))
{word: 12}

Sage

sage: TM = words.ThueMorseWord()[:1000]
sage: sorted(TM.return_words(Word([0])))
[word: 0, word: 01, word: 011]

Python

>>> from sage.all import *
>>> TM = words.ThueMorseWord()[:Integer(1000)]
>>> sorted(TM.return_words(Word([Integer(0)])))
[word: 0, word: 01, word: 011]

return_words_derivate(fact)[source]¶

Return the word generated by mapping a letter to each occurrence of the return words for the given factor dropping any dangling prefix and suffix. See for instance [Dur1998].

EXAMPLES:

Sage

sage: Word('12131221312313122').return_words_derivate(Word('1'))
word: 123242

Python

>>> from sage.all import *
>>> Word('12131221312313122').return_words_derivate(Word('1'))
word: 123242

rev_lex_less(other)[source]¶

Return True if the word self is reverse lexicographically less than other.

EXAMPLES:

Sage

sage: Word([1,2,4]).rev_lex_less(Word([1,3,2]))
True
sage: Word([3,2,1]).rev_lex_less(Word([1,2,3]))
False

Python

>>> from sage.all import *
>>> Word([Integer(1),Integer(2),Integer(4)]).rev_lex_less(Word([Integer(1),Integer(3),Integer(2)]))
True
>>> Word([Integer(3),Integer(2),Integer(1)]).rev_lex_less(Word([Integer(1),Integer(2),Integer(3)]))
False

reversal()[source]¶

Return the reversal of self.

EXAMPLES:

Sage

sage: Word('124563').reversal()
word: 365421

Python

>>> from sage.all import *
>>> Word('124563').reversal()
word: 365421

rfind(sub, start=0, end=None)[source]¶

Return the index of the last occurrence of sub in self, such that sub is contained within self[start:end]. Return -1 on failure.

INPUT:

sub – string, list, tuple or word to search for
start – nonnegative integer (default: \(0\)); specifying the position at which the search must stop
end – nonnegative integer (default: None); specifying the position from which to start the search. If None, then the search is performed up to the end of the string.

OUTPUT: nonnegative integer or \(-1\)

EXAMPLES:

Sage

sage: w = Word([0,1,0,0,1])
sage: w.rfind(Word([0,1]))
3

Python

>>> from sage.all import *
>>> w = Word([Integer(0),Integer(1),Integer(0),Integer(0),Integer(1)])
>>> w.rfind(Word([Integer(0),Integer(1)]))
3

The sub parameter can also be a list or a tuple:

Sage

sage: w.rfind([0,1])
3
sage: w.rfind((0,1))
3

Python

>>> from sage.all import *
>>> w.rfind([Integer(0),Integer(1)])
3
>>> w.rfind((Integer(0),Integer(1)))
3

Examples using the argument start and end:

Sage

sage: w.rfind(Word([0,1]), end=4)
0
sage: w.rfind(Word([0,1]), end=5)
3
sage: w.rfind(Word([0,0]), start=2, end=5)
2
sage: w.rfind(Word([0,0]), start=3, end=5)
-1

Python

>>> from sage.all import *
>>> w.rfind(Word([Integer(0),Integer(1)]), end=Integer(4))
0
>>> w.rfind(Word([Integer(0),Integer(1)]), end=Integer(5))
3
>>> w.rfind(Word([Integer(0),Integer(0)]), start=Integer(2), end=Integer(5))
2
>>> w.rfind(Word([Integer(0),Integer(0)]), start=Integer(3), end=Integer(5))
-1

Instances of Word_str handle string inputs as well:

Sage

sage: w = Word('abac')
sage: w.rfind('a')
2
sage: w.rfind(Word('a'))
2
sage: w.rfind([0,1])
-1

Python

>>> from sage.all import *
>>> w = Word('abac')
>>> w.rfind('a')
2
>>> w.rfind(Word('a'))
2
>>> w.rfind([Integer(0),Integer(1)])
-1

right_special_factors(n=None)[source]¶

Return the right special factors (of length n).

A factor \(u\) of a word \(w\) is right special if there are two distinct letters \(a\) and \(b\) such that \(ua\) and \(ub\) are factors of \(w\).

INPUT:

n – integer (default: None); if None, it returns all right special factors

OUTPUT: list of words

EXAMPLES:

Sage

sage: w = words.ThueMorseWord()[:30]
sage: for i in range(5):
....:     print("{} {}".format(i, sorted(w.right_special_factors(i))))
0 [word: ]
1 [word: 0, word: 1]
2 [word: 01, word: 10]
3 [word: 001, word: 010, word: 101, word: 110]
4 [word: 0110, word: 1001]

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()[:Integer(30)]
>>> for i in range(Integer(5)):
...     print("{} {}".format(i, sorted(w.right_special_factors(i))))
0 [word: ]
1 [word: 0, word: 1]
2 [word: 01, word: 10]
3 [word: 001, word: 010, word: 101, word: 110]
4 [word: 0110, word: 1001]

right_special_factors_iterator(n=None)[source]¶

Return an iterator over the right special factors (of length n).

A factor \(u\) of a word \(w\) is right special if there are two distinct letters \(a\) and \(b\) such that \(ua\) and \(ub\) are factors of \(w\).

INPUT:

n – integer (default: None); if None, it returns an iterator over all right special factors

EXAMPLES:

Sage

sage: alpha, beta, x = 0.61, 0.54, 0.3
sage: w = words.CodingOfRotationWord(alpha, beta, x)[:40]
sage: sorted(w.right_special_factors_iterator(3))
[word: 010, word: 101]
sage: sorted(w.right_special_factors_iterator(4))
[word: 0101, word: 1010]
sage: sorted(w.right_special_factors_iterator(5))
[word: 00101, word: 11010]

Python

>>> from sage.all import *
>>> alpha, beta, x = RealNumber('0.61'), RealNumber('0.54'), RealNumber('0.3')
>>> w = words.CodingOfRotationWord(alpha, beta, x)[:Integer(40)]
>>> sorted(w.right_special_factors_iterator(Integer(3)))
[word: 010, word: 101]
>>> sorted(w.right_special_factors_iterator(Integer(4)))
[word: 0101, word: 1010]
>>> sorted(w.right_special_factors_iterator(Integer(5)))
[word: 00101, word: 11010]

robinson_schensted()[source]¶

Return the semistandard tableau and standard tableau pair obtained by running the Robinson-Schensted algorithm on self.

This can also be done by running RSK() on self.

EXAMPLES:

Sage

sage: Word([1,1,3,1,2,3,1]).robinson_schensted()
[[[1, 1, 1, 1, 3], [2], [3]], [[1, 2, 3, 5, 6], [4], [7]]]

Python

>>> from sage.all import *
>>> Word([Integer(1),Integer(1),Integer(3),Integer(1),Integer(2),Integer(3),Integer(1)]).robinson_schensted()
[[[1, 1, 1, 1, 3], [2], [3]], [[1, 2, 3, 5, 6], [4], [7]]]

schuetzenberger_involution(n=None)[source]¶

Return the Schützenberger involution of the word self, which is obtained by reverting the word and then complementing all letters within the underlying ordered alphabet. If n is specified, the underlying alphabet is assumed to be \([1,2,\ldots,n]\). If no alphabet is specified, \(n\) is the maximal letter appearing in self.

INPUT:

self – a word
n – integer specifying the maximal letter in the alphabet (optional)

OUTPUT: a word, the Schützenberger involution of self

EXAMPLES:

Sage

sage: w = Word([9,7,4,1,6,2,3])
sage: v = w.schuetzenberger_involution(); v
word: 7849631
sage: v.parent()
Finite words over Set of Python objects of class 'object'

sage: w = Word([1,2,3],alphabet=[1,2,3,4,5])
sage: v = w.schuetzenberger_involution();v
word: 345
sage: v.parent()
Finite words over {1, 2, 3, 4, 5}

sage: w = Word([1,2,3])
sage: v = w.schuetzenberger_involution(n=5);v
word: 345
sage: v.parent()
Finite words over Set of Python objects of class 'object'

sage: w = Word([11,32,69,2,53,1,2,3,18,41])
sage: w.schuetzenberger_involution()
word: 29,52,67,68,69,17,68,1,38,59

sage: w = Word([],alphabet=[1,2,3,4,5])
sage: w.schuetzenberger_involution()
word:

sage: w = Word([])
sage: w.schuetzenberger_involution()
word:

Python

>>> from sage.all import *
>>> w = Word([Integer(9),Integer(7),Integer(4),Integer(1),Integer(6),Integer(2),Integer(3)])
>>> v = w.schuetzenberger_involution(); v
word: 7849631
>>> v.parent()
Finite words over Set of Python objects of class 'object'

>>> w = Word([Integer(1),Integer(2),Integer(3)],alphabet=[Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> v = w.schuetzenberger_involution();v
word: 345
>>> v.parent()
Finite words over {1, 2, 3, 4, 5}

>>> w = Word([Integer(1),Integer(2),Integer(3)])
>>> v = w.schuetzenberger_involution(n=Integer(5));v
word: 345
>>> v.parent()
Finite words over Set of Python objects of class 'object'

>>> w = Word([Integer(11),Integer(32),Integer(69),Integer(2),Integer(53),Integer(1),Integer(2),Integer(3),Integer(18),Integer(41)])
>>> w.schuetzenberger_involution()
word: 29,52,67,68,69,17,68,1,38,59

>>> w = Word([],alphabet=[Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> w.schuetzenberger_involution()
word:

>>> w = Word([])
>>> w.schuetzenberger_involution()
word:

shifted_shuffle(other, shift=None)[source]¶

Return the combinatorial class representing the shifted shuffle product between words self and other. This is the same as the shuffle product of self with the word obtained from other by incrementing its values (i.e. its letters) by the given shift.

INPUT:

other – finite word over the integers
shift – integer or None (default: None); added to each letter of other. When shift is None, it is replaced by self.length()

OUTPUT: combinatorial class of shifted shuffle products of self and other

EXAMPLES:

Sage

sage: w = Word([0,1,1])
sage: sp = w.shifted_shuffle(w); sp
Shuffle product of word: 011 and word: 344
sage: sp = w.shifted_shuffle(w, 2); sp
Shuffle product of word: 011 and word: 233
sage: sp.cardinality()
20
sage: WordOptions(identifier='')
sage: sp.list()
[011233, 012133, 012313, 012331, 021133, 021313, 021331, 023113, 023131, 023311, 201133, 201313, 201331, 203113, 203131, 203311, 230113, 230131, 230311, 233011]
sage: WordOptions(identifier='word: ')
sage: y = Word('aba')
sage: y.shifted_shuffle(w,2)
Traceback (most recent call last):
...
ValueError: for shifted shuffle, words must only contain integers as letters

Python

>>> from sage.all import *
>>> w = Word([Integer(0),Integer(1),Integer(1)])
>>> sp = w.shifted_shuffle(w); sp
Shuffle product of word: 011 and word: 344
>>> sp = w.shifted_shuffle(w, Integer(2)); sp
Shuffle product of word: 011 and word: 233
>>> sp.cardinality()
20
>>> WordOptions(identifier='')
>>> sp.list()
[011233, 012133, 012313, 012331, 021133, 021313, 021331, 023113, 023131, 023311, 201133, 201313, 201331, 203113, 203131, 203311, 230113, 230131, 230311, 233011]
>>> WordOptions(identifier='word: ')
>>> y = Word('aba')
>>> y.shifted_shuffle(w,Integer(2))
Traceback (most recent call last):
...
ValueError: for shifted shuffle, words must only contain integers as letters

shuffle(other, overlap=0)[source]¶

Return the combinatorial class representing the shuffle product between words self and other. This consists of all words of length self.length()+other.length() that have both self and other as subwords.

If overlap is nonzero, then the combinatorial class representing the shuffle product with overlaps is returned. The calculation of the shift in each overlap is done relative to the order of the alphabet. For example, \(a\) shifted by \(a\) is \(b\) in the alphabet \([a, b, c]\) and \(0\) shifted by \(1\) in \([0, 1, 2, 3]\) is \(2\).

INPUT:

other – finite word
overlap – (default: 0) integer or True

OUTPUT: combinatorial class of shuffle product of self and other

EXAMPLES:

Sage

sage: ab = Word("ab")
sage: cd = Word("cd")
sage: sp = ab.shuffle(cd); sp
Shuffle product of word: ab and word: cd
sage: sp.cardinality()
6
sage: sp.list()
[word: abcd, word: acbd, word: acdb, word: cabd, word: cadb, word: cdab]
sage: w = Word([0,1])
sage: u = Word([2,3])
sage: w.shuffle(w)
Shuffle product of word: 01 and word: 01
sage: u.shuffle(u)
Shuffle product of word: 23 and word: 23
sage: w.shuffle(u)
Shuffle product of word: 01 and word: 23
sage: sp2 = w.shuffle(u,2); sp2
Overlapping shuffle product of word: 01 and word: 23 with 2 overlaps
sage: list(sp2)
[word: 24]

Python

>>> from sage.all import *
>>> ab = Word("ab")
>>> cd = Word("cd")
>>> sp = ab.shuffle(cd); sp
Shuffle product of word: ab and word: cd
>>> sp.cardinality()
6
>>> sp.list()
[word: abcd, word: acbd, word: acdb, word: cabd, word: cadb, word: cdab]
>>> w = Word([Integer(0),Integer(1)])
>>> u = Word([Integer(2),Integer(3)])
>>> w.shuffle(w)
Shuffle product of word: 01 and word: 01
>>> u.shuffle(u)
Shuffle product of word: 23 and word: 23
>>> w.shuffle(u)
Shuffle product of word: 01 and word: 23
>>> sp2 = w.shuffle(u,Integer(2)); sp2
Overlapping shuffle product of word: 01 and word: 23 with 2 overlaps
>>> list(sp2)
[word: 24]

squares()[source]¶

Return a set of all distinct squares of self.

EXAMPLES:

Sage

sage: sorted(Word('cacao').squares())
[word: , word: caca]
sage: sorted(Word('1111').squares())
[word: , word: 11, word: 1111]
sage: w = Word('00110011010')
sage: sorted(w.squares())
[word: , word: 00, word: 00110011, word: 01100110, word: 1010, word: 11]

Python

>>> from sage.all import *
>>> sorted(Word('cacao').squares())
[word: , word: caca]
>>> sorted(Word('1111').squares())
[word: , word: 11, word: 1111]
>>> w = Word('00110011010')
>>> sorted(w.squares())
[word: , word: 00, word: 00110011, word: 01100110, word: 1010, word: 11]

standard_factorization()[source]¶

Return the standard factorization of self.

The standard factorization of a word \(w\) of length greater than \(1\) is the factorization \(w = uv\) where \(v\) is the longest proper suffix of \(w\) that is a Lyndon word.

Note that if \(w\) is a Lyndon word of length greater than \(1\) with standard factorization \(w = uv\), then \(u\) and \(v\) are also Lyndon words and \(u < v\).

See for instance [CFL1958], [Duv1983] and [Lot2002].

INPUT:

self – finite word of length greater than \(1\)

OUTPUT: \(2\)-tuple \((u, v)\)

EXAMPLES:

Sage

sage: Words('01')('0010110011').standard_factorization()
(word: 001011, word: 0011)
sage: Words('123')('1223312').standard_factorization()
(word: 12233, word: 12)
sage: Word([3,2,1]).standard_factorization()
(word: 32, word: 1)

Python

>>> from sage.all import *
>>> Words('01')('0010110011').standard_factorization()
(word: 001011, word: 0011)
>>> Words('123')('1223312').standard_factorization()
(word: 12233, word: 12)
>>> Word([Integer(3),Integer(2),Integer(1)]).standard_factorization()
(word: 32, word: 1)

Sage

sage: w = Word('0010110011',alphabet='01')
sage: w.standard_factorization()
(word: 001011, word: 0011)
sage: w = Word('0010110011',alphabet='10')
sage: w.standard_factorization()
(word: 001011001, word: 1)
sage: w = Word('1223312',alphabet='123')
sage: w.standard_factorization()
(word: 12233, word: 12)

Python

>>> from sage.all import *
>>> w = Word('0010110011',alphabet='01')
>>> w.standard_factorization()
(word: 001011, word: 0011)
>>> w = Word('0010110011',alphabet='10')
>>> w.standard_factorization()
(word: 001011001, word: 1)
>>> w = Word('1223312',alphabet='123')
>>> w.standard_factorization()
(word: 12233, word: 12)

standard_permutation()[source]¶

Return the standard permutation of the word self on the ordered alphabet. It is defined as the permutation with exactly the same inversions as self. Equivalently, it is the permutation of minimal length whose inverse sorts self.

EXAMPLES:

Sage

sage: w = Word([1,2,3,2,2,1]); w
word: 123221
sage: p = w.standard_permutation(); p
[1, 3, 6, 4, 5, 2]
sage: v = Word(p.inverse().action(w)); v
word: 112223
sage: [q for q in Permutations(w.length())
....:      if q.length() <= p.length() and
....:      q.inverse().action(w) == list(v)]
[[1, 3, 6, 4, 5, 2]]

Python

>>> from sage.all import *
>>> w = Word([Integer(1),Integer(2),Integer(3),Integer(2),Integer(2),Integer(1)]); w
word: 123221
>>> p = w.standard_permutation(); p
[1, 3, 6, 4, 5, 2]
>>> v = Word(p.inverse().action(w)); v
word: 112223
>>> [q for q in Permutations(w.length())
...      if q.length() <= p.length() and
...      q.inverse().action(w) == list(v)]
[[1, 3, 6, 4, 5, 2]]

Sage

sage: w = Words([1,2,3])([1,2,3,2,2,1,2,1]); w
word: 12322121
sage: p = w.standard_permutation(); p
[1, 4, 8, 5, 6, 2, 7, 3]
sage: Word(p.inverse().action(w))
word: 11122223

Python

>>> from sage.all import *
>>> w = Words([Integer(1),Integer(2),Integer(3)])([Integer(1),Integer(2),Integer(3),Integer(2),Integer(2),Integer(1),Integer(2),Integer(1)]); w
word: 12322121
>>> p = w.standard_permutation(); p
[1, 4, 8, 5, 6, 2, 7, 3]
>>> Word(p.inverse().action(w))
word: 11122223

Sage

sage: w = Words([3,2,1])([1,2,3,2,2,1,2,1]); w
word: 12322121
sage: p = w.standard_permutation(); p
[6, 2, 1, 3, 4, 7, 5, 8]
sage: Word(p.inverse().action(w))
word: 32222111

Python

>>> from sage.all import *
>>> w = Words([Integer(3),Integer(2),Integer(1)])([Integer(1),Integer(2),Integer(3),Integer(2),Integer(2),Integer(1),Integer(2),Integer(1)]); w
word: 12322121
>>> p = w.standard_permutation(); p
[6, 2, 1, 3, 4, 7, 5, 8]
>>> Word(p.inverse().action(w))
word: 32222111

Sage

sage: w = Words('ab')('abbaba'); w
word: abbaba
sage: p = w.standard_permutation(); p
[1, 4, 5, 2, 6, 3]
sage: Word(p.inverse().action(w))
word: aaabbb

Python

>>> from sage.all import *
>>> w = Words('ab')('abbaba'); w
word: abbaba
>>> p = w.standard_permutation(); p
[1, 4, 5, 2, 6, 3]
>>> Word(p.inverse().action(w))
word: aaabbb

Sage

sage: w = Words('ba')('abbaba'); w
word: abbaba
sage: p = w.standard_permutation(); p
[4, 1, 2, 5, 3, 6]
sage: Word(p.inverse().action(w))
word: bbbaaa

Python

>>> from sage.all import *
>>> w = Words('ba')('abbaba'); w
word: abbaba
>>> p = w.standard_permutation(); p
[4, 1, 2, 5, 3, 6]
>>> Word(p.inverse().action(w))
word: bbbaaa

sturmian_desubstitute_as_possible()[source]¶

Sturmian-desubstitute the word self as much as possible.

The finite word self must be defined on a two-letter alphabet or use at most two letters.

It can be Sturmian desubstituted if one letter appears isolated: the Sturmian desubstitution consists in removing one letter per run of the non-isolated letter. The accelerated Sturmian desubstitution consists in removing a run equal to the length of the shortest inner run from any run of the non-isolated letter (including possible leading and trailing runs even if they have shorter length). The (accelerated) Sturmian desubstitution is done as much as possible. A word is a factor of a Sturmian word if, and only if, the result is the empty word.

OUTPUT: a finite word defined on a two-letter alphabet

EXAMPLES:

Sage

sage: u = Word('10111101101110111',alphabet='01') ; u
word: 10111101101110111
sage: v = u.sturmian_desubstitute_as_possible() ; v
word: 01100101
sage: v == v.sturmian_desubstitute_as_possible()
True

sage: Word('azaazaaazaaazaazaaaz', alphabet='az').sturmian_desubstitute_as_possible()
word:

Python

>>> from sage.all import *
>>> u = Word('10111101101110111',alphabet='01') ; u
word: 10111101101110111
>>> v = u.sturmian_desubstitute_as_possible() ; v
word: 01100101
>>> v == v.sturmian_desubstitute_as_possible()
True

>>> Word('azaazaaazaaazaazaaaz', alphabet='az').sturmian_desubstitute_as_possible()
word:

AUTHOR:

Thierry Monteil

subword_complementaries(other)[source]¶

Return the possible complementaries other minus self if self is a subword of other (empty list otherwise). The complementary is made of all the letters that are in other once we removed the letters of self. There can be more than one.

To check whether self is a subword of other (without knowing its complementaries), use self.is_subword_of(other), and to count the number of occurrences of self in other, use other.number_of_subword_occurrences(self).

INPUT:

other – finite word

OUTPUT: list of all the complementary subwords of self in other

EXAMPLES:

Sage

sage: Word('tamtam').subword_complementaries(Word('ta'))
[]

sage: Word('mta').subword_complementaries(Word('tamtam'))
[word: tam]

sage: Word('ta').subword_complementaries(Word('tamtam'))
[word: mtam, word: amtm, word: tamm]

sage: Word('a').subword_complementaries(Word('a'))
[word: ]

Python

>>> from sage.all import *
>>> Word('tamtam').subword_complementaries(Word('ta'))
[]

>>> Word('mta').subword_complementaries(Word('tamtam'))
[word: tam]

>>> Word('ta').subword_complementaries(Word('tamtam'))
[word: mtam, word: amtm, word: tamm]

>>> Word('a').subword_complementaries(Word('a'))
[word: ]

suffix_tree()[source]¶

Alias for implicit_suffix_tree().

EXAMPLES:

Sage

sage: Word('abbabaab').suffix_tree()
Implicit Suffix Tree of the word: abbabaab

Python

>>> from sage.all import *
>>> Word('abbabaab').suffix_tree()
Implicit Suffix Tree of the word: abbabaab

suffix_trie()[source]¶

Return the suffix trie of self.

The suffix trie of a finite word \(w\) is a data structure representing the factors of \(w\). It is a tree whose edges are labelled with letters of \(w\), and whose leafs correspond to suffixes of \(w\).

Type sage.combinat.words.suffix_trees.SuffixTrie? for more information.

EXAMPLES:

Sage

sage: w = Word("cacao")
sage: w.suffix_trie()
Suffix Trie of the word: cacao

Python

>>> from sage.all import *
>>> w = Word("cacao")
>>> w.suffix_trie()
Suffix Trie of the word: cacao

Sage

sage: w = Word([0,1,0,1,1])
sage: w.suffix_trie()
Suffix Trie of the word: 01011

Python

>>> from sage.all import *
>>> w = Word([Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)])
>>> w.suffix_trie()
Suffix Trie of the word: 01011

swap(i, j=None)[source]¶

Return the word \(w\) with entries at positions i and j swapped. By default, j = i+1.

EXAMPLES:

Sage

sage: Word([1,2,3]).swap(0,2)
word: 321
sage: Word([1,2,3]).swap(1)
word: 132
sage: Word("abba").swap(1,-1)
word: aabb

Python

>>> from sage.all import *
>>> Word([Integer(1),Integer(2),Integer(3)]).swap(Integer(0),Integer(2))
word: 321
>>> Word([Integer(1),Integer(2),Integer(3)]).swap(Integer(1))
word: 132
>>> Word("abba").swap(Integer(1),-Integer(1))
word: aabb

swap_decrease(i)[source]¶

Return the word with positions i and i+1 exchanged if self[i] < self[i+1]. Otherwise, it returns self.

EXAMPLES:

Sage

sage: w = Word([1,3,2])
sage: w.swap_decrease(0)
word: 312
sage: w.swap_decrease(1)
word: 132
sage: w.swap_decrease(1) is w
True
sage: Words("ab")("abba").swap_decrease(0)
word: baba
sage: Words("ba")("abba").swap_decrease(0)
word: abba

Python

>>> from sage.all import *
>>> w = Word([Integer(1),Integer(3),Integer(2)])
>>> w.swap_decrease(Integer(0))
word: 312
>>> w.swap_decrease(Integer(1))
word: 132
>>> w.swap_decrease(Integer(1)) is w
True
>>> Words("ab")("abba").swap_decrease(Integer(0))
word: baba
>>> Words("ba")("abba").swap_decrease(Integer(0))
word: abba

swap_increase(i)[source]¶

Return the word with positions i and i+1 exchanged if self[i] > self[i+1]. Otherwise, it returns self.

EXAMPLES:

Sage

sage: w = Word([1,3,2])
sage: w.swap_increase(1)
word: 123
sage: w.swap_increase(0)
word: 132
sage: w.swap_increase(0) is w
True
sage: Words("ab")("abba").swap_increase(0)
word: abba
sage: Words("ba")("abba").swap_increase(0)
word: baba

Python

>>> from sage.all import *
>>> w = Word([Integer(1),Integer(3),Integer(2)])
>>> w.swap_increase(Integer(1))
word: 123
>>> w.swap_increase(Integer(0))
word: 132
>>> w.swap_increase(Integer(0)) is w
True
>>> Words("ab")("abba").swap_increase(Integer(0))
word: abba
>>> Words("ba")("abba").swap_increase(Integer(0))
word: baba

to_integer_list()[source]¶

Return a list of integers from [0,1,...,self.length()-1] in the same relative order as the letters in self in the parent.

EXAMPLES:

Sage

sage: from itertools import count
sage: w = Word('abbabaab')
sage: w.to_integer_list()
[0, 1, 1, 0, 1, 0, 0, 1]
sage: w = Word(iter("cacao"), length='finite')
sage: w.to_integer_list()
[1, 0, 1, 0, 2]
sage: w = Words([3,2,1])([2,3,3,1])
sage: w.to_integer_list()
[1, 0, 0, 2]

Python

>>> from sage.all import *
>>> from itertools import count
>>> w = Word('abbabaab')
>>> w.to_integer_list()
[0, 1, 1, 0, 1, 0, 0, 1]
>>> w = Word(iter("cacao"), length='finite')
>>> w.to_integer_list()
[1, 0, 1, 0, 2]
>>> w = Words([Integer(3),Integer(2),Integer(1)])([Integer(2),Integer(3),Integer(3),Integer(1)])
>>> w.to_integer_list()
[1, 0, 0, 2]

to_integer_word()[source]¶

Return a word over the alphabet [0,1,...,self.length()-1] whose letters are in the same relative order as the letters of self in the parent.

EXAMPLES:

Sage

sage: from itertools import count
sage: w = Word('abbabaab')
sage: w.to_integer_word()
word: 01101001
sage: w = Word(iter("cacao"), length='finite')
sage: w.to_integer_word()
word: 10102

sage: w = Words([3,2,1])([2,3,3,1])
sage: w.to_integer_word()
word: 1002

Python

>>> from sage.all import *
>>> from itertools import count
>>> w = Word('abbabaab')
>>> w.to_integer_word()
word: 01101001
>>> w = Word(iter("cacao"), length='finite')
>>> w.to_integer_word()
word: 10102

>>> w = Words([Integer(3),Integer(2),Integer(1)])([Integer(2),Integer(3),Integer(3),Integer(1)])
>>> w.to_integer_word()
word: 1002

to_monoid_element()[source]¶

Return self as an element of the free monoid with the same alphabet as self.

EXAMPLES:

Sage

sage: w = Word('aabb')
sage: w.to_monoid_element()
a^2*b^2
sage: W = Words('abc')
sage: w = W(w)
sage: w.to_monoid_element()
a^2*b^2

Python

>>> from sage.all import *
>>> w = Word('aabb')
>>> w.to_monoid_element()
a^2*b^2
>>> W = Words('abc')
>>> w = W(w)
>>> w.to_monoid_element()
a^2*b^2

to_ordered_set_partition()[source]¶

Return the ordered set partition correspond to self.

If \(w\) is a finite word of length \(n\), then the corresponding ordered set partition is an ordered set partition \((P_1, P_2, \ldots, P_k)\) of \(\{1, 2, \ldots, n\}\), where each block \(P_i\) is the set of positions at which the \(i\)-th smallest letter occurring in \(w\) occurs in \(w\).

EXAMPLES:

Sage

sage: w = Word('abbabaab')
sage: w.to_ordered_set_partition()
[{1, 4, 6, 7}, {2, 3, 5, 8}]
sage: Word([-10, 3, -10, 2]).to_ordered_set_partition()
[{1, 3}, {4}, {2}]
sage: Word([]).to_ordered_set_partition()
[]
sage: Word('aaaaa').to_ordered_set_partition()
[{1, 2, 3, 4, 5}]

Python

>>> from sage.all import *
>>> w = Word('abbabaab')
>>> w.to_ordered_set_partition()
[{1, 4, 6, 7}, {2, 3, 5, 8}]
>>> Word([-Integer(10), Integer(3), -Integer(10), Integer(2)]).to_ordered_set_partition()
[{1, 3}, {4}, {2}]
>>> Word([]).to_ordered_set_partition()
[]
>>> Word('aaaaa').to_ordered_set_partition()
[{1, 2, 3, 4, 5}]

topological_entropy(n)[source]¶

Return the topological entropy for the factors of length n.

The topological entropy of a sequence \(u\) is defined as the exponential growth rate of the complexity of \(u\) as the length increases: \(H_{top}(u)=\lim_{n\to\infty}\frac{\log_d(p_u(n))}{n}\) where \(d\) denotes the cardinality of the alphabet and \(p_u(n)\) is the complexity function, i.e. the number of factors of length \(n\) in the sequence \(u\) [Fog2002].

INPUT:

self – a word defined over a finite alphabet
n – positive integer

OUTPUT: real number (a symbolic expression)

EXAMPLES:

Sage

sage: W = Words([0, 1])
sage: w = W([0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1])
sage: t = w.topological_entropy(3); t                                       # needs sage.symbolic
1/3*log(7)/log(2)
sage: n(t)                                                                  # needs sage.symbolic
0.935784974019201

Python

>>> from sage.all import *
>>> W = Words([Integer(0), Integer(1)])
>>> w = W([Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1)])
>>> t = w.topological_entropy(Integer(3)); t                                       # needs sage.symbolic
1/3*log(7)/log(2)
>>> n(t)                                                                  # needs sage.symbolic
0.935784974019201

Sage

sage: w = words.ThueMorseWord()[:100]
sage: topo = w.topological_entropy
sage: for i in range(0, 41, 5):                                             # needs sage.symbolic
....:     print("{} {}".format(i, n(topo(i), digits=5)))
0 1.0000
5 0.71699
10 0.48074
15 0.36396
20 0.28774
25 0.23628
30 0.20075
35 0.17270
40 0.14827

Python

>>> from sage.all import *
>>> w = words.ThueMorseWord()[:Integer(100)]
>>> topo = w.topological_entropy
>>> for i in range(Integer(0), Integer(41), Integer(5)):                                             # needs sage.symbolic
...     print("{} {}".format(i, n(topo(i), digits=Integer(5))))
0 1.0000
5 0.71699
10 0.48074
15 0.36396
20 0.28774
25 0.23628
30 0.20075
35 0.17270
40 0.14827

If no alphabet is specified, an error is raised:

Sage

sage: w = Word(range(20))
sage: w.topological_entropy(3)
Traceback (most recent call last):
...
TypeError: The word must be defined over a finite alphabet

Python

>>> from sage.all import *
>>> w = Word(range(Integer(20)))
>>> w.topological_entropy(Integer(3))
Traceback (most recent call last):
...
TypeError: The word must be defined over a finite alphabet

The following is ok:

Sage

sage: W = Words(range(20))
sage: w = W(range(20))
sage: w.topological_entropy(3)                                              # needs sage.symbolic
1/3*log(18)/log(20)

Python

>>> from sage.all import *
>>> W = Words(range(Integer(20)))
>>> w = W(range(Integer(20)))
>>> w.topological_entropy(Integer(3))                                              # needs sage.symbolic
1/3*log(18)/log(20)

sage.combinat.words.finite_word.evaluation_dict(w)[source]¶

Return a dictionary keyed by the letters occurring in w with values the number of occurrences of the letter.

INPUT:

w – a word

sage.combinat.words.finite_word.word_to_ordered_set_partition(w)[source]¶

Return the ordered set partition corresponding to a finite word \(w\).

This is the same functionality that to_ordered_set_partition() provides, but without the wrapping: The input \(w\) can be given as a list or tuple, not necessarily as a word; and the output is returned as a list of lists (which are the blocks of the ordered set partition in increasing order), not as an ordered set partition.

EXAMPLES:

Sage

sage: from sage.combinat.words.finite_word import word_to_ordered_set_partition
sage: word_to_ordered_set_partition([3, 6, 3, 1])
[[4], [1, 3], [2]]
sage: word_to_ordered_set_partition((1, 3, 3, 7))
[[1], [2, 3], [4]]
sage: word_to_ordered_set_partition("noob")
[[4], [1], [2, 3]]
sage: word_to_ordered_set_partition(Word("hell"))
[[2], [1], [3, 4]]
sage: word_to_ordered_set_partition([1])
[[1]]
sage: word_to_ordered_set_partition([])
[]

Python

>>> from sage.all import *
>>> from sage.combinat.words.finite_word import word_to_ordered_set_partition
>>> word_to_ordered_set_partition([Integer(3), Integer(6), Integer(3), Integer(1)])
[[4], [1, 3], [2]]
>>> word_to_ordered_set_partition((Integer(1), Integer(3), Integer(3), Integer(7)))
[[1], [2, 3], [4]]
>>> word_to_ordered_set_partition("noob")
[[4], [1], [2, 3]]
>>> word_to_ordered_set_partition(Word("hell"))
[[2], [1], [3, 4]]
>>> word_to_ordered_set_partition([Integer(1)])
[[1]]
>>> word_to_ordered_set_partition([])
[]

Finite word¶

Creation of a finite word¶

Functions and algorithms¶

Factors and Rauzy Graphs¶