This document is one of More SageMath Tutorials. You may edit it on github. \(\def\NN{\mathbb{N}}\) \(\def\ZZ{\mathbb{Z}}\) \(\def\QQ{\mathbb{Q}}\) \(\def\RR{\mathbb{R}}\) \(\def\CC{\mathbb{C}}\)
Demonstration: Combinatorics on words¶
Words¶
Finite Words¶
One can create a finite word from anything.
From Python objects:
sage: Word('abfasdfas') word: abfasdfas sage: Word([2,3,4,5,6,6]) word: 234566 sage: Word((0,1,2,1,2,)) word: 01212
From an iterator:
sage: it = iter(range(10)) sage: Word(it) word: 0123456789
From a function:
sage: f = lambda n : (3 ^ n) % 5 sage: Word(f, length=20) word: 13421342134213421342
Infinite Words¶
One can create an infinite word.
From an iterator:
sage: from itertools import count, repeat sage: Word(count()) 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: Word(repeat('a')) word: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
From a function:
sage: f = lambda n : (3 ^ n) % 5 sage: Word(f) word: 1342134213421342134213421342134213421342...
Word methods and algorithms¶
There are more than one hundreds methods and algorithms implemented for finite words and infinite words. One can list them using the TAB command:
sage: w = Word(range(10))
sage: w.<TAB>
For instance, one can slice an infinite word to get a certain finite factor and compute its factor complexity:
sage: w = Word(p % 3 for p in primes(10000))
sage: w
word: 2021212122112122211211221212121221211122...
sage: factor = w[1000:2000]
sage: factor
word: 1122111211211222121222211211121212211212...
sage: map(factor.number_of_factors, range(20))
[1, 2, 4, 8, 16, 32, 62, 110, 156, 190, 206, 214, 218, 217, 216, 215, 214, 213, 212, 211]
Word Morphisms¶
Creation¶
Creation of a word morphism:
from a dictionary:
sage: m = WordMorphism({'a':'abcab','b':'cb','c':'ab'}) sage: print m WordMorphism: a->abcab, b->cb, c->ab
from a string:
sage: m = WordMorphism('a->abcab,b->cb,c->ab') sage: print m WordMorphism: a->abcab, b->cb, c->ab
Word Morphisms methods¶
Image of a word under a morphism:
sage: m('a')
word: abcab
sage: m('abcabc')
word: abcabcbababcabcbab
Power of a morphism:
sage: print m ^ 2
WordMorphism: a->abcabcbababcabcb, b->abcb, c->abcabcb
Incidence matrix:
sage: matrix(m)
[2 0 1]
[2 1 1]
[1 1 0]
Fixed point of a morphism¶
Iterated image under a morphism:
sage: print m
WordMorphism: a->abcab, b->cb, c->ab
sage: m('c')
word: ab
sage: m(m('c'))
word: abcabcb
sage: m(m(m('c')))
word: abcabcbababcabcbabcb
sage: m('c', 3)
word: abcabcbababcabcbabcb
Infinite fixed point of morphism:
sage: m('a', Infinity)
word: abcabcbababcabcbabcbabcabcbabcabcbababca...
or equivalently:
sage: m.fixed_point('a')
word: abcabcbababcabcbabcbabcabcbabcabcbababca...
S-adic sequences¶
Definition¶
Let \(w\) be a infinite word over an alphabet \(A=A_0\).
\(w\\in A_0^*\\xleftarrow{\\sigma_0}A_1^*\\xleftarrow{\\sigma_1}A_2^*\\xleftarrow{\\sigma_2} A_3^*\\xleftarrow{\\sigma_3}\\cdots\)
A standard representation of \(w\) is obtained from a sequence of substitutions \(\\sigma_k:A_{k+1}^*\\to A_k^*\) and a sequence of letters \(a_k\\in A_k\) such that:
\(w = \\lim_{k\\to\\infty}\\sigma_0\\circ\\sigma_1\\circ\\cdots\\sigma_k(a_k)\).
Given a set of substitutions \(S\), we say that the representation is \(S\) -adic standard if the subtitutions are chosen in \(S\).
One finite example¶
Let \(A_0=\\{g,h\\}\), \(A_1=\\{e,f\\}\), \(A_2=\\{c,d\\}\) and \(A_3=\\{a,b\\}\). Let \(\\sigma_0 : \\begin{array}{l}e\\mapsto gh\\\\f\\mapsto hg\\end{array}\), \(\\sigma_1 : \\begin{array}{l}c\\mapsto ef\\\\d\\mapsto e\\end{array}\) and \(\\sigma_2 : \\begin{array}{l}a\\mapsto cd\\\\b\\mapsto dc\\end{array}\).
\(\\begin{array}{lclclcl} g \\\\ gh \& \\xleftarrow{\\sigma_0} \& e \\\\ ghhg \& \\xleftarrow{\\sigma_0} \& ef \& \\xleftarrow{\\sigma_1} \& c \\\\ ghhggh \& \\xleftarrow{\\sigma_0} \& efe \& \\xleftarrow{\\sigma_1} \& cd \& \\xleftarrow{\\sigma_2} \& a\\end{array}\)
Let us define three morphisms and compute the first nested succesive prefixes of the s-adic word:
sage: sigma0 = WordMorphism('e->gh,f->hg')
sage: sigma1 = WordMorphism('c->ef,d->e')
sage: sigma2 = WordMorphism('a->cd,b->dc')
sage: words.s_adic([sigma2],'a')
word: cd
sage: words.s_adic([sigma1,sigma2],'ca')
word: efe
sage: words.s_adic([sigma0,sigma1,sigma2],'eca')
word: ghhggh
When the given sequence of morphism is finite, one may simply give
the last letter, i.e. 'a', instead of giving all of them,
i.e. 'eca':
sage: words.s_adic([sigma0,sigma1,sigma2],'a')
word: ghhggh
But if the letters don’t satisfy the hypothesis of the algorithm (nested prefixes), an error is raised:
sage: words.s_adic([sigma0,sigma1,sigma2],'ecb')
Traceback (most recent call last):
...
ValueError: The hypothesis of the algorithm used is not satisfied: the image of the 3-th letter (=b) under the 3-th morphism (=WordMorphism: a->cd, b->dc) should start with the 2-th letter (=c).
Infinite examples¶
Let \(A=A_i=\\{a,b\\}\) for all \(i\) and Let \(S = \\left\\{ tm : \\begin{array}{l}a\\mapsto ab\\\\b\\mapsto ba\\end{array}, fibo : \\begin{array}{l}a\\mapsto ab\\\\b\\mapsto a\\end{array} \\right\\}\).
\(\\begin{array}{lclclcl} a \\\\ ab \& \\xleftarrow{tm} \& a \\\\ abba \& \\xleftarrow{tm} \& ab \& \\xleftarrow{fibo} \& a \\\\ abbaab \& \\xleftarrow{tm} \& aba \& \\xleftarrow{fibo} \& ab \& \\xleftarrow{tm} \& a \\end{array}\)
Let us define the Thue-Morse and the Fibonacci morphism
and let’s import the repeat tool from the itertools:
sage: tm = WordMorphism('a->ab,b->ba')
sage: fib = WordMorphism('a->ab,b->a')
sage: from itertools import repeat
Fixed point are trivial examples of infinite s-adic words:
sage: words.s_adic(repeat(tm), repeat('a'))
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: tm.fixed_point('a')
word: abbabaabbaababbabaababbaabbabaabbaababba...
Let us alternate the application of the substitutions \(tm\) and \(fibo\) according to the Thue-Morse word:
sage: tmwordTF = words.ThueMorseWord('TF')
sage: words.s_adic(tmwordTF, repeat('a'), {'T':tm,'F':fib})
word: abbaababbaabbaabbaababbaababbaabbaababba...
Random infinite s-adic words:
sage: from sage.misc.prandom import randint
sage: def it():
....: while True: yield randint(0,1)
sage: words.s_adic(it(), repeat('a'), [tm,fib])
word: abbaabababbaababbaabbaababbaabababbaabba...
sage: words.s_adic(it(), repeat('a'), [tm,fib])
word: abbaababbaabbaababbaababbaabbaababbaabba...
sage: words.s_adic(it(), repeat('a'), [tm,fib])
word: abaaababaabaabaaababaabaaababaaababaabaa...
Language¶
Soon in Sage…