Opened 8 years ago
Closed 8 years ago
#8095 closed defect (fixed)
is_primitive of WordMorphism is broken
Reported by: | slabbe | Owned by: | slabbe |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3.2 |
Component: | combinatorics | Keywords: | |
Cc: | abmasse | Merged in: | sage-4.3.2.alpha1 |
Authors: | Sébastien Labbé | Reviewers: | Alexandre Blondin Massé |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Let us define the following morphism over 3 letters:
sage: substitution=WordMorphism('a->b,b->ac,c->a')
Then we get
sage: substitution.is_primitive() False
but also
sage: (substitution^2).is_primitive() True
expected behaviour:
See the description of ".is_primitive()": Returns True if self is primitive. A morphism ϕ is primitive if there exists an positive integer k such that for all α∈Σ, ϕk(α) contains all the letters of Σ.
So, if a morphism is primitive, so are all its powers. And if there is a power which is primitive, so is the morphism itself. In the example above, both outputs should be "True".
This was reported here (via 'Report a problem'):
http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/5ed1186c229e7343?hl=en
Attachments (1)
Change History (7)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Cc abmasse added; slabbe removed
- Status changed from new to needs_review
comment:3 Changed 8 years ago by
- Status changed from needs_review to needs_work
comment:4 Changed 8 years ago by
- Status changed from needs_work to needs_review
I found a reference for the above statement (Automatic sequences of Allouche and Shallit).
comment:5 Changed 8 years ago by
- Reviewers set to abmasse
- Status changed from needs_review to positive_review
Tested on sage-4.3.1 as well and it works.
It fixes the reported problem as well.
All tests passed when running sage -t morphism.py".
Positive review.
comment:6 Changed 8 years ago by
- Merged in set to sage-4.3.2.alpha1
- Resolution set to fixed
- Reviewers changed from abmasse to Alexandre Blondin Massé
- Status changed from positive_review to closed
I just posted a patch which solves the described problem. The solution uses the following algorithm:
Are we sure this is true? Is there a proof of that somewhere?