Combinatorics on words - demo

<span id="demo-words"></span>



<h1>Words</h1>

<h2>Finite Words</h2>
<p>One can create a finite word from anything.</p>
<ul>
<li><p class="first">From Python objects:</p>

{{{id=0|
Word('abfasdfas')
///
word: abfasdfas
}}}

{{{id=1|
Word([2,3,4,5,6,6])
///
word: 234566
}}}

{{{id=2|
Word((0,1,2,1,2,))
///
word: 01212
}}}

</li>
<li><p class="first">From an iterator:</p>

{{{id=3|
it = iter(range(10))
Word(it)
///
word: 0123456789
}}}

</li>
<li><p class="first">From a function:</p>

{{{id=4|
f = lambda n : (3 ^ n) % 5
Word(f, length=20)
///
word: 13421342134213421342
}}}

</li>
</ul>


<h2>Infinite Words</h2>
<p>One can create an infinite word.</p>
<ul>
<li><p class="first">From an iterator:</p>

{{{id=5|
from itertools import count, repeat
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,...
}}}

{{{id=6|
Word(repeat('a'))
///
word: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
}}}

</li>
<li><p class="first">From a function:</p>

{{{id=7|
f = lambda n : (3 ^ n) % 5
Word(f)
///
word: 1342134213421342134213421342134213421342...
}}}

</li>
</ul>


<h2>Word methods and algorithms</h2>
<p>There are more than one hundreds methods and algorithms implemented for finite
words and infinite words. One can list them using the TAB command:</p>

{{{id=8|
w = Word(range(10))
w.&lt;TAB&gt;
///
}}}

<p>For instance, one can slice an infinite word to get a certain finite factor and
compute its factor complexity:</p>

{{{id=9|
w = Word(p % 3 for p in primes(10000))
w
///
word: 2021212122112122211211221212121221211122...
}}}

{{{id=10|
factor = w[1000:2000]
factor
///
word: 1122111211211222121222211211121212211212...
}}}

{{{id=11|
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]
}}}

<h1>Word Morphisms</h1>

<h2>Creation</h2>
<p>Creation of a word morphism:</p>
<ul>
<li><p class="first">from a dictionary:</p>

{{{id=12|
m = WordMorphism({'a':'abcab','b':'cb','c':'ab'})
print m
///
WordMorphism: a->abcab, b->cb, c->ab
}}}

</li>
<li><p class="first">from a string:</p>

{{{id=13|
m = WordMorphism('a-&gt;abcab,b-&gt;cb,c-&gt;ab')
print m
///
WordMorphism: a->abcab, b->cb, c->ab
}}}

</li>
</ul>


<h2>Word Morphisms methods</h2>
<p>Image of a word under a morphism:</p>

{{{id=14|
m('a')
///
word: abcab
}}}

{{{id=15|
m('abcabc')
///
word: abcabcbababcabcbab
}}}

<p>Power of a morphism:</p>

{{{id=16|
print m ^ 2
///
WordMorphism: a->abcabcbababcabcb, b->abcb, c->abcabcb
}}}

<p>Incidence matrix:</p>

{{{id=17|
matrix(m)
///
[2 0 1][2 1 1][1 1 0]
}}}

<h2>Fixed point of a morphism</h2>
<p>Iterated image under a morphism:</p>

{{{id=18|
print m
///
WordMorphism: a->abcab, b->cb, c->ab
}}}

{{{id=19|
m('c')
///
word: ab
}}}

{{{id=20|
m(m('c'))
///
word: abcabcb
}}}

{{{id=21|
m(m(m('c')))
///
word: abcabcbababcabcbabcb
}}}

{{{id=22|
m('c', 3)
///
word: abcabcbababcabcbabcb
}}}

<p>Infinite fixed point of morphism:</p>

{{{id=23|
m('a', Infinity)
///
word: abcabcbababcabcbabcbabcabcbabcabcbababca...
}}}

<p>or equivalently:</p>

{{{id=24|
m.fixed_point('a')
///
word: abcabcbababcabcbabcbabcabcbabcabcbababca...
}}}

<h1>S-adic sequences</h1>

<h2>Definition</h2>
<p>Let $w$ be a infinite word over an alphabet $A=A_0$.</p>
<blockquote>
$w\in
A_0^*\xleftarrow{\sigma_0}A_1^*\xleftarrow{\sigma_1}A_2^*\xleftarrow{\sigma_2}
A_3^*\xleftarrow{\sigma_3}\cdots$</blockquote>
<p>A <strong>standard representation</strong> 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:</p>
<blockquote>
$w = \lim_{k\to\infty}\sigma_0\circ\sigma_1\circ\cdots\sigma_k(a_k)$.</blockquote>
<p>Given a set of substitutions $S$, we say that the representation is
$S$ <strong>-adic standard</strong> if the subtitutions are chosen in $S$.</p>


<h2>One finite example</h2>
<p>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}$.</p>
<blockquote>
$\begin{array}{lclclcl} g \\
gh &amp; \xleftarrow{\sigma_0} &amp;
e \\
ghhg &amp; \xleftarrow{\sigma_0} &amp;
ef &amp; \xleftarrow{\sigma_1} &amp;
c \\
ghhggh &amp; \xleftarrow{\sigma_0} &amp;
efe &amp; \xleftarrow{\sigma_1} &amp;
cd &amp; \xleftarrow{\sigma_2} &amp;
a\end{array}$</blockquote>
<p>Let's define three morphisms and compute the first nested succesive
prefixes of the s-adic word:</p>

{{{id=25|
sigma0 = WordMorphism('e-&gt;gh,f-&gt;hg')
sigma1 = WordMorphism('c-&gt;ef,d-&gt;e')
sigma2 = WordMorphism('a-&gt;cd,b-&gt;dc')
///
}}}


{{{id=26|
words.s_adic([sigma2],'a')
///
word: cd
}}}

{{{id=27|
words.s_adic([sigma1,sigma2],'ca')
///
word: efe
}}}

{{{id=28|
words.s_adic([sigma0,sigma1,sigma2],'eca')
///
word: ghhggh
}}}

<p>When the given sequence of morphism is finite, one may simply give
the last letter, i.e. <tt class="docutils literal">'a'</tt>, instead of giving all of them,
i.e. <tt class="docutils literal">'eca'</tt>:</p>

{{{id=29|
words.s_adic([sigma0,sigma1,sigma2],'a')
///
word: ghhggh
}}}

<p>But if the letters don't satisfy the hypothesis of the algorithm (nested
prefixes), an error is raised:</p>

{{{id=30|
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).
}}}

<h2>Infinite examples</h2>
<p>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\}$.</p>
<blockquote>
$\begin{array}{lclclcl} a \\
ab &amp; \xleftarrow{tm} &amp;
a \\
abba &amp; \xleftarrow{tm} &amp;
ab &amp; \xleftarrow{fibo} &amp;
a \\
abbaab &amp; \xleftarrow{tm} &amp;
aba &amp; \xleftarrow{fibo} &amp;
ab &amp; \xleftarrow{tm} &amp;
a
\end{array}$</blockquote>
<p>Let's define the Thue-Morse and the Fibonacci morphism
and let's import the <tt class="docutils literal">repeat</tt> tool from the <tt class="docutils literal">itertools</tt>:</p>

{{{id=31|
tm = WordMorphism('a-&gt;ab,b-&gt;ba')
fib = WordMorphism('a-&gt;ab,b-&gt;a')
from itertools import repeat
///
}}}

<p>Fixed point are trivial examples of infinite s-adic words:</p>

{{{id=32|
words.s_adic(repeat(tm), repeat('a'))
///
word: abbabaabbaababbabaababbaabbabaabbaababba...
}}}

{{{id=33|
tm.fixed_point('a')
///
word: abbabaabbaababbabaababbaabbabaabbaababba...
}}}

<p>Let's alternate the application of the substitutions $tm$ and $fibo$ according
to the Thue-Morse word:</p>

{{{id=34|
tmwordTF = words.ThueMorseWord('TF')
words.s_adic(tmwordTF, repeat('a'), {'T':tm,'F':fib})
///
word: abbaababbaabbaabbaababbaababbaabbaababba...
}}}

<p>Random infinite s-adic words:</p>

{{{id=35|
from sage.misc.prandom import randint
def it():
     while True: yield randint(0,1)
words.s_adic(it(), repeat('a'), [tm,fib])
///
word: abbaabababbaababbaabbaababbaabababbaabba...
}}}

{{{id=36|
words.s_adic(it(), repeat('a'), [tm,fib])
///
word: abbaababbaabbaababbaababbaabbaababbaabba...
}}}

{{{id=37|
words.s_adic(it(), repeat('a'), [tm,fib])
///
word: abaaababaabaabaaababaabaaababaaababaabaa...
}}}

<h1>Language</h1>
<p>Soon in Sage...</p>