## Attachment 'demo-words.txt'

   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
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|
274 ///
275 word: cd
276 }}}
277
278 {{{id=27|
280 ///
281 word: efe
282 }}}
283
284 {{{id=28|
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|
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|
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|
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')
356 ///
357 word: abbaababbaabbaabbaababbaababbaabbaababba...
358 }}}
359
361
362 {{{id=35|
363 from sage.misc.prandom import randint
364 def it():
365      while True: yield randint(0,1)
367 ///
368 word: abbaabababbaababbaabbaababbaabababbaabba...
369 }}}
370
371 {{{id=36|
373 ///
374 word: abbaababbaabbaababbaababbaabbaababbaabba...
375 }}}
376
377 {{{id=37|
379 ///
380 word: abaaababaabaabaaababaabaaababaaababaabaa...
381 }}}
382
383 <h1>Language</h1>
384 <p>Soon in Sage...</p>


## Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.
• [get | view] (2011-01-17 09:25:20, 659.2 KB) [[attachment:2011-01-17-SageDays28.pdf]]
• [get | view] (2011-01-18 15:18:22, 514.3 KB) [[attachment:Interval exchanges.sws]]
• [get | view] (2011-01-12 11:43:28, 74.7 KB) [[attachment:TPProg.pdf]]
• [get | view] (2011-01-17 15:31:02, 7.3 KB) [[attachment:demo-words.txt]]
• [get | view] (2011-01-18 08:22:34, 121.1 KB) [[attachment:demos-and-tutorials-version-17-janvier.zip]]