Adding Baum-Sweet Word

[mcognetta]

Add the Baum-Sweet word to word_generators.

Information on the Baum-Sweet word can be found at ​https://en.wikipedia.org/wiki/Baum%E2%80%93Sweet_sequence

[tscrim]

You can pass in words:

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

However, it is a bit cumbersome.

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?

[tmonteil]

The alphabet can be anything, including strings of length two. The syntax "00->0000,01->1001,10->0100,11->1101" 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.

Be careful by the way that Travis's proposition lead to a morphism with domain Finite words over {word: 00, word: 01, word: 10, word: 11} and codomain Finite words over {'0', '1'} (you might have expected the codomain to be Finite words over {word: 00, word: 01, word: 10, word: 11}, but how could Sage guess?).

[mcognetta]

Thanks for the info. Just to be clear, how would you recommend implementing the morphism that I mentioned in the ticket?

[vdelecroix]

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.

[mcognetta]

Here is the motivation that I had when I made this ticket: ​https://en.wikipedia.org/wiki/Baum%E2%80%93Sweet_sequence

I think that it would be possible to do this by doing something like

a->aa
b->ca
c->ba
d->db

and then just change a to 00, b to 01, c to 10, and d to 11.

[vdelecroix]

Indeed it is a morphic but not purely morphic word. And the precise commands to generate the sequence

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

[vdelecroix]

I would suggest to either:

• close this ticket as won't fix
• or add a baum_sweet to words so that one can do

  sage: words.baum_sweet()
  word: 1101100001000000100000000000000001000000...
  

[mcognetta]

I will add it to the generators in the next day or so.

Thanks for the help.

[mcognetta]

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

---

New commits:

​3812f35

added Baum-Sweet Word to word_generators

[vdelecroix]

Dear Marco,

1) The sequence you used does not coincide with wikipedia at the seventh position

1, 1, 0, 1, 1, 0, 0, 0 # in the ticket
1, 1, 0, 1, 1, 0, 0, 1 # on wikipedia

there is something wrong with the substitution definition.

2) You should say that the Baum-Sweet word is on the alphabet {0, 1}.

3) You should add a reference to wikipedia (see for example finite_word.py line 3568 on how to do that).

4) I do not like calling f: 00 -> 0000, 01 -> 1001, etc a morphism. The reason is that you consider the alphabet {0,1} and f is not a morphism of the free monoid {0, 1}*. It is a morphism of the submodules of words of even length that is generated by {00, 01, 10, 11} ( 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".

[mcognetta]

Thanks for catching that and the other advice.

Just to be clear,

It is a morphism of the submodule of words of even length that is generated by {00, 01, 10, 11}

Did you mean submonoid?

If so, would

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\}`:

be sufficient or should I just write it is a word over \{0,1\} with the following string substitution rules...

[vdelecroix]

Replying to mcognetta:

Thanks for catching that and the other advice.

Just to be clear,

It is a morphism of the submodule of words of even length that is generated by {00, 01, 10, 11}

Did you mean submonoid?

Yes. Sorry.

If so, would

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\}`:

This is a bit formal but precise.

be sufficient or should I just write it is a word over \{0,1\} with the following string substitution rules...

This is less formal but less precise... up to you.

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.

[mcognetta]

That was what I was considering also.

Thanks for the help.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​22d56e3

updated the docs and fixed the example

[vdelecroix]

Nicer. There is no need to have twice the substitution rules in the documentation. You can just write

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

(and be careful you wrote "submodule")

It would be nice to illustrate some of the properties of the sequence in the EXAMPLES section. For example

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

Though I do not like so much the definition of f given above.

[slabbe]

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:

Replying to mcognetta:

WordMorphism? fails with morphisms that have domains with elements of greater than length 1.

I do not agree, letters can be anything that is hashable:

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),...

But then those letter of arbitrary length are still considered as of length 1. Is this what you want?

sage: w = m([(0,0)])
sage: w
word: (0, 0),(0, 0)
sage: w.length()
2

There is also some unfortunate behavior if you try to define the morphism as a dict.

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:

sage: WordMorphism({0:[0,1], 1:[1,0]})
WordMorphism: 0->01, 1->10

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

Note also that leading zero are intepreted as octal system in Python:

sage: 0100
64

It makes sense why the above example does not work, but it would be nice if one could do it this way.

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.

Would it be possible that the description of the ticket be updated to what is now the current goal of the ticket? Thank you!

[vdelecroix]

Replying to slabbe:

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:

Replying to mcognetta: 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.

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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b1aef84

updated the docs and added a new example

[vdelecroix]

Good! Thanks for the addition. Next time do not forget to add your complete to the "Authors" field of the ticket (I did it).

[vbraun]

[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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​cc3c8b0

added extra line after a math markup section

[mcognetta]

Added an extra line after my ..MATH:: markup section and the warning went away and built the docs correctly.