#12150: upgrade defect() of a finite word
-----------------------------+----------------------------------------------
Reporter: sstarosta | Owner: sstarosta
Type: enhancement | Status: needs_work
Priority: trivial | Milestone: sage-4.8
Component: combinatorics | Keywords: finite word, defect,
palindrome, pseudopalindrome
Work_issues: | Upstream: N/A
Reviewer: vdelecroix | Author: Stepan Starosta
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by newvalueoldvalue):
* status: needs_review => needs_work
* reviewer: => vdelecroix
* author: => Stepan Starosta
Comment:
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]
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12150#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
