Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#19159 closed enhancement (fixed)

Check if a word is a Christoffel word.

Reported by: mlapointe Owned by: mlapointe
Priority: minor Milestone: sage-6.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 egunawan)

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 mlapointe

  • Authors set to Mélodie Lapointe
  • 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 mlapointe

  • Cc mlapointe nadialafreniere added

comment:3 Changed 4 years ago by mlapointe

  • Branch set to u/mlapointe/check_if_a_word_is_a_christoffel_word_

comment:4 Changed 4 years ago by mlapointe

  • Commit set to c66eadea26675e33b34f2d664c1cc31be6497d25
  • Status changed from new to needs_review

New commits:

c66eadeAdd is_christoffel function

comment:5 Changed 4 years ago by git

  • Commit changed from c66eadea26675e33b34f2d664c1cc31be6497d25 to dceb8c447b2f6ac617cb7c3328c83b47458ad2c8

Branch pushed to git repo; I updated commit sha1. New commits:

dceb8c4Make reference hyperlink.

comment:6 follow-up: Changed 4 years ago by nadialafreniere

  • Status changed from needs_review to needs_work
#A Christoffel word is a non-empty 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#python-code-style

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 git

  • Commit changed from dceb8c447b2f6ac617cb7c3328c83b47458ad2c8 to d2e74c6444c0272d63fe5a3a9591ce277624cd2b

Branch pushed to git repo; I updated commit sha1. New commits:

d2e74c6Change condition to respect the definition.

comment:8 Changed 4 years ago by git

  • Commit changed from d2e74c6444c0272d63fe5a3a9591ce277624cd2b to f1900de5e10a367c5443efca1d826df4e8cff7da

Branch pushed to git repo; I updated commit sha1. New commits:

9d731b3Add space.
f1900dechange <1 by ==0

comment:9 Changed 4 years ago by git

  • Commit changed from f1900de5e10a367c5443efca1d826df4e8cff7da to 177aecda5d5dea5e3db9b1c016ee78cccab5c4e6

Branch pushed to git repo; I updated commit sha1. New commits:

177aecdRemove a comment

comment:10 Changed 4 years ago by nadialafreniere

  • Description modified (diff)

comment:11 Changed 4 years ago by nadialafreniere

It is now getting better, but I would still like to have a doctest testing if a single-letter-word is a Christoffel word.

comment:12 Changed 4 years ago by git

  • Commit changed from 177aecda5d5dea5e3db9b1c016ee78cccab5c4e6 to 75724dcc12135aea1ed61d87eada760c70533e81

Branch pushed to git repo; I updated commit sha1. New commits:

523e350Modifying documentation.
75724dcAdd doctest for the one letter word.

comment:13 Changed 4 years ago by nadialafreniere

The description is wrong : "Equivalently, w is a Christoffel word iff w is a symmetric non-empty word and w[1:n-2] is a palindrome". It should be w[1:n-1] as in the algorithm.

comment:14 Changed 4 years ago by git

  • Commit changed from 75724dcc12135aea1ed61d87eada760c70533e81 to e3c4697ae3a68c2bdb0bee389aa8f1b39fc371bc

Branch pushed to git repo; I updated commit sha1. New commits:

e3c4697Correction of the definition

comment:15 Changed 4 years ago by nadialafreniere

  • Reviewers set to Nadia Lafrenière
  • Status changed from needs_work to positive_review

comment:16 Changed 4 years ago by egunawan

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

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 23-47. Springer-Verlag, 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: 978-0-8218-4480-9

comment:18 Changed 4 years ago by git

  • Commit changed from e3c4697ae3a68c2bdb0bee389aa8f1b39fc371bc to eda3febf9d6f07c3f8bf5bfa36eb01a3f3cda503

Branch pushed to git repo; I updated commit sha1. New commits:

eda3febMake reference as link

comment:19 Changed 4 years ago by mlapointe

  • Status changed from needs_work to needs_review

comment:20 Changed 4 years ago by nadialafreniere

  • Status changed from needs_review to positive_review

comment:21 Changed 4 years ago by vbraun

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

  • Commit eda3febf9d6f07c3f8bf5bfa36eb01a3f3cda503 deleted

As well, self[1:len(self)-1] should be transformed in self[1:len(self) - 1].

rather in self[1:-1]

Note: See TracTickets for help on using tickets.