Opened 6 years ago

Closed 6 years ago

## #21769 closed enhancement (fixed)

Reported by: Owned by: mcognetta minor sage-7.5 combinatorics words, combinat, combinatorics, days79 vdelecroix, slabbe Marco Cognetta Vincent Delecroix N/A cc3c8b0 cc3c8b0ccda7162e7941bb30c31c3b9379cead05

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

### comment:1 Changed 6 years ago by 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?

### comment:2 Changed 6 years ago by 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?).

### comment:3 Changed 6 years ago by mcognetta

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

### comment:4 Changed 6 years ago by 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.

### comment:5 Changed 6 years ago by 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.

### comment:6 Changed 6 years ago by 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...
```

### comment:7 Changed 6 years ago by 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...
```

### comment:8 Changed 6 years ago by mcognetta

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

Thanks for the help.

### comment:9 Changed 6 years ago by mcognetta

• Branch set to u/mcognetta/wordmorphism_does_not_allow_elements_of_length___1_in_the_domain

### comment:10 Changed 6 years ago by mcognetta

• Status changed from new to needs_review
• Summary changed from WordMorphism does not allow elements of length > 1 in the domain to Adding Baum-Sweet Word (Was "WordMorphism does not allow elements of length > 1 in the domain")

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`

### comment:11 Changed 6 years ago by vdelecroix

• Reviewers set to Vincent Delecroix
• Status changed from needs_review to needs_work

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

### comment:12 follow-up: ↓ 13 Changed 6 years ago by 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...

### comment:13 in reply to: ↑ 12 Changed 6 years ago by vdelecroix

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.

### comment:14 Changed 6 years ago by mcognetta

That was what I was considering also.

Thanks for the help.

### comment:15 Changed 6 years ago by git

• Commit changed from 3812f358f4e4cc4bcf3b4ead073d16c6c781737e to 22d56e3828500d55a1b6f948f77d8470b1bf11eb

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

 ​22d56e3 `updated the docs and fixed the example`

### comment:16 Changed 6 years ago by mcognetta

• Status changed from needs_work to needs_review

### comment:17 Changed 6 years ago by 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.

### comment:18 in reply to: ↑ description ; follow-up: ↓ 19 Changed 6 years ago by 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:

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

Therefore, I do not see what you are expecting from this part of the description of the ticket:

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

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

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!

Last edited 6 years ago by slabbe (previous) (diff)

### comment:19 in reply to: ↑ 18 Changed 6 years ago by vdelecroix

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.

### comment:20 Changed 6 years ago by git

• Commit changed from 22d56e3828500d55a1b6f948f77d8470b1bf11eb to b1aef84b1de0a55db584a9834222d3b00eb92e48

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

 ​b1aef84 `updated the docs and added a new example`

### comment:21 Changed 6 years ago by mcognetta

• Description modified (diff)

### comment:22 Changed 6 years ago by vdelecroix

• Authors set to Marco Cognetta
• Status changed from needs_review to positive_review

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

### comment:23 Changed 6 years ago by vbraun

• Status changed from positive_review to needs_work
```[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.
```

### comment:24 Changed 6 years ago by git

• Commit changed from b1aef84b1de0a55db584a9834222d3b00eb92e48 to cc3c8b0ccda7162e7941bb30c31c3b9379cead05

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

 ​cc3c8b0 `added extra line after a math markup section`

### comment:25 Changed 6 years ago by mcognetta

• Status changed from needs_work to needs_review

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

### comment:26 Changed 6 years ago by vdelecroix

• Status changed from needs_review to positive_review

### comment:27 Changed 6 years ago by tscrim

• Description modified (diff)