#12230 closed enhancement (fixed)
WordMorphism - growing letters
Reported by: | sstarosta | Owned by: | sstarosta |
---|---|---|---|
Priority: | major | Milestone: | sage-5.10 |
Component: | combinatorics | Keywords: | Cernay2012 |
Cc: | vdelecroix, slabbe, tmonteil | Merged in: | sage-5.10.beta0 |
Authors: | Štěpán Starosta | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #8920, #12466 | Stopgaps: |
Description (last modified by )
Enhance WordMorphism? with the analysis of growing/non-growing letters (the letter a is growing of |sigman(a)| tends to infinity)
Motivation comes from substitutive languages, see #12227.
apply in that order
Attachments (5)
Change History (33)
comment:1 Changed 11 years ago by
- Owner changed from sage-combinat to sstarosta
comment:2 Changed 11 years ago by
- Dependencies set to #12466
- Keywords Cernay2012 added
comment:3 Changed 11 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:4 Changed 11 years ago by
- Summary changed from WordMorphism - growing letters, injectivity to WordMorphism - growing letters
comment:5 Changed 11 years ago by
- Cc tmonteil added
comment:6 follow-up: ↓ 8 Changed 10 years ago by
Hi Stepan,
I'm afraid that the accented characters in your HG username seem to cause problems: they're getting garbaged somewhere (judging by the output of the patchbot). The patchbot also doesn't like code lines with trailing whitespace on them. So I've done a new version of your patch, which is functionally identical to the old one; hope that's OK.
comment:7 Changed 10 years ago by
Apply trac_12230-ss-ascii.patch
(for the patchbot)
comment:8 in reply to: ↑ 6 Changed 10 years ago by
Replying to davidloeffler:
Hi Stepan,
I'm afraid that the accented characters in your HG username seem to cause problems: they're getting garbaged somewhere (judging by the output of the patchbot). The patchbot also doesn't like code lines with trailing whitespace on them. So I've done a new version of your patch, which is functionally identical to the old one; hope that's OK.
Hi David,
thanks, the patchbot looks happy now.
Stepan
comment:9 Changed 10 years ago by
- Reviewers set to vdelecroix
- Status changed from needs_review to needs_work
Hello,
Very useful patch!
Ameliorations
1) The function is letter_growing can be made in a nicer way by replacing
rcs = self.rational_contractive_space() alphabet = self.domain().alphabet() parikh_vector = [0 for i in xrange(len(alphabet))] parikh_vector[alphabet.list().index(letter)] = 1 return not vector(parikh_vector) in rcs
by
rcs = self.rational_contractive_space() V = rcs.ambient_vector_space() i = self.domain().alphabet().unrank(letter) return not V.basis()[i] in rcs
2) In rational_contractive_space you can access coefficient of degree 0 of a polynom P with P[0].
Some points of terminology and usability
1) Why do you prefer 'letter_growing' instead of 'growing_letter' ? (which is the name it has in CANT)
2) It should be useful to have as well a 'bounded_letter' method. If not we have to use 'not s.is_growing_letter(letter)'. It's up to you, I'm not sure about what is better.
3) What you called the "contractive subspace" is actually called "central stable space" in dynamics. The stable space (or contractive space) is reserved for the subspace where eigenvalues are strictly less than 1 in absolute value. But then, the name 'rational_central_stable_space' won't be very fancy but on the other hand it is not intended to be used by the front-end user.
comment:10 Changed 10 years ago by
I should apologize: it's "rank" and not "unrank" which has to be used!
comment:11 Changed 10 years ago by
Dear patchbot, would you be so kind to just apply trac_12230-growing_letters-ss.patch please?
comment:12 Changed 10 years ago by
- Status changed from needs_work to needs_review
Thanks for the comments. I modified and updated the patch accordingly.
comment:13 Changed 10 years ago by
apply trac_12230-growing_letters-ss.patch
comment:14 Changed 10 years ago by
- Description modified (diff)
comment:15 Changed 10 years ago by
apply trac_12230-growing_letters-ss.patch
(for patchbot)
comment:16 follow-up: ↓ 17 Changed 10 years ago by
Algorithmic
- if the substitution is primitive all letters are growing (and the test cost much less). I think that a first step in both is_growing and growing_letters would be the test of primitivity.
Docstring
- in growing_letters(): you may change "Returns a list" by "Returns the list"
After that, the patch seems ready to positive review.
Vincent
comment:17 in reply to: ↑ 16 Changed 10 years ago by
Replying to vdelecroix:
- if the substitution is primitive all letters are growing (and the test cost much less). I think that a first step in both is_growing and growing_letters would be the test of primitivity.
Done.
- in growing_letters(): you may change "Returns a list" by "Returns the list"
Done.
Many thanks, Stepan
apply trac_12230-growing_letters-ss.patch
(for patchbot)
Changed 10 years ago by
comment:18 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
I modified the documentation strings to fit with Sage standards. I set to positive review.
Nice patch! Vincent
PS (for patchbot):
apply trac_12230-growing_letters-ss.patch trac_12230-growing_letters-review-vd.patch
comment:19 Changed 10 years ago by
- Milestone changed from sage-5.6 to sage-pending
comment:20 Changed 9 years ago by
- Milestone changed from sage-pending to sage-5.9
comment:21 Changed 9 years ago by
- Milestone changed from sage-5.9 to sage-5.10
- Reviewers changed from vdelecroix to Vincent Delecroix
comment:22 Changed 9 years ago by
- Description modified (diff)
comment:23 Changed 9 years ago by
- Status changed from positive_review to needs_work
trac_12230-growing_letters-ss.patch should be rebased to sage-5.9.beta3.
comment:24 Changed 9 years ago by
- Dependencies changed from #12466 to #8920, #12466
comment:25 Changed 9 years ago by
Also, trac_12230-growing_letters-review-vd.patch needs a proper commit message.
Changed 9 years ago by
comment:26 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to positive_review
I've uploaded a combined rebased patch and just did a quick tweak to the reference to have a better name.
comment:27 Changed 9 years ago by
- Merged in set to sage-5.10.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
I lowered the goals of the ticket, the test of injectivity will follow in another ticket later.