Abstract word (finite or infinite)

This module gathers functions that works for both finite and infinite words.

AUTHORS:

  • Sebastien Labbe
  • Franco Saliola

EXAMPLES:

sage: a = 0.618
sage: g = words.CodingOfRotationWord(alpha=a, beta=1-a, x=a)
sage: f = words.FibonacciWord()
sage: p = f.longest_common_prefix(g, length='finite')
sage: p
word: 0100101001001010010100100101001001010010...
sage: p.length()
231
class sage.combinat.words.abstract_word.Word_class

Bases: sage.structure.sage_object.SageObject

x.__init__(...) initializes x; see help(type(x)) for signature

apply_morphism(morphism)

Returns the word obtained by applying the morphism to self.

INPUT:

  • morphism - Can be an instance of WordMorphism, or anything that can be used to construct one.

EXAMPLES:

sage: w = Word("ab")
sage: d = {'a':'ab', 'b':'ba'}
sage: w.apply_morphism(d)
word: abba
sage: w.apply_morphism(WordMorphism(d))
word: abba
sage: w = Word('ababa')
sage: d = dict(a='ab', b='ba')
sage: d
{'a': 'ab', 'b': 'ba'}
sage: w.apply_morphism(d)
word: abbaabbaab

For infinite words:

sage: t = words.ThueMorseWord([0,1]); t
word: 0110100110010110100101100110100110010110...
sage: t.apply_morphism({0:8,1:9})
word: 8998988998898998988989988998988998898998...
complete_return_words_iterator(fact)

Returns an iterator over all the complete return words of fact in self (without unicity).

A complete return words \(u\) of a factor \(v\) is a factor starting by the given factor \(v\) and ending just after the next occurrence of this factor \(v\). See for instance [1].

INPUT:

  • fact - a non empty finite word

OUTPUT:

iterator

EXAMPLES:

sage: TM = words.ThueMorseWord()
sage: fact = Word([0,1,1,0,1])
sage: it = TM.complete_return_words_iterator(fact)
sage: it.next()
word: 01101001100101101
sage: it.next()
word: 01101001011001101
sage: it.next()
word: 011010011001011001101
sage: it.next()
word: 0110100101101
sage: it.next()
word: 01101001100101101
sage: it.next()
word: 01101001011001101

REFERENCES:

  • [1] J. Justin, L. Vuillon, Return words in Sturmian and episturmian words, Theor. Inform. Appl. 34 (2000) 343–356.
delta()

Returns the image of self under the delta morphism. This is the word composed of the length of consecutive runs of the same letter in a given word.

OUTPUT:

Word over integers

EXAMPLES:

For finite words:

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

For infinite words:

sage: t = words.ThueMorseWord()
sage: t.delta()
word: 1211222112112112221122211222112112112221...
factor_occurrences_iterator(fact)

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

INPUT:

  • fact - a non empty finite word

OUTPUT:

iterator

EXAMPLES:

sage: TM = words.ThueMorseWord()
sage: fact = Word([0,1,1,0,1])
sage: it = TM.factor_occurrences_iterator(fact)
sage: it.next()
0
sage: it.next()
12
sage: it.next()
24
finite_differences(mod=None)

Returns the word obtained by the diffences of consecutive letters of self.

INPUT:

  • self - A word over the integers.

  • mod - (default: None) It can be one of the following:
    • None or 0 : result is over the integers
    • integer : result is over the integers modulo mod.

EXAMPLES:

sage: w = Word([x^2 for x in range(10)])
sage: w.finite_differences()
word: 1,3,5,7,9,11,13,15,17
sage: w.finite_differences(mod=4)
word: 131313131
sage: w.finite_differences(mod=0)
word: 1,3,5,7,9,11,13,15,17

TESTS:

sage: w = Word([2,3,6])
sage: w.finite_differences()
word: 13
sage: w = Word([2,6])
sage: w.finite_differences()
word: 4
sage: w = Word([2])
sage: w.finite_differences()
word:
sage: w = Word()
sage: w.finite_differences()
word:

If the word is infinite, so is the result:

sage: w = Word(lambda n:n)
sage: u = w.finite_differences()
sage: u
word: 1111111111111111111111111111111111111111...
sage: type(u)
<class 'sage.combinat.words.word.InfiniteWord_iter_with_caching'>
is_empty()

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

EXAMPLES:

sage: it = iter([])
sage: Word(it).is_empty()
True
sage: it = iter([1,2,3])
sage: Word(it).is_empty()
False
sage: from itertools import count
sage: Word(count()).is_empty()
False
is_finite()

Returns whether this word is known to be finite.

Warning

A word defined by an iterator such that its end has never been reached will returns False.

EXAMPLES:

sage: Word([]).is_finite()
True
sage: Word('a').is_finite()
True
sage: TM = words.ThueMorseWord()
sage: TM.is_finite()
False
sage: w = Word(iter('a'*100))
sage: w.is_finite()
False
iterated_right_palindromic_closure(f=None, algorithm='recursive')

Returns the iterated (\(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).
  • algorithm - string (default: 'recursive') specifying which algorithm to be used when computing the iterated palindromic closure. It must be one of the two following values:
    • 'definition' - computed using the definition
    • 'recursive' - computation based on an efficient formula that recursively computes the iterated right palindromic closure without having to recompute the longest \(f\)-palindromic suffix at each iteration [2].

OUTPUT:

word – the iterated (\(f\)-)palindromic closure of self

EXAMPLES:

sage: Word('123').iterated_right_palindromic_closure()
word: 1213121
sage: w = Word('abc')
sage: w.iterated_right_palindromic_closure()
word: abacaba
sage: w = Word('aaa')
sage: w.iterated_right_palindromic_closure()
word: aaa
sage: w = Word('abbab')
sage: w.iterated_right_palindromic_closure()
word: ababaabababaababa

A right \(f\)-palindromic closure:

sage: f = WordMorphism('a->b,b->a')
sage: w = Word('abbab')
sage: w.iterated_right_palindromic_closure(f=f)
word: abbaabbaababbaabbaabbaababbaabbaab

An infinite word:

sage: t = words.ThueMorseWord('ab')
sage: t.iterated_right_palindromic_closure()
word: ababaabababaababaabababaababaabababaabab...

There are two implementations computing the iterated right \(f\)-palindromic closure, the latter being much more efficient:

sage: w = Word('abaab')
sage: u = w.iterated_right_palindromic_closure(algorithm='definition')
sage: v = w.iterated_right_palindromic_closure(algorithm='recursive')
sage: u
word: abaabaababaabaaba
sage: u == v
True
sage: w = words.RandomWord(8)
sage: u = w.iterated_right_palindromic_closure(algorithm='definition')
sage: v = w.iterated_right_palindromic_closure(algorithm='recursive')
sage: u == v
True

TESTS:

The empty word:

sage: w = Word()
sage: w.iterated_right_palindromic_closure()
word:

The length-\(1\) word:

sage: Word('1').iterated_right_palindromic_closure()
word: 1

If the word is finite, so is the result:

sage: w = Word([0,1]*7)
sage: c = w.iterated_right_palindromic_closure()
sage: type(c)
<class 'sage.combinat.words.word.FiniteWord_iter_with_caching'>

REFERENCES:

  • [1] A. de Luca, A. De Luca, Pseudopalindrome closure operators in free monoids, Theoret. Comput. Sci. 362 (2006) 282–300.
  • [2] J. Justin, Episturmian morphisms and a Galois theorem on continued fractions, RAIRO Theoret. Informatics Appl. 39 (2005) 207-215.
length()

Returns the length of self.

TESTS:

sage: from sage.combinat.words.word import Word_class
sage: w = Word(iter('abba'*100), length="unknown")
sage: w.length() is None
True
sage: w = Word(iter('abba'), length="finite")
sage: w.length()
4
sage: w = Word(iter([0,1,1,0,1,0,0,1]*100), length="unknown")
sage: w.length() is None
True
sage: w = Word(iter([0,1,1,0,1,0,0,1]), length="finite")
sage: w.length()
8
lex_greater(other)

Returns True if self is lexicographically greater than other.

EXAMPLES:

sage: w = Word([1,2,3])
sage: u = Word([1,3,2])
sage: v = Word([3,2,1])
sage: w.lex_greater(u)
False
sage: v.lex_greater(w)
True
sage: a = Word("abba")
sage: b = Word("abbb")
sage: a.lex_greater(b)
False
sage: b.lex_greater(a)
True

For infinite words:

sage: t = words.ThueMorseWord()
sage: t[:10].lex_greater(t)
False
sage: t.lex_greater(t[:10])
True
lex_less(other)

Returns True if self is lexicographically less than other.

EXAMPLES:

sage: w = Word([1,2,3])
sage: u = Word([1,3,2])
sage: v = Word([3,2,1])
sage: w.lex_less(u)
True
sage: v.lex_less(w)
False
sage: a = Word("abba")
sage: b = Word("abbb")
sage: a.lex_less(b)
True
sage: b.lex_less(a)
False

For infinite words:

sage: t = words.ThueMorseWord()
sage: t.lex_less(t[:10])
False
sage: t[:10].lex_less(t)
True
longest_common_prefix(other, length='unknown')

Returns the longest common prefix of self and other.

INPUT:

  • other - word
  • length - str or +Infinity (optional, default: 'unknown') the length type of the resulting word if known. It may be one of the following:
    • 'unknown'
    • 'finite'
    • 'infinite' or Infinity

OUTPUT:

word

EXAMPLES:

sage: f = lambda n : add(Integer(n).digits(2)) % 2
sage: t = Word(f)
sage: u = t[:10]
sage: t.longest_common_prefix(u)
word: 0110100110

The longest common prefix of two equal infinite words:

sage: t1 = Word(f)
sage: t2 = Word(f)
sage: t1.longest_common_prefix(t2)
word: 0110100110010110100101100110100110010110...

Useful to study the approximation of an infinite word:

sage: a = 0.618
sage: g = words.CodingOfRotationWord(alpha=a, beta=1-a, x=a)
sage: f = words.FibonacciWord()
sage: p = f.longest_common_prefix(g, length='finite')
sage: p.length()
231

TESTS:

sage: w = Word('12345')
sage: y = Word('1236777')
sage: w.longest_common_prefix(y)
word: 123
sage: w.longest_common_prefix(w)
word: 12345
sage: y.longest_common_prefix(w)
word: 123
sage: y.longest_common_prefix(y)
word: 1236777
sage: Word().longest_common_prefix(w)
word:
sage: w.longest_common_prefix(Word())
word:
sage: w.longest_common_prefix(w[:3])
word: 123
sage: Word("11").longest_common_prefix(Word("1"))
word: 1
sage: Word("1").longest_common_prefix(Word("11"))
word: 1

With infinite words:

sage: t = words.ThueMorseWord('ab')
sage: u = t[:10]
sage: u.longest_common_prefix(t)
word: abbabaabba
sage: u.longest_common_prefix(u)
word: abbabaabba
longest_periodic_prefix(period=1)

Returns the longest prefix of self having the given period.

INPUT:

  • period - positive integer (optional, default 1)

OUTPUT:

word

EXAMPLES:

sage: Word([]).longest_periodic_prefix()
word:
sage: Word([1]).longest_periodic_prefix()
word: 1
sage: Word([1,2]).longest_periodic_prefix()
word: 1
sage: Word([1,1,2]).longest_periodic_prefix()
word: 11
sage: Word([1,2,1,2,1,3]).longest_periodic_prefix(2)
word: 12121
sage: type(_)
<class 'sage.combinat.words.word.FiniteWord_iter_with_caching'>
sage: Word(lambda n:0).longest_periodic_prefix()
word: 0000000000000000000000000000000000000000...
palindrome_prefixes_iterator(max_length=None)

Returns an iterator over the palindrome prefixes of self.

INPUT:

  • max_length - non negative integer or None (optional, default: None) the maximum length of the prefixes

OUTPUT:

iterator

EXAMPLES:

sage: w = Word('abaaba')
sage: for pp in w.palindrome_prefixes_iterator(): pp
word:
word: a
word: aba
word: abaaba
sage: for pp in w.palindrome_prefixes_iterator(max_length=4): pp
word:
word: a
word: aba

You can iterate over the palindrome prefixes of an infinite word:

sage: f = words.FibonacciWord()
sage: for pp in f.palindrome_prefixes_iterator(max_length=20): pp
word:
word: 0
word: 010
word: 010010
word: 01001010010
word: 0100101001001010010
parent()

Returns the parent of self.

TESTS:

sage: Word(iter([1,2,3]), length="unknown").parent()
Words
sage: Word(range(12)).parent()
Words
sage: Word(range(4), alphabet=range(6)).parent()
Words over {0, 1, 2, 3, 4, 5}
sage: Word(iter('abac'), alphabet='abc').parent()
Words over {'a', 'b', 'c'}
partial_sums(start, mod=None)

Returns the word defined by the partial sums of its prefixes.

INPUT:

  • self - A word over the integers.

  • start - integer, the first letter of the resulting word.

  • mod - (default: None) It can be one of the following:
    • None or 0 : result is over the integers
    • integer : result is over the integers modulo mod.

EXAMPLES:

sage: w = Word(range(10))
sage: w.partial_sums(0)
word: 0,0,1,3,6,10,15,21,28,36,45
sage: w.partial_sums(1)
word: 1,1,2,4,7,11,16,22,29,37,46
sage: w = Word([1,2,3,1,2,3,2,2,2,2])
sage: w.partial_sums(0, mod=None)
word: 0,1,3,6,7,9,12,14,16,18,20
sage: w.partial_sums(0, mod=0)
word: 0,1,3,6,7,9,12,14,16,18,20
sage: w.partial_sums(0, mod=8)
word: 01367146024
sage: w.partial_sums(0, mod=4)
word: 01323102020
sage: w.partial_sums(0, mod=2)
word: 01101100000
sage: w.partial_sums(0, mod=1)
word: 00000000000

TESTS:

If the word is infinite, so is the result:

sage: w = Word(lambda n:1)
sage: u = w.partial_sums(0)
sage: type(u)
<class 'sage.combinat.words.word.InfiniteWord_iter_with_caching'>
prefixes_iterator(max_length=None)

Returns an iterator over the prefixes of self.

INPUT:

  • max_length - non negative integer or None (optional, default: None) the maximum length of the prefixes

OUTPUT:

iterator

EXAMPLES:

sage: w = Word('abaaba')
sage: for p in w.prefixes_iterator(): p
word:
word: a
word: ab
word: aba
word: abaa
word: abaab
word: abaaba
sage: for p in w.prefixes_iterator(max_length=3): p
word:
word: a
word: ab
word: aba

You can iterate over the prefixes of an infinite word:

sage: f = words.FibonacciWord()
sage: for p in f.prefixes_iterator(max_length=8): p
word:
word: 0
word: 01
word: 010
word: 0100
word: 01001
word: 010010
word: 0100101
word: 01001010

TESTS:

sage: list(f.prefixes_iterator(max_length=0))
[word: ]
return_words_iterator(fact)

Returns an iterator over all the return words of fact in self (without unicity).

INPUT:

  • fact - a non empty finite word

OUTPUT:

iterator

EXAMPLES:

sage: w = Word('baccabccbacbca')
sage: b = Word('b')
sage: list(w.return_words_iterator(b))
[word: bacca, word: bcc, word: bac]
sage: TM = words.ThueMorseWord()
sage: fact = Word([0,1,1,0,1])
sage: it = TM.return_words_iterator(fact)
sage: it.next()
word: 011010011001
sage: it.next()
word: 011010010110
sage: it.next()
word: 0110100110010110
sage: it.next()
word: 01101001
sage: it.next()
word: 011010011001
sage: it.next()
word: 011010010110
string_rep()

Returns the (truncated) raw sequence of letters as a string.

EXAMPLES:

sage: Word('abbabaab').string_rep()
'abbabaab'
sage: Word([0, 1, 0, 0, 1]).string_rep()
'01001'
sage: Word([0,1,10,101]).string_rep()
'0,1,10,101'
sage: WordOptions(letter_separator='-')
sage: Word([0,1,10,101]).string_rep()
'0-1-10-101'
sage: WordOptions(letter_separator=',')

TESTS:

Insertion in a str:

sage: from itertools import count
sage: w = Word((i % 5 for i in count()), length='unknown')
sage: "w = %s in this string." % w
'w = 0123401234012340123401234012340123401234... in this string.'

Using LatexExpr:

sage: from sage.misc.latex import LatexExpr
sage: LatexExpr(w)
0123401234012340123401234012340123401234...

With the print statement:

sage: print w
0123401234012340123401234012340123401234...

Truncation is done for possibily infinite words:

sage: print w
0123401234012340123401234012340123401234...
sum_digits(base=2, mod=None)

Return the sequence of the sum modulo mod of the digits written in base base of self.

INPUT:

  • self - word over natural numbers
  • base - integer (default : 2), greater or equal to 2
  • mod - modulo (default: None), can take the following values:
    • integer - the modulo
    • None - the value base is considered for the modulo.

EXAMPLES:

The Thue-Morse word:

sage: from itertools import count
sage: Word(count()).sum_digits()
word: 0110100110010110100101100110100110010110...

Sum of digits modulo 2 of the prime numbers written in base 2:

sage: Word(primes(1000)).sum_digits()
word: 1001110100111010111011001011101110011011...

Sum of digits modulo 3 of the prime numbers written in base 3:

sage: Word(primes(1000)).sum_digits(base=3)
word: 2100002020002221222121022221022122111022...
sage: Word(primes(1000)).sum_digits(base=3, mod=3)
word: 2100002020002221222121022221022122111022...

Sum of digits modulo 2 of the prime numbers written in base 3:

sage: Word(primes(1000)).sum_digits(base=3, mod=2)
word: 0111111111111111111111111111111111111111...

Sum of digits modulo 7 of the prime numbers written in base 10:

sage: Word(primes(1000)).sum_digits(base=10, mod=7)
word: 2350241354435041006132432241353546006304...

Negative entries:

sage: w = Word([-1,0,1,2,3,4,5])
sage: w.sum_digits()
Traceback (most recent call last):
...
NotImplementedError: nth digit of Thue-Morse word is not implemented for negative value of n

TESTS:

The Thue-Morse word:

sage: from itertools import count
sage: w = Word(count()).sum_digits()
sage: t = words.ThueMorseWord()
sage: w[:100]  == t[:100]
True
sage: type(Word(range(10)).sum_digits())
<class 'sage.combinat.words.word.FiniteWord_iter_with_caching'>
to_integer_word()

Returns a word over the integers whose letters are those output by self._to_integer_iterator()

EXAMPLES:

sage: from itertools import count
sage: w = Word(count()); w
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,...
sage: w.to_integer_word()
word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,...
sage: w = Word(iter("abbacabba"), length="finite"); w
word: abbacabba
sage: w.to_integer_word()
word: 011020110
sage: w = Word(iter("abbacabba"), length="unknown"); w
word: abbacabba
sage: w.to_integer_word()
word: 011020110

Previous topic

Alphabet

Next topic

Finite word

This Page