#31454 closed defect (fixed)

Fix bug in WordMorphism.growing_letters() and periodic_points()

Reported by: gh-mrejmon Owned by:
Priority: major Milestone: sage-9.3
Component: combinatorics Keywords:
Cc: slabbe, slelievre Merged in:
Authors: Martin Rejmon Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 87a8aae (Commits, GitHub, GitLab) Commit: 87a8aaef146b79d3905c06b24abc92a722477a59
Dependencies: Stopgaps:

Status badges

Description

1)

sage: WordMorphism('a->a').is_growing('a')
True

should return False.

This happens due to the if self.is_primitive(): return True optimization. Easily fixable for example like this:

-       if self.is_primitive():
+       if self.is_primitive() and len(self._morph) > 1:
            return True

2)

sage: WordMorphism('a->a,b->bb').periodic_points()
Traceback (most recent call last):
...
ValueError: generator already executing

should return [[word: bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...]].

I think this happens because periodic_points() doesn't check whether the letters are growing, so the following should fix it (assuming we only care about periodic points with infinite length):

        A = self.domain().alphabet()
        d = dict((letter,self(letter)[0]) for letter in A)
+       G = set(self.growing_letters())

        res = []
        parent = self.codomain().shift()
        for cycle in get_cycles(CallableDict(d),A):
+           if cycle[0] in G:
                P = PeriodicPointIterator(self, cycle)
                res.append([parent(P._cache[i]) for i in range(len(cycle))])

I added a branch with the proposed fixes.

Change History (8)

comment:1 Changed 18 months ago by gh-mrejmon

  • Status changed from new to needs_review

comment:2 Changed 18 months ago by slelievre

  • Cc slabbe slelievre added

comment:3 Changed 18 months ago by slabbe

Thanks for proposing such fixes. I will take a look as soon as possible.

comment:4 follow-up: Changed 17 months ago by vdelecroix

Martin. Your branch should include the two doctests that are in the ticket description. Since the sage doctests are run it will prevent the bug to occur again in the future.

comment:5 Changed 17 months ago by git

  • Commit changed from 085165a8432d47f73870f83385200a1ad9cf4837 to 87a8aaef146b79d3905c06b24abc92a722477a59

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

87a8aaeAdd regression tests

comment:6 in reply to: ↑ 4 Changed 17 months ago by gh-mrejmon

Replying to vdelecroix:

Martin. Your branch should include the two doctests that are in the ticket description. Since the sage doctests are run it will prevent the bug to occur again in the future.

Done.

comment:7 Changed 17 months ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

thanks!

comment:8 Changed 17 months ago by vbraun

  • Branch changed from u/gh-mrejmon/fix_growing_and_periodic to 87a8aaef146b79d3905c06b24abc92a722477a59
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.