Finite words

Finite words

Methods that are not in Sage (for now!)

AUTHORS:

  • Sébastien Labbé, 2015
  • Sébastien Labbé, 2017, added lexicographic Lyndon stuff

EXAMPLES:

sage: from slabbe.finite_word import discrepancy
sage: w = words.ChristoffelWord(5,8)
sage: discrepancy(w)
12/13
slabbe.finite_word.are_overlapping_factors(u, v, d)

Returns whether there exists a word w such that u occurs in w at position 0 and v occurs in w at position d.

INPUT:

  • u – word
  • v – word
  • d – integer (positive or negative)

EXAMPLES:

sage: from slabbe.finite_word import are_overlapping_factors
sage: are_overlapping_factors('abc', 'abc', 0)
True
sage: are_overlapping_factors('abc', 'abc', 1)
False
sage: are_overlapping_factors('abcdef', 'bc', 1)
True
sage: are_overlapping_factors('abcdef', 'bcdefgh', 1)
True
sage: are_overlapping_factors('abcdef', 'bcddefgh', 1)
False
sage: are_overlapping_factors('abcdef', 'aabcdefgh', -1)
True
sage: are_overlapping_factors('abcdef', 'aabcd', -1)
True
sage: are_overlapping_factors('abcdef', 'aabcc', -1)
False
slabbe.finite_word.discrepancy(self, freq=None)

Return the discrepancy of the word.

This is a distance to the euclidean line defined in [T1980].

INPUT:

  • freq – frequency vector (default: None)

EXAMPLES:

sage: from slabbe.finite_word import discrepancy
sage: w = words.ChristoffelWord(5,8)
sage: w
word: 0010010100101
sage: discrepancy(w)
12/13
sage: for c in w.conjugates(): print (c, discrepancy(c))
0010010100101 12/13
0100101001010 7/13
1001010010100 10/13
0010100101001 10/13
0101001010010 7/13
1010010100100 12/13
0100101001001 8/13
1001010010010 9/13
0010100100101 11/13
0101001001010 6/13
1010010010100 11/13
0100100101001 9/13
1001001010010 8/13

REFERENCES:

[T1980]R., Tijdeman. The chairman assignment problem. Discrete Mathematics 32, no 3 (1980): 323-30. doi:10.1016/0012-365X(80)90269-1.
slabbe.finite_word.is_lyndon_mod_reverse(self)

EXAMPLES:

sage: from slabbe.finite_word import is_lyndon_mod_reverse
sage: is_lyndon_mod_reverse(Word('111222'))
True
sage: is_lyndon_mod_reverse(Word('1112221'))
False
sage: is_lyndon_mod_reverse(Word('143'))
False
sage: w = words.ChristoffelWord(72452,462443)
sage: is_lyndon_mod_reverse(w)
True
slabbe.finite_word.minimum_lexicographic_conjugate(self)

Return the conjugate word which is minimal for the lexicographic order.

The output is a Lyndon word (or some power of).

EXAMPLES:

sage: from slabbe.finite_word import minimum_lexicographic_conjugate
sage: minimum_lexicographic_conjugate(Word([1,3,2,2,2]))
word: 13222
sage: minimum_lexicographic_conjugate(Word([1,4,3]))
word: 143
sage: minimum_lexicographic_conjugate(Word([3,4,1]))
word: 134

The code is fast:

sage: w = words.ChristoffelWord(72452, 462443)
sage: minimum_lexicographic_conjugate(w)
word: 0000000100000010000000100000010000001000...
slabbe.finite_word.minimum_lexicographic_conjugate_reversal(self)

TODO: Use Lyndon factorisation to improve the time/space…

EXAMPLES:

sage: from slabbe.finite_word import minimum_lexicographic_conjugate_reversal
sage: minimum_lexicographic_conjugate_reversal(Word([1,3,2,2,2]))
word: 12223
sage: w = words.ChristoffelWord(72452,462443)
sage: minimum_lexicographic_conjugate_reversal(w)
word: 0000000100000010000000100000010000001000...
sage: _ == w
True
sage: minimum_lexicographic_conjugate_reversal(Word([1,3,2,2,1,1,2]))
word: 1121322
slabbe.finite_word.run_length_encoding(self)

EXAMPLES:

sage: from slabbe.finite_word import run_length_encoding
sage: L = [0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3]
sage: run_length_encoding(L)
[(0, 1), (1, 6), (2, 1), (1, 1), (2, 5), (3, 6)]
slabbe.finite_word.sort_word_by_length_lex_key(w)

A key function to sort word (by length, and then lexicographically).

EXAMPLES:

sage: from slabbe.finite_word import sort_word_by_length_lex_key
sage: L = ['aa', 'aaa', 'bb', 'ccc']
sage: sorted(L, key=sort_word_by_length_lex_key)
['aa', 'bb', 'aaa', 'ccc']
slabbe.finite_word.to_image(self, width=1000)

Creates an image from a word

INPUT:

  • width – integer, width of image

EXAMPLES:

sage: from slabbe.finite_word import to_image
sage: t = words.ThueMorseWord()
sage: img = to_image(t[:10000], width=100)
sage: img
<PIL.Image.Image image mode=RGB size=100x100 at 0x...>
sage: img.show()    # not tested
sage: W = FiniteWords(range(10))
sage: d = {a:W.random_element(7) for a in range(10)}
sage: m = WordMorphism(d, codomain=W)
sage: w = m.periodic_points()[0][0]
sage: s = map(int, str(pi.n(digits=40001))[2:])
sage: len(s)
40000
sage: img = to_image(W(s), 200)
sage: img.show()    # not tested
slabbe.finite_word.word_to_polyomino(self)

Returns the inside points of a polyomino.

INPUT:

  • self – list of integers in 0,1,2,3 describing a closed path

OUTPUT:

  • list of 2d vectors

EXAMPLES:

sage: from slabbe.finite_word import word_to_polyomino
sage: w = [0,0,0,1,1,1,2,2,2,3,3,3]
sage: word_to_polyomino(w)
[(0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2), (1, 2), (2, 1), (2, 2)]
sage: w = [1,1,1,0,0,0,3,3,3,2,2,2]
sage: word_to_polyomino(w)
[(0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2), (1, 2), (2, 1), (2, 2)]