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

### Description (last modified by )

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)

### Change History (26)

### comment:1 Changed 11 years ago by

Description: | modified (diff) |
---|

### comment:2 Changed 11 years ago by

Description: | modified (diff) |
---|---|

Summary: | upgrade defect() of a finite word to work correctly with any involutive antimorphism as generalized reversal mapping → upgrade defect() of a finite word |

### comment:3 Changed 11 years ago by

Description: | modified (diff) |
---|

### comment:4 Changed 11 years ago by

Description: | modified (diff) |
---|

### comment:5 Changed 11 years ago by

Status: | new → needs_review |
---|

### comment:6 follow-up: 8 Changed 11 years ago by

Authors: | → Stepan Starosta |
---|---|

Reviewers: | → vdelecroix |

Status: | needs_review → needs_work |

### comment:7 Changed 11 years ago by

Status: | needs_work → needs_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 follow-ups: 9 10 Changed 11 years ago by

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) TODOIt 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 Changed 11 years ago by

Reviewers: | vdelecroix → Vincent 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 Changed 11 years ago by

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:12 Changed 11 years ago by

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

Status: | needs_review → positive_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

Status: | positive_review → needs_info |
---|

Please state clearly which patches have to be applied.

### comment:15 Changed 11 years ago by

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

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.

### comment:17 follow-up: 18 Changed 11 years ago by

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

### comment:18 Changed 11 years ago by

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

Status: | needs_info → needs_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

Description: | modified (diff) |
---|---|

Status: | needs_review → positive_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

Merged in: | → sage-5.0.beta2 |
---|---|

Resolution: | → fixed |

Status: | positive_review → closed |

### comment:22 Changed 6 years ago by

Authors: | Stepan Starosta → Štěpán Starosta |
---|

**Note:**See TracTickets for help on using tickets.

Hello,

1) About documentationI 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")

2) About the algorithmI 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) TODOIt 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: