Opened 11 years ago

Closed 9 years ago

Last modified 6 years ago

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

Status badges

Description (last modified by tscrim)

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)

trac_12230-ss.patch (5.2 KB) - added by sstarosta 11 years ago.
tested on 5.0.beta2
trac_12230-ss-ascii.patch (5.0 KB) - added by davidloeffler 10 years ago.
ASCII-ified version; tested on 5.0.beta2 and 5.0.beta7
trac_12230-growing_letters-ss.patch (7.7 KB) - added by sstarosta 10 years ago.
tested on sage 5.5.rc0
trac_12230-growing_letters-review-vd.patch (1.6 KB) - added by vdelecroix 10 years ago.
trac_12230-growing_letters-rebase.patch (7.9 KB) - added by tscrim 9 years ago.

Download all attachments as: .zip

Change History (33)

comment:1 Changed 11 years ago by sstarosta

  • Owner changed from sage-combinat to sstarosta

comment:2 Changed 11 years ago by sstarosta

  • Dependencies set to #12466
  • Keywords Cernay2012 added

comment:3 Changed 11 years ago by sstarosta

  • Description modified (diff)
  • Status changed from new to needs_review

I lowered the goals of the ticket, the test of injectivity will follow in another ticket later.

Changed 11 years ago by sstarosta

tested on 5.0.beta2

comment:4 Changed 11 years ago by sstarosta

  • Summary changed from WordMorphism - growing letters, injectivity to WordMorphism - growing letters

comment:5 Changed 11 years ago by tmonteil

  • Cc tmonteil added

comment:6 follow-up: Changed 10 years ago by 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.

Changed 10 years ago by davidloeffler

ASCII-ified version; tested on 5.0.beta2 and 5.0.beta7

comment:7 Changed 10 years ago by davidloeffler

Apply trac_12230-ss-ascii.patch

(for the patchbot)

comment:8 in reply to: ↑ 6 Changed 10 years ago by sstarosta

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 vdelecroix

  • 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 vdelecroix

I should apologize: it's "rank" and not "unrank" which has to be used!

comment:11 Changed 10 years ago by sstarosta

Dear patchbot, would you be so kind to just apply trac_12230-growing_letters-ss.patch please?

Last edited 10 years ago by sstarosta (previous) (diff)

comment:12 Changed 10 years ago by sstarosta

  • Authors set to Stepan Starosta
  • 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 sstarosta

apply trac_12230-growing_letters-ss.patch

comment:14 Changed 10 years ago by sstarosta

  • Description modified (diff)

comment:15 Changed 10 years ago by davidloeffler

apply trac_12230-growing_letters-ss.patch

(for patchbot)

comment:16 follow-up: Changed 10 years ago by vdelecroix

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

Changed 10 years ago by sstarosta

tested on sage 5.5.rc0

comment:17 in reply to: ↑ 16 Changed 10 years ago by sstarosta

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 vdelecroix

comment:18 Changed 10 years ago by vdelecroix

  • 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 jdemeyer

  • Milestone changed from sage-5.6 to sage-pending

comment:20 Changed 9 years ago by tscrim

  • Milestone changed from sage-pending to sage-5.9

comment:21 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.9 to sage-5.10
  • Reviewers changed from vdelecroix to Vincent Delecroix

comment:22 Changed 9 years ago by jdemeyer

  • Description modified (diff)

comment:23 Changed 9 years ago by jdemeyer

  • 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 jdemeyer

  • Dependencies changed from #12466 to #8920, #12466

comment:25 Changed 9 years ago by jdemeyer

Also, trac_12230-growing_letters-review-vd.patch needs a proper commit message.

Changed 9 years ago by tscrim

comment:26 Changed 9 years ago by tscrim

  • 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 jdemeyer

  • Merged in set to sage-5.10.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:28 Changed 6 years ago by chapoton

  • Authors changed from Stepan Starosta to Štěpán Starosta
Note: See TracTickets for help on using tickets.