#19159 closed enhancement (fixed)
Check if a word is a Christoffel word.
Reported by:  mlapointe  Owned by:  mlapointe 

Priority:  minor  Milestone:  sage6.9 
Component:  combinatorics  Keywords:  words, Christoffel, days69 
Cc:  mlapointe, egunawan, nadialafreniere  Merged in:  
Authors:  Mélodie Lapointe  Reviewers:  Nadia Lafrenière 
Report Upstream:  N/A  Work issues:  
Branch:  eda3feb (Commits)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
Add a function in the class word to check if a word is a Christoffel word.
(It is best to pull this ticket on top of 6.9 beta 5)
Change History (22)
comment:1 Changed 4 years ago by
 Component changed from PLEASE CHANGE to combinatorics
 Description modified (diff)
 Keywords words Christoffel days69 added
 Owner changed from (none) to mlapointe
 Priority changed from major to minor
 Summary changed from is_christoffel to Check if a word is a Christoffel word.
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 4 years ago by
 Cc mlapointe nadialafreniere added
comment:3 Changed 4 years ago by
 Branch set to u/mlapointe/check_if_a_word_is_a_christoffel_word_
comment:4 Changed 4 years ago by
 Commit set to c66eadea26675e33b34f2d664c1cc31be6497d25
 Status changed from new to needs_review
comment:5 Changed 4 years ago by
 Commit changed from c66eadea26675e33b34f2d664c1cc31be6497d25 to dceb8c447b2f6ac617cb7c3328c83b47458ad2c8
Branch pushed to git repo; I updated commit sha1. New commits:
dceb8c4  Make reference hyperlink.

comment:6 followup: ↓ 22 Changed 4 years ago by
 Status changed from needs_review to needs_work
#A Christoffel word is a nonempty word over a binary alphabet
+ if len(self) < 0 or len(self.letters()) > 2 or self.is_palindrome():
+ return False
+ elif self.is_symmetric() and self[1:len(self)1].is_palindrome():
+ return True
+ else:
+ return False
A comment should always start with a space after '#'. As well, self[1:len(self)1]
should be transformed in self[1:len(self)  1]
. For more info on Python and Sage conventions, see http://doc.sagemath.org/html/en/developer/coding_basics.html#pythoncodestyle
I'm also wondering about the first condition: When the length of a word can be strictly shorter than 0?
Also, a single letter is a Christoffel word, according to the reference you give (Berstel et al.) Right now, it returns false because it is a palindrome. You should add a test for it.
comment:7 Changed 4 years ago by
 Commit changed from dceb8c447b2f6ac617cb7c3328c83b47458ad2c8 to d2e74c6444c0272d63fe5a3a9591ce277624cd2b
Branch pushed to git repo; I updated commit sha1. New commits:
d2e74c6  Change condition to respect the definition.

comment:8 Changed 4 years ago by
 Commit changed from d2e74c6444c0272d63fe5a3a9591ce277624cd2b to f1900de5e10a367c5443efca1d826df4e8cff7da
comment:9 Changed 4 years ago by
 Commit changed from f1900de5e10a367c5443efca1d826df4e8cff7da to 177aecda5d5dea5e3db9b1c016ee78cccab5c4e6
Branch pushed to git repo; I updated commit sha1. New commits:
177aecd  Remove a comment

comment:10 Changed 4 years ago by
 Description modified (diff)
comment:11 Changed 4 years ago by
It is now getting better, but I would still like to have a doctest testing if a singleletterword is a Christoffel word.
comment:12 Changed 4 years ago by
 Commit changed from 177aecda5d5dea5e3db9b1c016ee78cccab5c4e6 to 75724dcc12135aea1ed61d87eada760c70533e81
comment:13 Changed 4 years ago by
The description is wrong : "Equivalently, w
is a Christoffel word iff w
is a symmetric
nonempty word and w[1:n2]
is a palindrome". It should be w[1:n1]
as in the algorithm.
comment:14 Changed 4 years ago by
 Commit changed from 75724dcc12135aea1ed61d87eada760c70533e81 to e3c4697ae3a68c2bdb0bee389aa8f1b39fc371bc
Branch pushed to git repo; I updated commit sha1. New commits:
e3c4697  Correction of the definition

comment:15 Changed 4 years ago by
 Reviewers set to Nadia Lafrenière
 Status changed from needs_work to positive_review
comment:16 Changed 4 years ago by
 Cc egunawan added
 Description modified (diff)
 Status changed from positive_review to needs_work
The line See for instance _[1] and _[2].
should be replaced with See for instance [1]_ and [2]_.
in order to create the hyperlinks for the two references.
comment:17 Changed 4 years ago by
Also, you need to write the following format for the hyperlinks to work:
REFERENCES:
.. [1] Jean Berstel. Sturmian and episturmian words (a survey of
some recent results). In S. Bozapalidis and G. Rahonis, editors, CAI 2007,volume 4728 of Lecture Notes in Computer Science, pages 2347. SpringerVerlag, 2007.
.. [2] J. Berstel, A. Lauve, C. R., F. Saliola, Combinatorics on
words: Christoffel words and repetitions in words, CRM Monograph Series, 27. American Mathematical Society, Providence, RI, 2009. xii+147 pp. ISBN: 9780821844809
comment:18 Changed 4 years ago by
 Commit changed from e3c4697ae3a68c2bdb0bee389aa8f1b39fc371bc to eda3febf9d6f07c3f8bf5bfa36eb01a3f3cda503
Branch pushed to git repo; I updated commit sha1. New commits:
eda3feb  Make reference as link

comment:19 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:20 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:21 Changed 4 years ago by
 Branch changed from u/mlapointe/check_if_a_word_is_a_christoffel_word_ to eda3febf9d6f07c3f8bf5bfa36eb01a3f3cda503
 Resolution set to fixed
 Status changed from positive_review to closed
comment:22 in reply to: ↑ 6 Changed 4 years ago by
 Commit eda3febf9d6f07c3f8bf5bfa36eb01a3f3cda503 deleted
As well,
self[1:len(self)1]
should be transformed inself[1:len(self)  1]
.
rather in self[1:1]
New commits:
Add is_christoffel function