Opened 4 years ago
Closed 4 years ago
#20403 closed enhancement (fixed)
Fix enumeration of finitely generated semigroups
Reported by:  tscrim  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage7.2 
Component:  algebra  Keywords:  
Cc:  sagecombinat, nthiery  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  702d333 (Commits)  Commit:  702d33315879dadcdaccfcb6c66114e9207b8c2d 
Dependencies:  #13580  Stopgaps: 
Description
We use breadthfirstsearch via RecursivelyEnumeratedSet
to iterate through the elements of a finitely generated semigroup. This will allow us to deprecate TransitiveIdeal*
Change History (19)
comment:1 Changed 4 years ago by
 Branch set to public/semigroups/iterator_finitely_generated_semigroups20403
 Commit set to a0307f3cc2e0c34a0e2228b1b41947f527def4da
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
 Commit changed from a0307f3cc2e0c34a0e2228b1b41947f527def4da to 859b05f5d9e58a553942689f739886c9e05c2301
Branch pushed to git repo; I updated commit sha1. New commits:
859b05f  Change TODO list in backtrack to state we can deprecate TransitiveIdeal* now.

comment:3 Changed 4 years ago by
Deprecation ticket is #20404.
comment:4 Changed 4 years ago by
 Commit changed from 859b05f5d9e58a553942689f739886c9e05c2301 to c427ca9ee191927200a40eaeb54dbf0adb1057b4
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c427ca9  Change TODO list in backtrack to state we can deprecate TransitiveIdeal* now.

comment:5 Changed 4 years ago by
 Commit changed from c427ca9ee191927200a40eaeb54dbf0adb1057b4 to a27f383dc8ca925fe711050df8aa4526de5db532
Branch pushed to git repo; I updated commit sha1. New commits:
a27f383  trac #20403 fixing one doctest

comment:6 Changed 4 years ago by
 Commit changed from a27f383dc8ca925fe711050df8aa4526de5db532 to c20562ebf3a7e4763b6caa5ecc7c37b13eca4223
Branch pushed to git repo; I updated commit sha1. New commits:
c20562e  trac #20403 doc formatting

comment:7 Changed 4 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
looks good to me
comment:8 Changed 4 years ago by
 Commit changed from c20562ebf3a7e4763b6caa5ecc7c37b13eca4223 to 67521dd7f14f74d975bfd74cf6ed10c4092f36a4
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:
a5f4d67  Improved doc for mapreduce

569de0d  Merge branch 'develop' into t/13580/map_reduce

b07dfe2  Doc of the two implementationsof ActiveTaskCounter

beebcbc  #13580: Added comment on timing in the doc

58eca2e  #13580: Removed comment which is now in the doc

1badd8a  #13580: Renamed ActiveTaskCounter(Posix)

46cbab9  13580: Fixed doctests to pass on Darwin

134c1fa  13580: doc rereading

4c82d1b  Merge branch 'u/hivert/ticket/13580' of trac.sagemath.org:sage into u/hivert/ticket/13580

67521dd  Merge branch 'u/hivert/ticket/13580' into public/semigroups/iterator_finitely_generated_semigroups20403

comment:10 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:12 Changed 4 years ago by
 Commit changed from 67521dd7f14f74d975bfd74cf6ed10c4092f36a4 to 6272efd5359a98368bcb7edcb583572c25bf28bc
Branch pushed to git repo; I updated commit sha1. New commits:
6272efd  Removing tab character.

comment:13 Changed 4 years ago by
 Status changed from needs_work to positive_review
comment:14 Changed 4 years ago by
 Status changed from positive_review to needs_work
There is another failure on 32bit that seems to come from this ticket: http://build.sagedev.org/release/builders/%20%20slow%20AIMS%20%20%28Debian%207%2032%20bit%29%20incremental/builds/479/steps/shell_4/logs/stdio
comment:15 Changed 4 years ago by
My own doctesting earlier this afternoon, complained about a tab in backtrack.py
as well.
comment:16 Changed 4 years ago by
The tab character should be fixed in 6272efd.
I am actually surprised the breadth first search is so consistent. It is somewhat nondeterministic because it uses a set for the next level, whereas it probably should be a list. However, that is an issue for another ticket because it will require much more largescale changes.
comment:17 Changed 4 years ago by
 Commit changed from 6272efd5359a98368bcb7edcb583572c25bf28bc to 702d33315879dadcdaccfcb6c66114e9207b8c2d
Branch pushed to git repo; I updated commit sha1. New commits:
702d333  Fix doctest output order (for 32bit).

comment:18 Changed 4 years ago by
 Status changed from needs_work to positive_review
Quickndirty fix for doctest order.
comment:19 Changed 4 years ago by
 Branch changed from public/semigroups/iterator_finitely_generated_semigroups20403 to 702d33315879dadcdaccfcb6c66114e9207b8c2d
 Resolution set to fixed
 Status changed from positive_review to closed
I want to do the deprecation on a separate ticket because only this part is needed for #17039.
New commits:
Changed iterator for finitely generated semigroups.