Opened 6 years ago

Closed 6 years ago

#21769 closed enhancement (fixed)

Adding Baum-Sweet Word

Reported by: mcognetta Owned by:
Priority: minor Milestone: sage-7.5
Component: combinatorics Keywords: words, combinat, combinatorics, days79
Cc: vdelecroix, slabbe Merged in:
Authors: Marco Cognetta Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: cc3c8b0 (Commits, GitHub, GitLab) Commit: cc3c8b0ccda7162e7941bb30c31c3b9379cead05
Dependencies: Stopgaps:

Status badges

Description (last modified by tscrim)

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

Change History (28)

comment:1 Changed 6 years ago by tscrim

  • Cc vdelecroix added

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

  • Cc slabbe added

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

  • Commit set to 3812f358f4e4cc4bcf3b4ead073d16c6c781737e
  • 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:

3812f35added 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: 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

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.

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:

22d56e3updated 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: 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:

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!

Version 0, edited 6 years ago by slabbe (next)

comment:19 in reply to: ↑ 18 Changed 6 years ago by 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.

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:

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

cc3c8b0added 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)
  • Keywords days79 added
  • Summary changed from Adding Baum-Sweet Word (Was "WordMorphism does not allow elements of length > 1 in the domain") to Adding Baum-Sweet Word
  • Type changed from defect to enhancement

comment:28 Changed 6 years ago by vbraun

  • Branch changed from u/mcognetta/wordmorphism_does_not_allow_elements_of_length___1_in_the_domain to cc3c8b0ccda7162e7941bb30c31c3b9379cead05
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.