Demonstration: Combinatorics on words

Words

Finite Words

One can create a finite word from anything.

• From Python objects:

  {{{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 }}}

• From an iterator:

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

• From a function:

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

Infinite Words

One can create an infinite word.

• From an iterator:

  {{{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... }}}

• From a function:

  {{{id=7| f = lambda n : (3 ^ n) % 5 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:

{{{id=8| w = Word(range(10)) w.<TAB> /// }}}

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

{{{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] }}}

Word Morphisms

Creation

Creation of a word morphism:

• from a dictionary:

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

• from a string:

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

Word Morphisms methods

Image of a word under a morphism:

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

Power of a morphism:

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

Incidence matrix:

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

Fixed point of a morphism

Iterated image under a morphism:

{{{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 }}}

Infinite fixed point of morphism:

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

or equivalently:

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

S-adic sequences

Definition

Let be a infinite word over an alphabet .

A standard representation of is obtained from a sequence of substitutions and a sequence of letters such that:

.

Given a set of substitutions , we say that the representation is -adic standard if the subtitutions are chosen in .

One finite example

Let , , and . Let , and .

Let’s define three morphisms and compute the first nested succesive prefixes of the s-adic word:

{{{id=25| sigma0 = WordMorphism('e->gh,f->hg') sigma1 = WordMorphism('c->ef,d->e') sigma2 = WordMorphism('a->cd,b->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 }}}

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':

{{{id=29| 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:

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

Infinite examples

Let for all and Let .

Let’s define the Thue-Morse and the Fibonacci morphism and let’s import the repeat tool from the itertools:

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

Fixed point are trivial examples of infinite s-adic words:

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

Let’s alternate the application of the substitutions and according to the Thue-Morse word:

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

Random infinite s-adic words:

{{{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... }}}

Language

Soon in Sage...