Opened 11 years ago

Closed 11 years ago

# upgrade defect() of a finite word

Reported by: Owned by: Štěpán Starosta Štěpán Starosta trivial sage-5.0 combinatorics finite word, defect, palindrome, pseudopalindrome Vincent Delecroix, Sébastien Labbé sage-5.0.beta2 Štěpán Starosta Vincent Delecroix N/A

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 :

### 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) 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 Š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: new → needs_review

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

Authors: → Stepan Starosta → vdelecroix needs_review → needs_work

Hello,

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

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_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 in reply to:  6 ; follow-ups:  9  10 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: 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 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

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_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 Jeroen Demeyer

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

apply in 4th

apply in 2nd

### comment:17 follow-up:  18 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
```

apply 1st

apply 3rd

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

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_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 Nathann Cohen

Description: modified (diff) 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 Jeroen Demeyer

Merged in: → sage-5.0.beta2 → fixed positive_review → closed

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