Sage: Ticket #21769: Adding Baum-Sweet Word
https://trac.sagemath.org/ticket/21769
<p>
Add the Baum-Sweet word to word_generators.
</p>
<p>
Information on the Baum-Sweet word can be found at <a class="ext-link" href="https://en.wikipedia.org/wiki/Baum%E2%80%93Sweet_sequence"><span class="icon"></span>https://en.wikipedia.org/wiki/Baum%E2%80%93Sweet_sequence</a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/21769
Trac 1.1.6tscrimWed, 26 Oct 2016 14:59:51 GMTcc set
https://trac.sagemath.org/ticket/21769#comment:1
https://trac.sagemath.org/ticket/21769#comment:1
<ul>
<li><strong>cc</strong>
<em>vdelecroix</em> added
</li>
</ul>
<p>
You can pass in words:
</p>
<pre class="wiki">sage: d = {Word('00'):Word('0000'), Word('01'):Word('1001'),
....: Word('10'):Word('0100'), Word('11'):Word('1101')}
sage: WordMorphism(d)
WordMorphism: 00->0000, 01->1001, 10->0100, 11->1101
</pre><p>
However, it is a bit cumbersome.
</p>
<p>
I'm not an expert enough on words to say if this is a valid morphism or not, but at least my naïve thought (i.e., equating to a morphism of a free monoid) is the domain must be letters. So I would expect this assumption in the code. Vincent, perhaps you can comment more on this?
</p>
TickettmonteilWed, 26 Oct 2016 16:22:52 GMTcc changed
https://trac.sagemath.org/ticket/21769#comment:2
https://trac.sagemath.org/ticket/21769#comment:2
<ul>
<li><strong>cc</strong>
<em>slabbe</em> added
</li>
</ul>
<p>
The alphabet can be anything, including strings of length two. The syntax <code>"00->0000,01->1001,10->0100,11->1101"</code> is only a wrapper to ease self-evident definitions (imagine if the alphabet contains the string '->'...), so it won't work when there is an ambiguity, which is good. We wight be a bit more flexible, but we should not guess in case of ambiguity.
</p>
<p>
Be careful by the way that Travis's proposition lead to a morphism with domain <code>Finite words over {word: 00, word: 01, word: 10, word: 11}</code> and codomain <code>Finite words over {'0', '1'}</code> (you might have expected the codomain to be <code>Finite words over {word: 00, word: 01, word: 10, word: 11}</code>, but how could Sage guess?).
</p>
TicketmcognettaWed, 26 Oct 2016 16:53:05 GMT
https://trac.sagemath.org/ticket/21769#comment:3
https://trac.sagemath.org/ticket/21769#comment:3
<p>
Thanks for the info. Just to be clear, how would you recommend implementing the morphism that I mentioned in the ticket?
</p>
TicketvdelecroixThu, 27 Oct 2016 11:36:38 GMT
https://trac.sagemath.org/ticket/21769#comment:4
https://trac.sagemath.org/ticket/21769#comment:4
<p>
From the ticket description, I don't undersand what is your morphism. Could you be more specific about the domain and the codomain. In Sage a word morphism is a semigroup morphism from a free monoid to another.
</p>
TicketmcognettaThu, 27 Oct 2016 12:23:38 GMT
https://trac.sagemath.org/ticket/21769#comment:5
https://trac.sagemath.org/ticket/21769#comment:5
<p>
Here is the motivation that I had when I made this ticket: <a class="ext-link" href="https://en.wikipedia.org/wiki/Baum%E2%80%93Sweet_sequence"><span class="icon"></span>https://en.wikipedia.org/wiki/Baum%E2%80%93Sweet_sequence</a>
</p>
<p>
I think that it would be possible to do this by doing something like
</p>
<pre class="wiki">a->aa
b->ca
c->ba
d->db
</pre><p>
and then just change a to 00, b to 01, c to 10, and d to 11.
</p>
TicketvdelecroixThu, 27 Oct 2016 13:08:57 GMT
https://trac.sagemath.org/ticket/21769#comment:6
https://trac.sagemath.org/ticket/21769#comment:6
<p>
Indeed it is a morphic but not purely morphic word. And the precise commands to generate the sequence
</p>
<pre class="wiki">sage: p = WordMorphism('a->00,b->01,c->10,d->11')
sage: s = WordMorphism('a->aa,b->ca,c->ba,d->db')
sage: p(s.fixed_point('d'))
word: 1101100001000000100000000000000001000000...
</pre>
TicketvdelecroixThu, 27 Oct 2016 14:23:01 GMT
https://trac.sagemath.org/ticket/21769#comment:7
https://trac.sagemath.org/ticket/21769#comment:7
<p>
I would suggest to either:
</p>
<ul><li>close this ticket as won't fix
</li><li>or add a <code>baum_sweet</code> to <code>words</code> so that one can do
<pre class="wiki">sage: words.baum_sweet()
word: 1101100001000000100000000000000001000000...
</pre></li></ul>
TicketmcognettaThu, 27 Oct 2016 14:28:25 GMT
https://trac.sagemath.org/ticket/21769#comment:8
https://trac.sagemath.org/ticket/21769#comment:8
<p>
I will add it to the generators in the next day or so.
</p>
<p>
Thanks for the help.
</p>
TicketmcognettaMon, 31 Oct 2016 07:56:59 GMTbranch set
https://trac.sagemath.org/ticket/21769#comment:9
https://trac.sagemath.org/ticket/21769#comment:9
<ul>
<li><strong>branch</strong>
set to <em>u/mcognetta/wordmorphism_does_not_allow_elements_of_length___1_in_the_domain</em>
</li>
</ul>
TicketmcognettaMon, 31 Oct 2016 07:58:11 GMTstatus, summary changed; commit set
https://trac.sagemath.org/ticket/21769#comment:10
https://trac.sagemath.org/ticket/21769#comment:10
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>3812f358f4e4cc4bcf3b4ead073d16c6c781737e</em>
</li>
<li><strong>summary</strong>
changed from <em>WordMorphism does not allow elements of length > 1 in the domain</em> to <em>Adding Baum-Sweet Word (Was "WordMorphism does not allow elements of length > 1 in the domain")</em>
</li>
</ul>
<p>
Changed the name of the ticket to reflect what it actually does and added a patch to add the Baum-Sweet Word to word_generators.py
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=3812f358f4e4cc4bcf3b4ead073d16c6c781737e"><span class="icon"></span>3812f35</a></td><td><code>added Baum-Sweet Word to word_generators</code>
</td></tr></table>
TicketvdelecroixMon, 31 Oct 2016 09:16:56 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/21769#comment:11
https://trac.sagemath.org/ticket/21769#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>Vincent Delecroix</em>
</li>
</ul>
<p>
Dear Marco,
</p>
<p>
1) The sequence you used does not coincide with wikipedia at the seventh position
</p>
<pre class="wiki">1, 1, 0, 1, 1, 0, 0, 0 # in the ticket
1, 1, 0, 1, 1, 0, 0, 1 # on wikipedia
</pre><blockquote>
<p>
there is something wrong with the substitution definition.
</p>
</blockquote>
<p>
2) You should say that the Baum-Sweet word is on the alphabet <code>{0, 1}</code>.
</p>
<p>
3) You should add a reference to wikipedia (see for example <code>finite_word.py</code> line 3568 on how to do that).
</p>
<p>
4) I do not like calling <code>f: 00 -> 0000, 01 -> 1001, etc</code> a morphism. The reason is that you consider the alphabet <code>{0,1}</code> and <code>f</code> is not a morphism of the free monoid <code>{0, 1}*</code>. It is a morphism of the submodules of words of even length that is generated by <code>{00, 01, 10, 11}</code> ( it is a free monoid on these four generators). Either you say that it is a morphism on this specific submonoid or you say something more vague such as "rewriting rule".
</p>
TicketmcognettaMon, 31 Oct 2016 10:47:20 GMT
https://trac.sagemath.org/ticket/21769#comment:12
https://trac.sagemath.org/ticket/21769#comment:12
<p>
Thanks for catching that and the other advice.
</p>
<p>
Just to be clear,
</p>
<blockquote class="citation">
<p>
It is a morphism of the <span class="underline">submodule</span> of words of even length that is generated by {00, 01, 10, 11}
</p>
</blockquote>
<p>
Did you mean submonoid?
</p>
<p>
If so, would
</p>
<pre class="wiki">The Baum-Sweet Sequence is an infinite word over the alphabet `\{0,1\}` defined as a
fixed point of the following morphism over the submodule of words of even length
generated by `\{00,01,10,11\}`:
</pre><p>
be sufficient or should I just write it is a word over <code>\{0,1\}</code> with the following string substitution rules...
</p>
TicketvdelecroixMon, 31 Oct 2016 11:10:46 GMT
https://trac.sagemath.org/ticket/21769#comment:13
https://trac.sagemath.org/ticket/21769#comment:13
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21769#comment:12" title="Comment 12">mcognetta</a>:
</p>
<blockquote class="citation">
<p>
Thanks for catching that and the other advice.
</p>
<p>
Just to be clear,
</p>
<blockquote class="citation">
<p>
It is a morphism of the <span class="underline">submodule</span> of words of even length that is generated by {00, 01, 10, 11}
</p>
</blockquote>
<p>
Did you mean submonoid?
</p>
</blockquote>
<p>
Yes. Sorry.
</p>
<blockquote class="citation">
<p>
If so, would
</p>
<pre class="wiki">The Baum-Sweet Sequence is an infinite word over the alphabet `\{0,1\}` defined as a
fixed point of the following morphism over the submodule of words of even length
generated by `\{00,01,10,11\}`:
</pre></blockquote>
<p>
This is a bit formal but precise.
</p>
<blockquote class="citation">
<p>
be sufficient or should I just write it is a word over <code>\{0,1\}</code> with the following string substitution rules...
</p>
</blockquote>
<p>
This is less formal but less precise... up to you.
</p>
<p>
If it was me, I would actually use the second formulation first and then make a remark about the fact that this substitution rule could be define as a morphism on the submonoid of words of even length.
</p>
TicketmcognettaMon, 31 Oct 2016 11:13:29 GMT
https://trac.sagemath.org/ticket/21769#comment:14
https://trac.sagemath.org/ticket/21769#comment:14
<p>
That was what I was considering also.
</p>
<p>
Thanks for the help.
</p>
TicketgitMon, 31 Oct 2016 12:10:42 GMTcommit changed
https://trac.sagemath.org/ticket/21769#comment:15
https://trac.sagemath.org/ticket/21769#comment:15
<ul>
<li><strong>commit</strong>
changed from <em>3812f358f4e4cc4bcf3b4ead073d16c6c781737e</em> to <em>22d56e3828500d55a1b6f948f77d8470b1bf11eb</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=22d56e3828500d55a1b6f948f77d8470b1bf11eb"><span class="icon"></span>22d56e3</a></td><td><code>updated the docs and fixed the example</code>
</td></tr></table>
TicketmcognettaMon, 31 Oct 2016 12:11:07 GMTstatus changed
https://trac.sagemath.org/ticket/21769#comment:16
https://trac.sagemath.org/ticket/21769#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketvdelecroixMon, 31 Oct 2016 12:26:04 GMT
https://trac.sagemath.org/ticket/21769#comment:17
https://trac.sagemath.org/ticket/21769#comment:17
<p>
Nicer. There is no need to have twice the substitution rules in the documentation. You can just write
</p>
<pre class="wiki">The substitution rule above can be considered as a morphism
on the submonoid of `\{0,1\}` generated by `\{00,01,10,11\}`
(which is a free monoid on these generators).
</pre><p>
(and be careful you wrote "submodule")
</p>
<p>
It would be nice to illustrate some of the properties of the sequence in the <code>EXAMPLES</code> section. For example
</p>
<pre class="wiki">sage: w = words.BaumSweetWord()
sage: f = lambda n: '1' if all(len(x)%2 == 0 for x in ''.join(map(str,ZZ(n).digits(2))).split('1')) else '0'
sage: all(f(i) == w[i] for i in range(100))
True
</pre><p>
Though I do not like so much the definition of <code>f</code> given above.
</p>
TicketslabbeMon, 31 Oct 2016 12:42:30 GMT
https://trac.sagemath.org/ticket/21769#comment:18
https://trac.sagemath.org/ticket/21769#comment:18
<p>
Hi, sorry, I had a visitor last week and I was not working during the weekend... In this comment, I am replying only to the description of the ticket:
</p>
<p>
Replying to <a class="closed ticket" href="https://trac.sagemath.org/ticket/21769" title="enhancement: Adding Baum-Sweet Word (closed: fixed)">mcognetta</a>:
</p>
<blockquote class="citation">
<p>
<a class="missing wiki">WordMorphism?</a> fails with morphisms that have domains with elements of greater than length 1.
</p>
</blockquote>
<p>
I do not agree, letters can be anything that is hashable:
</p>
<pre class="wiki">sage: m = WordMorphism({
....: (0,0):[(0,0),(0,0)],
....: (0,1):[(1,0),(0,1)],
....: (1,0):[(0,1),(0,0)],
....: (1,1):[(1,1),(0,1)]})
....:
sage:
sage: m
WordMorphism: (0, 0)->(0, 0),(0, 0), (0, 1)->(1, 0),(0, 1), (1, 0)->(0, 1),(0, 0), (1, 1)->(1, 1),(0, 1)
sage: m([(0,0)])
word: (0, 0),(0, 0)
sage: m([(0,0),(1,0),(0,1)])
word: (0, 0),(0, 0),(0, 1),(0, 0),(1, 0),(0, 1)
sage: m([(0,0),(1,0),(0,1),(1,1),(1,1)])
word: (0, 0),(0, 0),(0, 1),(0, 0),(1, 0),(0, 1),(1, 1),(0, 1),(1, 1),(0, 1)
sage: m.fixed_point((0,0))
word: (0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),(0, 0),...
</pre><p>
But then those letter of arbitrary length are still considered as of length 1. Is this what you want?
</p>
<pre class="wiki">sage: w = m([(0,0)])
sage: w
word: (0, 0),(0, 0)
sage: w.length()
2
</pre><blockquote class="citation">
<p>
There is also some unfortunate behavior if you try to define the morphism as a dict.
</p>
</blockquote>
<p>
In the documentation, you will see that the images must be defined as a list. For example, Thue Morse morphism can be defined like this using a dict:
</p>
<pre class="wiki">sage: WordMorphism({0:[0,1], 1:[1,0]})
WordMorphism: 0->01, 1->10
</pre><p>
Therefore, I do not see what you are expecting from this part of the description of the ticket:
</p>
<blockquote class="citation">
<pre class="wiki">sage: WordMorphism({00:0000,01:1001,10:0100,11:1101})
DeprecationWarning: use 0o as octal prefix instead of 0
If you do not want this number to be interpreted as octal, remove the leading zeros.
See http://trac.sagemath.org/17413 for details.
exec(code_obj, self.user_global_ns, self.user_ns)
WordMorphism: 0->0, 1->1001, 10->64, 11->1101
</pre></blockquote>
<p>
Note also that leading zero are intepreted as octal system in Python:
</p>
<pre class="wiki">sage: 0100
64
</pre><blockquote class="citation">
<p>
It makes sense why the above example does not work, but it would be nice if one could do it this way.
</p>
</blockquote>
<p>
What do you mean by "this way"? Because I do not think that we want to change the fact that 0100 is 64 in Python...
</p>
<p>
A morphism is a function which satisfies f(uv) = f(u)f(v). Therefore, defining the images on the letters is sufficient. Maybe what you want to implement is something more general (like a substitution). If yes, I think it would be easier to implement as a new Python class in a new file substitution.py, instead of generalizing morphism.py.
</p>
<p>
Would it be possible that the description of the ticket be updated to what is now the current goal of the ticket? Thank you!
</p>
TicketvdelecroixMon, 31 Oct 2016 13:00:38 GMT
https://trac.sagemath.org/ticket/21769#comment:19
https://trac.sagemath.org/ticket/21769#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21769#comment:18" title="Comment 18">slabbe</a>:
</p>
<blockquote class="citation">
<p>
Hi, sorry, I had a visitor last week and I was not working during the weekend... In this comment, I am replying only to the description of the ticket:
</p>
<p>
Replying to <a class="closed ticket" href="https://trac.sagemath.org/ticket/21769" title="enhancement: Adding Baum-Sweet Word (closed: fixed)">mcognetta</a>:
A morphism is a function which satisfies f(uv) = f(u)f(v). Therefore, defining the images on the letters is sufficient. Maybe what you want to implement is something more general (like a substitution). If yes, I think it would be easier to implement as a new Python class in a new file substitution.py, instead of generalizing morphism.py.
</p>
</blockquote>
<p>
It would be nice to support morphisms with domain being a submoinoid of the free monoid like we have here: the monoid generated by {00, 01, 10, 11} which is the even length words. In this context, the Baum-Sweet sequence is a fixed point! But it is beyond the scope of this ticket.
</p>
TicketgitSun, 06 Nov 2016 12:14:53 GMTcommit changed
https://trac.sagemath.org/ticket/21769#comment:20
https://trac.sagemath.org/ticket/21769#comment:20
<ul>
<li><strong>commit</strong>
changed from <em>22d56e3828500d55a1b6f948f77d8470b1bf11eb</em> to <em>b1aef84b1de0a55db584a9834222d3b00eb92e48</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=b1aef84b1de0a55db584a9834222d3b00eb92e48"><span class="icon"></span>b1aef84</a></td><td><code>updated the docs and added a new example</code>
</td></tr></table>
TicketmcognettaSun, 06 Nov 2016 12:23:28 GMTdescription changed
https://trac.sagemath.org/ticket/21769#comment:21
https://trac.sagemath.org/ticket/21769#comment:21
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/21769?action=diff&version=21">diff</a>)
</li>
</ul>
TicketvdelecroixTue, 08 Nov 2016 17:59:49 GMTstatus changed; author set
https://trac.sagemath.org/ticket/21769#comment:22
https://trac.sagemath.org/ticket/21769#comment:22
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>author</strong>
set to <em>Marco Cognetta</em>
</li>
</ul>
<p>
Good! Thanks for the addition. Next time do not forget to add your complete to the "Authors" field of the ticket (I did it).
</p>
TicketvbraunThu, 10 Nov 2016 20:39:43 GMTstatus changed
https://trac.sagemath.org/ticket/21769#comment:23
https://trac.sagemath.org/ticket/21769#comment:23
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<pre class="wiki">[dochtml] OSError: [combinat ] /home/sage/sage/local/lib/python2.7/site-packages/sage/combinat/words/word_generators.py:docstring of sage.combinat.words.word_generators.WordGenerator.BaumSweetWord:39: WARNING: Explicit markup ends without a blank line; unexpected unindent.
</pre>
TicketgitThu, 17 Nov 2016 05:57:55 GMTcommit changed
https://trac.sagemath.org/ticket/21769#comment:24
https://trac.sagemath.org/ticket/21769#comment:24
<ul>
<li><strong>commit</strong>
changed from <em>b1aef84b1de0a55db584a9834222d3b00eb92e48</em> to <em>cc3c8b0ccda7162e7941bb30c31c3b9379cead05</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=cc3c8b0ccda7162e7941bb30c31c3b9379cead05"><span class="icon"></span>cc3c8b0</a></td><td><code>added extra line after a math markup section</code>
</td></tr></table>
TicketmcognettaThu, 17 Nov 2016 05:58:34 GMTstatus changed
https://trac.sagemath.org/ticket/21769#comment:25
https://trac.sagemath.org/ticket/21769#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Added an extra line after my ..MATH:: markup section and the warning went away and built the docs correctly.
</p>
TicketvdelecroixTue, 22 Nov 2016 15:17:31 GMTstatus changed
https://trac.sagemath.org/ticket/21769#comment:26
https://trac.sagemath.org/ticket/21769#comment:26
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TickettscrimTue, 22 Nov 2016 15:29:11 GMTkeywords, type, description, summary changed
https://trac.sagemath.org/ticket/21769#comment:27
https://trac.sagemath.org/ticket/21769#comment:27
<ul>
<li><strong>keywords</strong>
<em>days79</em> added
</li>
<li><strong>type</strong>
changed from <em>defect</em> to <em>enhancement</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/21769?action=diff&version=27">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Adding Baum-Sweet Word (Was "WordMorphism does not allow elements of length > 1 in the domain")</em> to <em>Adding Baum-Sweet Word</em>
</li>
</ul>
TicketvbraunThu, 24 Nov 2016 23:41:04 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/21769#comment:28
https://trac.sagemath.org/ticket/21769#comment:28
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/mcognetta/wordmorphism_does_not_allow_elements_of_length___1_in_the_domain</em> to <em>cc3c8b0ccda7162e7941bb30c31c3b9379cead05</em>
</li>
</ul>
Ticket