Demonstration: Combinatorics on words -- Sage Reference Manual v4.7.rc0
system:sage


<div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index" accesskey="I">index</a></li>
        <li class="right">
          <a href="../../../py-modindex.html" title="Python Module Index">modules</a> |</li>
        <li class="right">
          <a href="alphabet.html" title="Alphabets" accesskey="N">next</a> |</li>
        <li class="right">
          <a href="../../../combinat/words.html" title="Words" accesskey="P">previous</a> |</li>
  
    
      <a href="../../../../index.html"><img src="../../../_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="../../../index.html">Sage Reference v4.7.rc0</a> &raquo;</li>

          <li><a href="../../../combinat/index.html">Combinatorics</a> &raquo;</li>
          <li><a href="../../../combinat/words.html" accesskey="U">Words</a> &raquo;</li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <div class="section" id="demonstration-combinatorics-on-words">
<span id="sage-combinat-words-demo"></span><h1>Demonstration: Combinatorics on words<a class="headerlink" href="#demonstration-combinatorics-on-words" title="Permalink to this headline">¶</a></h1>
<span class="target" id="module-sage.combinat.words.demo"></span><div class="section" id="words">
<h2>Words<a class="headerlink" href="#words" title="Permalink to this headline">¶</a></h2>
<div class="section" id="finite-words">
<h3>Finite Words<a class="headerlink" href="#finite-words" title="Permalink to this headline">¶</a></h3>
<p>One can create a finite word from anything.</p>
<ul>
<li><p class="first">From Python objects:</p>
<div class="highlight-python">

{{{id=0|
Word(&#39;abfasdfas&#39;)
///
word: abfasdfas
}}}

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

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

</div>
</li>
<li><p class="first">From an iterator:</p>
<div class="highlight-python">

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

</div>
</li>
<li><p class="first">From a function:</p>
<div class="highlight-python">

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

</div>
</li>
</ul>
</div>
<div class="section" id="infinite-words">
<h3>Infinite Words<a class="headerlink" href="#infinite-words" title="Permalink to this headline">¶</a></h3>
<p>One can create an infinite word.</p>
<ul>
<li><p class="first">From an iterator:</p>
<div class="highlight-python">

{{{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(&#39;a&#39;))
///
word: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
}}}

</div>
</li>
<li><p class="first">From a function:</p>
<div class="highlight-python">

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

</div>
</li>
</ul>
</div>
<div class="section" id="word-methods-and-algorithms">
<h3>Word methods and algorithms<a class="headerlink" href="#word-methods-and-algorithms" title="Permalink to this headline">¶</a></h3>
<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>
<div class="highlight-python">

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

</div>
<p>For instance, one can slice an infinite word to get a certain finite factor and
compute its factor complexity:</p>
<div class="highlight-python">

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

</div>
</div>
</div>
<div class="section" id="word-morphisms">
<h2>Word Morphisms<a class="headerlink" href="#word-morphisms" title="Permalink to this headline">¶</a></h2>
<div class="section" id="creation">
<h3>Creation<a class="headerlink" href="#creation" title="Permalink to this headline">¶</a></h3>
<p>Creation of a word morphism:</p>
<ul>
<li><p class="first">from a dictionary:</p>
<div class="highlight-python">

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

</div>
</li>
<li><p class="first">from a string:</p>
<div class="highlight-python">

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

</div>
</li>
</ul>
</div>
<div class="section" id="word-morphisms-methods">
<h3>Word Morphisms methods<a class="headerlink" href="#word-morphisms-methods" title="Permalink to this headline">¶</a></h3>
<p>Image of a word under a morphism:</p>
<div class="highlight-python">

{{{id=14|
m(&#39;a&#39;)
///
word: abcab
}}}

{{{id=15|
m(&#39;abcabc&#39;)
///
word: abcabcbababcabcbab
}}}

</div>
<p>Power of a morphism:</p>
<div class="highlight-python">

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

</div>
<p>Incidence matrix:</p>
<div class="highlight-python">

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

</div>
</div>
<div class="section" id="fixed-point-of-a-morphism">
<h3>Fixed point of a morphism<a class="headerlink" href="#fixed-point-of-a-morphism" title="Permalink to this headline">¶</a></h3>
<p>Iterated image under a morphism:</p>
<div class="highlight-python">

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

{{{id=19|
m(&#39;c&#39;)
///
word: ab
}}}

{{{id=20|
m(m(&#39;c&#39;))
///
word: abcabcb
}}}

{{{id=21|
m(m(m(&#39;c&#39;)))
///
word: abcabcbababcabcbabcb
}}}

{{{id=22|
m(&#39;c&#39;, 3)
///
word: abcabcbababcabcbabcb
}}}

</div>
<p>Infinite fixed point of morphism:</p>
<div class="highlight-python">

{{{id=23|
m(&#39;a&#39;, Infinity)
///
word: abcabcbababcabcbabcbabcabcbabcabcbababca...
}}}

</div>
<p>or equivalently:</p>
<div class="highlight-python">

{{{id=24|
m.fixed_point(&#39;a&#39;)
///
word: abcabcbababcabcbabcbabcabcbabcabcbababca...
}}}

</div>
</div>
</div>
<div class="section" id="s-adic-sequences">
<h2>S-adic sequences<a class="headerlink" href="#s-adic-sequences" title="Permalink to this headline">¶</a></h2>
<div class="section" id="definition">
<h3>Definition<a class="headerlink" href="#definition" title="Permalink to this headline">¶</a></h3>
<p>Let <img class="math" src="../../../_images/math/9ee4b825a2e36ae093ed7be5e4851ef453b34914.png" alt="w"> be a infinite word over an alphabet <img class="math" src="../../../_images/math/d834b761acde544fc47aed1b41fb62e1d5af2a9f.png" alt="A=A_0">.</p>
<blockquote>
<img class="math" src="../../../_images/math/a41b757dacf0242d3b4b333bc3152fb06aa08150.png" alt="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 <img class="math" src="../../../_images/math/9ee4b825a2e36ae093ed7be5e4851ef453b34914.png" alt="w"> is obtained from a sequence of substitutions
<img class="math" src="../../../_images/math/c8fad7e5b7258a6b07b42bf6c8b6d8d4de43aecb.png" alt="\\sigma_k:A_{k+1}^*\\to A_k^*"> and a sequence of letters <img class="math" src="../../../_images/math/b16250931cfacb31ce4cdb51aab5c97ebe7e388b.png" alt="a_k\\in A_k"> such that:</p>
<blockquote>
<img class="math" src="../../../_images/math/ed5d0877adb0c187f27472da75fecdb6c4c15aa6.png" alt="w = \\lim_{k\\to\\infty}\\sigma_0\\circ\\sigma_1\\circ\\cdots\\sigma_k(a_k)">.</blockquote>
<p>Given a set of substitutions <img class="math" src="../../../_images/math/ad28c83c99a8fd0dd2e2e594c9d02ee532765a0a.png" alt="S">, we say that the representation is
<img class="math" src="../../../_images/math/ad28c83c99a8fd0dd2e2e594c9d02ee532765a0a.png" alt="S"> <strong>-adic standard</strong> if the subtitutions are chosen in <img class="math" src="../../../_images/math/ad28c83c99a8fd0dd2e2e594c9d02ee532765a0a.png" alt="S">.</p>
</div>
<div class="section" id="one-finite-example">
<h3>One finite example<a class="headerlink" href="#one-finite-example" title="Permalink to this headline">¶</a></h3>
<p>Let <img class="math" src="../../../_images/math/3568c30f4bb028cb56295bd7a8150b6f83201e12.png" alt="A_0=\\{g,h\\}">, <img class="math" src="../../../_images/math/11269d20f6a67f45d30ec9d614c937c34e8b6c2d.png" alt="A_1=\\{e,f\\}">, <img class="math" src="../../../_images/math/7010ca36a263733de8fa36c3642d07b0fac5e094.png" alt="A_2=\\{c,d\\}"> and <img class="math" src="../../../_images/math/d133094c48b26c18272a983035d6ee692f45b1f7.png" alt="A_3=\\{a,b\\}">.
Let <img class="math" src="../../../_images/math/937704220b6ec17cfe7b3fb5ad84073ad09c6027.png" alt="\\sigma_0 : \\begin{array}{l}e\\mapsto gh\\\\f\\mapsto hg\\end{array}">,
<img class="math" src="../../../_images/math/c078802c5414c0f17ea9c4b4c06a062c087868fd.png" alt="\\sigma_1 : \\begin{array}{l}c\\mapsto ef\\\\d\\mapsto e\\end{array}"> and
<img class="math" src="../../../_images/math/99f910da2a28b93e6c30a26105fb80e2d40ee8df.png" alt="\\sigma_2 : \\begin{array}{l}a\\mapsto cd\\\\b\\mapsto dc\\end{array}">.</p>
<blockquote>
<img class="math" src="../../../_images/math/4355fbc17396768dfab9ba2fa4924b92d3a1a082.png" alt="\\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}"></blockquote>
<p>Let&#8217;s define three morphisms and compute the first nested succesive 
prefixes of the s-adic word:</p>
<div class="highlight-python">

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

</div>
<div class="highlight-python">

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

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

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

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

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

</div>
<p>But if the letters don&#8217;t satisfy the hypothesis of the algorithm (nested
prefixes), an error is raised:</p>
<div class="highlight-python">

{{{id=30|
words.s_adic([sigma0,sigma1,sigma2],&#39;ecb&#39;)
///
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).
}}}

</div>
</div>
<div class="section" id="infinite-examples">
<h3>Infinite examples<a class="headerlink" href="#infinite-examples" title="Permalink to this headline">¶</a></h3>
<p>Let <img class="math" src="../../../_images/math/67710431efcdaf294dafb577353c69f12e420783.png" alt="A=A_i=\\{a,b\\}"> for all <img class="math" src="../../../_images/math/34857b3ba74ce5cd8607f3ebd23e9015908ada71.png" alt="i"> and 
Let <img class="math" src="../../../_images/math/d250cd4227e46bbf547fbb8e4484088893c0f884.png" alt="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>
<img class="math" src="../../../_images/math/368402f1c66db889ffd349ee80194fb5c14a8b59.png" alt="\\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}"></blockquote>
<p>Let&#8217;s define the Thue-Morse and the Fibonacci morphism
and let&#8217;s import the <tt class="docutils literal"><span class="pre">repeat</span></tt> tool from the <tt class="docutils literal"><span class="pre">itertools</span></tt>:</p>
<div class="highlight-python">

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

</div>
<p>Fixed point are trivial examples of infinite s-adic words:</p>
<div class="highlight-python">

{{{id=32|
words.s_adic(repeat(tm), repeat(&#39;a&#39;))
///
word: abbabaabbaababbabaababbaabbabaabbaababba...
}}}

{{{id=33|
tm.fixed_point(&#39;a&#39;)
///
word: abbabaabbaababbabaababbaabbabaabbaababba...
}}}

</div>
<p>Let&#8217;s alternate the application of the substitutions <img class="math" src="../../../_images/math/15f00fe2c1866b8a49c93b36afb407159606a233.png" alt="tm"> and <img class="math" src="../../../_images/math/c433512eee448b14e329765a44974500d763f9ea.png" alt="fibo"> according
to the Thue-Morse word:</p>
<div class="highlight-python">

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

</div>
<p>Random infinite s-adic words:</p>
<div class="highlight-python">

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

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

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

</div>
</div>
</div>
<div class="section" id="language">
<h2>Language<a class="headerlink" href="#language" title="Permalink to this headline">¶</a></h2>
<p>Soon in Sage...</p>
</div>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
            <h3><a href="../../../index.html">Table Of Contents</a></h3>
            <ul>
<li><a class="reference internal" href="#">Demonstration: Combinatorics on words</a><ul>
<li><a class="reference internal" href="#words">Words</a><ul>
<li><a class="reference internal" href="#finite-words">Finite Words</a></li>
<li><a class="reference internal" href="#infinite-words">Infinite Words</a></li>
<li><a class="reference internal" href="#word-methods-and-algorithms">Word methods and algorithms</a></li>
</ul>
</li>
<li><a class="reference internal" href="#word-morphisms">Word Morphisms</a><ul>
<li><a class="reference internal" href="#creation">Creation</a></li>
<li><a class="reference internal" href="#word-morphisms-methods">Word Morphisms methods</a></li>
<li><a class="reference internal" href="#fixed-point-of-a-morphism">Fixed point of a morphism</a></li>
</ul>
</li>
<li><a class="reference internal" href="#s-adic-sequences">S-adic sequences</a><ul>
<li><a class="reference internal" href="#definition">Definition</a></li>
<li><a class="reference internal" href="#one-finite-example">One finite example</a></li>
<li><a class="reference internal" href="#infinite-examples">Infinite examples</a></li>
</ul>
</li>
<li><a class="reference internal" href="#language">Language</a></li>
</ul>
</li>
</ul>

            <h4>Previous topic</h4>
            <p class="topless"><a href="../../../combinat/words.html" title="previous chapter">Words</a></p>
            <h4>Next topic</h4>
            <p class="topless"><a href="alphabet.html" title="next chapter">Alphabets</a></p>
            <h3>This Page</h3>
            <ul class="this-page-menu">
              <li><a href="../../../_sources/sage/combinat/words/demo.txt" rel="nofollow">Show Source</a></li>
            </ul>
          <div id="searchbox" style="display: none">
            <h3>Quick search</h3>
              <p class="searchtip" style="font-size: 90%">
              Enter search terms or a module, class or function name.
              </p>
          </div>
          <script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index">index</a></li>
        <li class="right">
          <a href="../../../py-modindex.html" title="Python Module Index">modules</a> |</li>
        <li class="right">
          <a href="alphabet.html" title="Alphabets">next</a> |</li>
        <li class="right">
          <a href="../../../combinat/words.html" title="Words">previous</a> |</li>
  
    
      <a href="../../../../index.html"><img src="../../../_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="../../../index.html">Sage Reference v4.7.rc0</a> &raquo;</li>

          <li><a href="../../../combinat/index.html">Combinatorics</a> &raquo;</li>
          <li><a href="../../../combinat/words.html">Words</a> &raquo;</li> 
      </ul>
    </div>
    
    <div class="footer">
        &copy; Copyright 2005--2011, The Sage Development Team.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.0.4.
    </div>
    <script type="text/javascript">
/*global jQuery, window */
/* Sphinx sidebar toggle.  Putting this code at the end of the body
 * enables the toggle for the live, static, and offline docs.  Note:
 * sage.misc.html.math_parse() eats jQuery's dollar-sign shortcut. */
var jq = jQuery;  
jq(document).ready(function () {
    var bar, bod, bg, fg, key, tog, wid_old, wid_new, resize, get_state, set_state;
    bod = jq('div.bodywrapper');
    bar = jq('div.sphinxsidebar');
    tog = jq('<div class="sphinxsidebartoggle"></div>');
    
    /* Delayed resize helper.  Not perfect but good enough. */
    resize = function () {
        setTimeout(function () {
            tog.height(bod.height());
        }, 100);
    };
    jq(window).resize(function () {
        resize();
    });
    
    /* Setup and add the toggle. See Sphinx v0.5.1 default.css. */
    fg = jq('div.sphinxsidebar p a').css('color') || 'rgb(152, 219, 204)';
    bg = jq('div.document').css('background-color') || 'rgb(28, 78, 99)';
    wid_old = '230px';
    wid_new = '5px';
    tog.css('background-color', bg)
        .css('border-width', '0px')
        .css('border-right', wid_new + ' ridge ' + bg)
        .css('cursor', 'pointer')
        .css('position', 'absolute')
        .css('left', '-' + wid_new)
        .css('top', '0px')
        .css('width', wid_new);
    bod.css('position', 'relative');
    bod.prepend(tog);
    resize();
    
    /* Cookie helpers. */
    key = 'sphinxsidebar=';
    set_state = function (s) {
        var date = new Date();
        /* Expiry in 7 days. */
        date.setTime(date.getTime() + (7 * 24 * 3600 * 1000));
        document.cookie = key + encodeURIComponent(s) + '; expires=' +
            date.toUTCString() + '; path=/';
    };
    get_state = function () {
        var i, c, crumbs = document.cookie.split(';');
        for (i = 0; i < crumbs.length; i += 1) {
            c = crumbs[i].replace(/^\s+/, '');
            if (c.indexOf(key) === 0) {
                return decodeURIComponent(c.substring(key.length, c.length));
            }
        }
        return null;
    };
    
    /* Event handlers. */
    tog.mouseover(function (ev) {
        tog.css('border-right-color', fg);
    }).mouseout(function (ev) {
        tog.css('border-right-color', bg);
    }).click(function (ev) {
        if (bod.hasClass('wide')) {
            bod.removeClass('wide');
            bod.css('margin-left', wid_old);
            bar.css('width', wid_old);
            bar.show();
            set_state('visible');
        } else {
            set_state('hidden');
            bar.hide();
            bar.css('width', '0px');
            bod.css('margin-left', wid_new);
            bod.addClass('wide');
        }
        resize();
    });
    
    /* Hide the normally visible sidebar? */
    if (get_state() === 'hidden') {
        tog.trigger('click');
    } else {
        set_state('visible');
    }
});
    </script>