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: |
Description (last modified by )
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
- Cc vdelecroix added
comment:2 Changed 6 years ago by
- 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
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
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
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
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
I would suggest to either:
- close this ticket as won't fix
- or add a
baum_sweet
towords
so that one can dosage: words.baum_sweet() word: 1101100001000000100000000000000001000000...
comment:8 Changed 6 years ago by
I will add it to the generators in the next day or so.
Thanks for the help.
comment:9 Changed 6 years ago by
- Branch set to u/mcognetta/wordmorphism_does_not_allow_elements_of_length___1_in_the_domain
comment:10 Changed 6 years ago by
- 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:
3812f35 | added Baum-Sweet Word to word_generators
|
comment:11 Changed 6 years ago by
- 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
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
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
That was what I was considering also.
Thanks for the help.
comment:15 Changed 6 years ago by
- 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
- Status changed from needs_work to needs_review
comment:17 Changed 6 years ago by
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
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!
comment:19 in reply to: ↑ 18 Changed 6 years ago by
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
- 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
- Description modified (diff)
comment:22 Changed 6 years ago by
- 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
- 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
- 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
- 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
- Status changed from needs_review to positive_review
comment:27 Changed 6 years ago by
- 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
- 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
You can pass in words:
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?