#12150: upgrade defect() of a finite word
-----------------------------+----------------------------------------------
Reporter: sstarosta | Owner: sstarosta
Type: enhancement | Status: needs_review
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:
-----------------------------+----------------------------------------------
Comment(by slabbe):
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12150#comment:8>
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.
