Opened 11 years ago

Closed 11 years ago

Last modified 6 years ago

#12150 closed enhancement (fixed)

upgrade defect() of a finite word

Reported by: Štěpán Starosta Owned by: Štěpán Starosta
Priority: trivial Milestone: sage-5.0
Component: combinatorics Keywords: finite word, defect, palindrome, pseudopalindrome
Cc: Vincent Delecroix, Sébastien Labbé Merged in: sage-5.0.beta2
Authors: Štěpán Starosta Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Nathann Cohen)

Update defect() method of a finite word to calculate the defect for generalized palindromes. Apply the four patches.

Details: the defect is the difference between the maximum number of palindromic factors in a word and their actual count. If we count generalized palindromes (or f-palindromes, theta-palindromes, pseudopalindromes...), the upper bound needs to be corrected according to (Š. Starosta, On Theta-palindromic Richness, Theoret. Comp. Sci. 412 (2011) 1111-1121, DOI: 10.1016/j.tcs.2010.12.011).

Original behavior:

sage: f = WordMorphism('a->b,b->a')
sage: Word('abbabaabbaababba').defect(f)
4

Expected:

sage: f = WordMorphism('a->b,b->a')
sage: Word('abbabaabbaababba').defect(f)
3

The method is_full() also needs to be updated to be compliant with the generalized definition of defect:

now

sage: f = WordMorphism('a->b,b->a')
sage: w = Word('ab')
sage: w.is_full(f)
False

expected

sage: f = WordMorphism('a->b,b->a')
sage: w = Word('ab')
sage: w.is_full(f)
True

Apply :

Attachments (4)

trac_12150-review2.patch (3.9 KB) - added by Vincent Delecroix 11 years ago.
apply in 4th
trac_12150-review.patch (5.9 KB) - added by Vincent Delecroix 11 years ago.
apply in 2nd
trac_12150.patch (4.6 KB) - added by Štěpán Starosta 11 years ago.
apply 1st
trac_12150-reviewed.patch (9.2 KB) - added by Štěpán Starosta 11 years ago.
apply 3rd

Download all attachments as: .zip

Change History (26)

comment:1 Changed 11 years ago by Štěpán Starosta

Description: modified (diff)

comment:2 Changed 11 years ago by Štěpán Starosta

Description: modified (diff)
Summary: upgrade defect() of a finite word to work correctly with any involutive antimorphism as generalized reversal mappingupgrade defect() of a finite word

comment:3 Changed 11 years ago by Štěpán Starosta

Description: modified (diff)

comment:4 Changed 11 years ago by Štěpán Starosta

Description: modified (diff)

comment:5 Changed 11 years ago by Štěpán Starosta

Status: newneeds_review

comment:6 Changed 11 years ago by Vincent Delecroix

Authors: Stepan Starosta
Reviewers: vdelecroix
Status: needs_reviewneeds_work

Hello,

1) About documentation

I think you should consider two parts in the documentation. The first paragraph should describe the function with the argument set to None (which is the general behavior that a user would like). And another one for the generalized version. (I made a proposition in the patch)

I also rewrite the examples in order to include a theorem and a conjecture.

You should add references to (see the "NEED REFERENCE")

  • the fact that the maximal number of palindromic factors in a word is the length of the word +1
  • the fact that Sturmian words are full of palindrome
  • the conjecture about defect 0 or infinity for Sturmian words

2) About the algorithm

I change the construction of the "real" alphabet of the word. You used w.factor_set(1) which need the computation of the suffix_trie. I suggest set(w). I rewrite the function, I find it better that way. I hope you agree. (see in the patch)

3) TODO

It could be very nice to have a function which returns the "defects of prefixes". In other word, in one call I would like to be able to get the following:

sage: w=words.ThueMorseWord()[:20]
sage: [w[:i].defect() for i in xrange(20)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

comment:7 Changed 11 years ago by Štěpán Starosta

Status: needs_workneeds_review

Hi,

thanks a lot for the review.

1. Ok, thanks. I gladly accept. I made a few modifications to you proposition, added the references and some more examples.

2. Nice python/sage magic, I wasn't able to get it working that way. Thank you.

3. Nice suggestion. In fact, this would be the output of a different (and mainly faster) algorithm to calculate the defect. I am planning on doing in for the defected generalized to more symmetries at a time. I will open a ticket for that.

comment:8 in reply to:  6 ; Changed 11 years ago by Sébastien Labbé

Hi,

Extending the definition of full for f-palindromes is a good question. That is the reason why I left it coded that way. Now that Stepan studied the question in a paper, I agree to adapt the definition in Sage as what Stepan suggests. On two letters a and b, am I right to say that abababab... and babababab... are the only two words that are E-full where E is the exchange of a and b?

3) TODO

It could be very nice to have a function which returns the "defects of prefixes". In other word, in one call I would like to be able to get the following:

sage: w=words.ThueMorseWord()[:20]
sage: [w[:i].defect() for i in xrange(20)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

This is already done by the method lacunas (from which you can regenerate the above list of repeated numbers). A lacuna is a position where there are no new palindrome finishing there or equivalently, the defect goes up by one. Here are some examples from the doctests :

sage: w = Word([0,1,1,2,3,4,5,1,13,3])                              
sage: w.lacunas()                                                   
[7, 9]                                                              
sage: words.ThueMorseWord()[:100].lacunas()                         
[8, 9, 24, 25, 32, 33, 34, 35, 36, 37, 38, 39, 96, 97, 98, 99]      
sage: f = WordMorphism({0:[1],1:[0]})                               
sage: words.ThueMorseWord()[:50].lacunas(f)
[0, 2, 4, 12, 16, 17, 18, 19, 48, 49]

By merging both patches, Stepan becomes author of what Vincent did. Usually, we keep both patches separated. Anyway, which patche(s) should be reviewed? the last one only? Right now, the patchbot tries to apply all of them which fails...

Sébastien

comment:9 in reply to:  8 Changed 11 years ago by Sébastien Labbé

Reviewers: vdelecroixVincent Delecroix

By merging both patches, Stepan becomes author of what Vincent did. Usually, we keep both patches separated. Anyway, which patche(s) should be reviewed? the last one only? Right now, the patchbot tries to apply all of them which fails...

Sébastien

Also, it is bad to merge patches that have already been reviewed because one needs to start over to do the next review. Also, it is impossible to see what Stepan did after Vincent suggestions and patch. Stepan, could you please post a another patch which would replace the third and that would apply on the first two and that would contain only modification made without merge?

Thanks,

Sébastien

comment:10 in reply to:  8 Changed 11 years ago by Štěpán Starosta

Hi Sébastien,

thanks for the comment.

On two letters a and b, am I right to say that abababab... and babababab... are the only two words that are E-full where E is the exchange of a and b?

Yes. To have finite defect implies some other properties, for instance, there have to be overlaps at some point (in the infinite word).

This is already done by the method lacunas (from which you can regenerate the above list of repeated numbers). A lacuna is a position where there are no new palindrome finishing there or equivalently, the defect goes up by one. Here are some examples from the doctests :

sage: w = Word([0,1,1,2,3,4,5,1,13,3])                              
sage: w.lacunas()                                                   
[7, 9]                                                              
sage: words.ThueMorseWord()[:100].lacunas()                         
[8, 9, 24, 25, 32, 33, 34, 35, 36, 37, 38, 39, 96, 97, 98, 99]      
sage: f = WordMorphism({0:[1],1:[0]})                               
sage: words.ThueMorseWord()[:50].lacunas(f)
[0, 2, 4, 12, 16, 17, 18, 19, 48, 49]

Ok, thanks! I forgot about that. I should maybe update the comment in that method also and check if it works fine with the modifications done.

Stepan, could you please post a another patch which would replace the third and that would apply on the first two and that would contain only modification made without merge?

My bad, I will do it as you suggest, I can replace the file so it should be fine.

Thanks, Stepan

comment:11 Changed 11 years ago by Sébastien Labbé

Great!

Sébastien

comment:12 Changed 11 years ago by Štěpán Starosta

Hi,

I replaced the last patch by the correct one, they all should work now.

I also updated the comments in the methods palindromic_lacunas_study(), lacunas(), is_palindrome().

Stepan

comment:13 Changed 11 years ago by Vincent Delecroix

Status: needs_reviewpositive_review

I change the way the references are displayed in the method defect. All test passed, documentation builds and many precisions added !

Positive review.

comment:14 Changed 11 years ago by Jeroen Demeyer

Status: positive_reviewneeds_info

Please state clearly which patches have to be applied.

comment:15 Changed 11 years ago by Vincent Delecroix

Description: modified (diff)

Sorry for that... the four patches need to be applied in the order they appear.

comment:16 Changed 11 years ago by Jeroen Demeyer

trac_12150-review.patch is missing a username (this shouldn't happen if you make the patch with hg export) and a commit message.

trac_12150-reviewed.patch needs a proper commit message.

Changed 11 years ago by Vincent Delecroix

Attachment: trac_12150-review2.patch added

apply in 4th

Changed 11 years ago by Vincent Delecroix

Attachment: trac_12150-review.patch added

apply in 2nd

comment:17 Changed 11 years ago by Jeroen Demeyer

The first patch doesn't apply any more (to sage-4.8.alpha4):

applying /mnt/usb1/scratch/jdemeyer/merger/patches/trac_12150.patch
patching file sage/combinat/words/finite_word.py
Hunk #1 FAILED at 1952
Hunk #2 FAILED at 1984
Hunk #3 FAILED at 1996
Hunk #4 succeeded at 2042 with fuzz 2 (offset 0 lines).
3 out of 5 hunks FAILED -- saving rejects to file sage/combinat/words/finite_word.py.rej
abort: patch failed to apply

Changed 11 years ago by Štěpán Starosta

Attachment: trac_12150.patch added

apply 1st

Changed 11 years ago by Štěpán Starosta

Attachment: trac_12150-reviewed.patch added

apply 3rd

comment:18 in reply to:  17 Changed 11 years ago by Štěpán Starosta

Replying to jdemeyer:

The first patch doesn't apply any more (to sage-4.8.alpha4):

Sorry for the problems, it should be ok now.

comment:19 Changed 11 years ago by Sébastien Labbé

Status: needs_infoneeds_review

For the patchbot:

Apply trac_12150.patch trac_12150-review.patch trac_12150-reviewed.patch trac_12150-review2.patch

comment:20 Changed 11 years ago by Nathann Cohen

Description: modified (diff)
Status: needs_reviewpositive_review

Considering it was already reviewed, I just checked it applied on beta1 and passes tests. And that went good :-)

Nathann

comment:21 Changed 11 years ago by Jeroen Demeyer

Merged in: sage-5.0.beta2
Resolution: fixed
Status: positive_reviewclosed

comment:22 Changed 6 years ago by Frédéric Chapoton

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