attachment:demo-words.txt of days28

   1 Combinatorics on words - demo
   2 
   3 <span id="demo-words"></span>
   4 
   5 
   6 
   7 <h1>Words</h1>
   8 
   9 <h2>Finite Words</h2>
  10 <p>One can create a finite word from anything.</p>
  11 <ul>
  12 <li><p class="first">From Python objects:</p>
  13 
  14 {{{id=0|
  15 Word('abfasdfas')
  16 ///
  17 word: abfasdfas
  18 }}}
  19 
  20 {{{id=1|
  21 Word([2,3,4,5,6,6])
  22 ///
  23 word: 234566
  24 }}}
  25 
  26 {{{id=2|
  27 Word((0,1,2,1,2,))
  28 ///
  29 word: 01212
  30 }}}
  31 
  32 </li>
  33 <li><p class="first">From an iterator:</p>
  34 
  35 {{{id=3|
  36 it = iter(range(10))
  37 Word(it)
  38 ///
  39 word: 0123456789
  40 }}}
  41 
  42 </li>
  43 <li><p class="first">From a function:</p>
  44 
  45 {{{id=4|
  46 f = lambda n : (3 ^ n) % 5
  47 Word(f, length=20)
  48 ///
  49 word: 13421342134213421342
  50 }}}
  51 
  52 </li>
  53 </ul>
  54 
  55 
  56 <h2>Infinite Words</h2>
  57 <p>One can create an infinite word.</p>
  58 <ul>
  59 <li><p class="first">From an iterator:</p>
  60 
  61 {{{id=5|
  62 from itertools import count, repeat
  63 Word(count())
  64 ///
  65 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,...
  66 }}}
  67 
  68 {{{id=6|
  69 Word(repeat('a'))
  70 ///
  71 word: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
  72 }}}
  73 
  74 </li>
  75 <li><p class="first">From a function:</p>
  76 
  77 {{{id=7|
  78 f = lambda n : (3 ^ n) % 5
  79 Word(f)
  80 ///
  81 word: 1342134213421342134213421342134213421342...
  82 }}}
  83 
  84 </li>
  85 </ul>
  86 
  87 
  88 <h2>Word methods and algorithms</h2>
  89 <p>There are more than one hundreds methods and algorithms implemented for finite
  90 words and infinite words. One can list them using the TAB command:</p>
  91 
  92 {{{id=8|
  93 w = Word(range(10))
  94 w.&lt;TAB&gt;
  95 ///
  96 }}}
  97 
  98 <p>For instance, one can slice an infinite word to get a certain finite factor and
  99 compute its factor complexity:</p>
 100 
 101 {{{id=9|
 102 w = Word(p % 3 for p in primes(10000))
 103 w
 104 ///
 105 word: 2021212122112122211211221212121221211122...
 106 }}}
 107 
 108 {{{id=10|
 109 factor = w[1000:2000]
 110 factor
 111 ///
 112 word: 1122111211211222121222211211121212211212...
 113 }}}
 114 
 115 {{{id=11|
 116 map(factor.number_of_factors, range(20))
 117 ///
 118 [1, 2, 4, 8, 16, 32, 62, 110, 156, 190, 206, 214, 218, 217, 216, 215, 214, 213, 212, 211]
 119 }}}
 120 
 121 <h1>Word Morphisms</h1>
 122 
 123 <h2>Creation</h2>
 124 <p>Creation of a word morphism:</p>
 125 <ul>
 126 <li><p class="first">from a dictionary:</p>
 127 
 128 {{{id=12|
 129 m = WordMorphism({'a':'abcab','b':'cb','c':'ab'})
 130 print m
 131 ///
 132 WordMorphism: a->abcab, b->cb, c->ab
 133 }}}
 134 
 135 </li>
 136 <li><p class="first">from a string:</p>
 137 
 138 {{{id=13|
 139 m = WordMorphism('a-&gt;abcab,b-&gt;cb,c-&gt;ab')
 140 print m
 141 ///
 142 WordMorphism: a->abcab, b->cb, c->ab
 143 }}}
 144 
 145 </li>
 146 </ul>
 147 
 148 
 149 <h2>Word Morphisms methods</h2>
 150 <p>Image of a word under a morphism:</p>
 151 
 152 {{{id=14|
 153 m('a')
 154 ///
 155 word: abcab
 156 }}}
 157 
 158 {{{id=15|
 159 m('abcabc')
 160 ///
 161 word: abcabcbababcabcbab
 162 }}}
 163 
 164 <p>Power of a morphism:</p>
 165 
 166 {{{id=16|
 167 print m ^ 2
 168 ///
 169 WordMorphism: a->abcabcbababcabcb, b->abcb, c->abcabcb
 170 }}}
 171 
 172 <p>Incidence matrix:</p>
 173 
 174 {{{id=17|
 175 matrix(m)
 176 ///
 177 [2 0 1][2 1 1][1 1 0]
 178 }}}
 179 
 180 <h2>Fixed point of a morphism</h2>
 181 <p>Iterated image under a morphism:</p>
 182 
 183 {{{id=18|
 184 print m
 185 ///
 186 WordMorphism: a->abcab, b->cb, c->ab
 187 }}}
 188 
 189 {{{id=19|
 190 m('c')
 191 ///
 192 word: ab
 193 }}}
 194 
 195 {{{id=20|
 196 m(m('c'))
 197 ///
 198 word: abcabcb
 199 }}}
 200 
 201 {{{id=21|
 202 m(m(m('c')))
 203 ///
 204 word: abcabcbababcabcbabcb
 205 }}}
 206 
 207 {{{id=22|
 208 m('c', 3)
 209 ///
 210 word: abcabcbababcabcbabcb
 211 }}}
 212 
 213 <p>Infinite fixed point of morphism:</p>
 214 
 215 {{{id=23|
 216 m('a', Infinity)
 217 ///
 218 word: abcabcbababcabcbabcbabcabcbabcabcbababca...
 219 }}}
 220 
 221 <p>or equivalently:</p>
 222 
 223 {{{id=24|
 224 m.fixed_point('a')
 225 ///
 226 word: abcabcbababcabcbabcbabcabcbabcabcbababca...
 227 }}}
 228 
 229 <h1>S-adic sequences</h1>
 230 
 231 <h2>Definition</h2>
 232 <p>Let $w$ be a infinite word over an alphabet $A=A_0$.</p>
 233 <blockquote>
 234 $w\in
 235 A_0^*\xleftarrow{\sigma_0}A_1^*\xleftarrow{\sigma_1}A_2^*\xleftarrow{\sigma_2}
 236 A_3^*\xleftarrow{\sigma_3}\cdots$</blockquote>
 237 <p>A <strong>standard representation</strong> of $w$ is obtained from a sequence of substitutions
 238 $\sigma_k:A_{k+1}^*\to A_k^*$ and a sequence of letters $a_k\in A_k$ such that:</p>
 239 <blockquote>
 240 $w = \lim_{k\to\infty}\sigma_0\circ\sigma_1\circ\cdots\sigma_k(a_k)$.</blockquote>
 241 <p>Given a set of substitutions $S$, we say that the representation is
 242 $S$ <strong>-adic standard</strong> if the subtitutions are chosen in $S$.</p>
 243 
 244 
 245 <h2>One finite example</h2>
 246 <p>Let $A_0=\{g,h\}$, $A_1=\{e,f\}$, $A_2=\{c,d\}$ and $A_3=\{a,b\}$.
 247 Let $\sigma_0 : \begin{array}{l}e\mapsto gh\\f\mapsto hg\end{array}$,
 248 $\sigma_1 : \begin{array}{l}c\mapsto ef\\d\mapsto e\end{array}$ and
 249 $\sigma_2 : \begin{array}{l}a\mapsto cd\\b\mapsto dc\end{array}$.</p>
 250 <blockquote>
 251 $\begin{array}{lclclcl} g \\
 252 gh &amp; \xleftarrow{\sigma_0} &amp;
 253 e \\
 254 ghhg &amp; \xleftarrow{\sigma_0} &amp;
 255 ef &amp; \xleftarrow{\sigma_1} &amp;
 256 c \\
 257 ghhggh &amp; \xleftarrow{\sigma_0} &amp;
 258 efe &amp; \xleftarrow{\sigma_1} &amp;
 259 cd &amp; \xleftarrow{\sigma_2} &amp;
 260 a\end{array}$</blockquote>
 261 <p>Let's define three morphisms and compute the first nested succesive
 262 prefixes of the s-adic word:</p>
 263 
 264 {{{id=25|
 265 sigma0 = WordMorphism('e-&gt;gh,f-&gt;hg')
 266 sigma1 = WordMorphism('c-&gt;ef,d-&gt;e')
 267 sigma2 = WordMorphism('a-&gt;cd,b-&gt;dc')
 268 ///
 269 }}}
 270 
 271 
 272 {{{id=26|
 273 words.s_adic([sigma2],'a')
 274 ///
 275 word: cd
 276 }}}
 277 
 278 {{{id=27|
 279 words.s_adic([sigma1,sigma2],'ca')
 280 ///
 281 word: efe
 282 }}}
 283 
 284 {{{id=28|
 285 words.s_adic([sigma0,sigma1,sigma2],'eca')
 286 ///
 287 word: ghhggh
 288 }}}
 289 
 290 <p>When the given sequence of morphism is finite, one may simply give
 291 the last letter, i.e. <tt class="docutils literal">'a'</tt>, instead of giving all of them,
 292 i.e. <tt class="docutils literal">'eca'</tt>:</p>
 293 
 294 {{{id=29|
 295 words.s_adic([sigma0,sigma1,sigma2],'a')
 296 ///
 297 word: ghhggh
 298 }}}
 299 
 300 <p>But if the letters don't satisfy the hypothesis of the algorithm (nested
 301 prefixes), an error is raised:</p>
 302 
 303 {{{id=30|
 304 words.s_adic([sigma0,sigma1,sigma2],'ecb')
 305 ///
 306 Traceback (most recent call last):
 307 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).
 308 }}}
 309 
 310 <h2>Infinite examples</h2>
 311 <p>Let $A=A_i=\{a,b\}$ for all $i$ and
 312 Let $S = \left\{ tm : \begin{array}{l}a\mapsto ab\\b\mapsto ba\end{array},
 313 fibo : \begin{array}{l}a\mapsto ab\\b\mapsto a\end{array} \right\}$.</p>
 314 <blockquote>
 315 $\begin{array}{lclclcl} a \\
 316 ab &amp; \xleftarrow{tm} &amp;
 317 a \\
 318 abba &amp; \xleftarrow{tm} &amp;
 319 ab &amp; \xleftarrow{fibo} &amp;
 320 a \\
 321 abbaab &amp; \xleftarrow{tm} &amp;
 322 aba &amp; \xleftarrow{fibo} &amp;
 323 ab &amp; \xleftarrow{tm} &amp;
 324 a
 325 \end{array}$</blockquote>
 326 <p>Let's define the Thue-Morse and the Fibonacci morphism
 327 and let's import the <tt class="docutils literal">repeat</tt> tool from the <tt class="docutils literal">itertools</tt>:</p>
 328 
 329 {{{id=31|
 330 tm = WordMorphism('a-&gt;ab,b-&gt;ba')
 331 fib = WordMorphism('a-&gt;ab,b-&gt;a')
 332 from itertools import repeat
 333 ///
 334 }}}
 335 
 336 <p>Fixed point are trivial examples of infinite s-adic words:</p>
 337 
 338 {{{id=32|
 339 words.s_adic(repeat(tm), repeat('a'))
 340 ///
 341 word: abbabaabbaababbabaababbaabbabaabbaababba...
 342 }}}
 343 
 344 {{{id=33|
 345 tm.fixed_point('a')
 346 ///
 347 word: abbabaabbaababbabaababbaabbabaabbaababba...
 348 }}}
 349 
 350 <p>Let's alternate the application of the substitutions $tm$ and $fibo$ according
 351 to the Thue-Morse word:</p>
 352 
 353 {{{id=34|
 354 tmwordTF = words.ThueMorseWord('TF')
 355 words.s_adic(tmwordTF, repeat('a'), {'T':tm,'F':fib})
 356 ///
 357 word: abbaababbaabbaabbaababbaababbaabbaababba...
 358 }}}
 359 
 360 <p>Random infinite s-adic words:</p>
 361 
 362 {{{id=35|
 363 from sage.misc.prandom import randint
 364 def it():
 365      while True: yield randint(0,1)
 366 words.s_adic(it(), repeat('a'), [tm,fib])
 367 ///
 368 word: abbaabababbaababbaabbaababbaabababbaabba...
 369 }}}
 370 
 371 {{{id=36|
 372 words.s_adic(it(), repeat('a'), [tm,fib])
 373 ///
 374 word: abbaababbaabbaababbaababbaabbaababbaabba...
 375 }}}
 376 
 377 {{{id=37|
 378 words.s_adic(it(), repeat('a'), [tm,fib])
 379 ///
 380 word: abaaababaabaabaaababaabaaababaaababaabaa...
 381 }}}
 382 
 383 <h1>Language</h1>
 384 <p>Soon in Sage...</p>