Opened 4 years ago

Closed 4 years ago

#20403 closed enhancement (fixed)

Fix enumeration of finitely generated semigroups

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-7.2
Component: algebra Keywords:
Cc: sage-combinat, 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 breadth-first-search 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 tscrim

  • Branch set to public/semigroups/iterator_finitely_generated_semigroups-20403
  • Commit set to a0307f3cc2e0c34a0e2228b1b41947f527def4da
  • Status changed from new to needs_review

I want to do the deprecation on a separate ticket because only this part is needed for #17039.


New commits:

a0307f3Changed iterator for finitely generated semigroups.

comment:2 Changed 4 years ago by git

  • Commit changed from a0307f3cc2e0c34a0e2228b1b41947f527def4da to 859b05f5d9e58a553942689f739886c9e05c2301

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

859b05fChange TODO list in backtrack to state we can deprecate TransitiveIdeal* now.

comment:3 Changed 4 years ago by tscrim

Deprecation ticket is #20404.

comment:4 Changed 4 years ago by git

  • Commit changed from 859b05f5d9e58a553942689f739886c9e05c2301 to c427ca9ee191927200a40eaeb54dbf0adb1057b4

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c427ca9Change TODO list in backtrack to state we can deprecate TransitiveIdeal* now.

comment:5 Changed 4 years ago by git

  • Commit changed from c427ca9ee191927200a40eaeb54dbf0adb1057b4 to a27f383dc8ca925fe711050df8aa4526de5db532

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

a27f383trac #20403 fixing one doctest

comment:6 Changed 4 years ago by git

  • Commit changed from a27f383dc8ca925fe711050df8aa4526de5db532 to c20562ebf3a7e4763b6caa5ecc7c37b13eca4223

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

c20562etrac #20403 doc formatting

comment:7 Changed 4 years ago by chapoton

  • 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 git

  • 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:

a5f4d67Improved doc for map-reduce
569de0dMerge branch 'develop' into t/13580/map_reduce
b07dfe2Doc 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)
46cbab913580: Fixed doctests to pass on Darwin
134c1fa13580: doc rereading
4c82d1bMerge branch 'u/hivert/ticket/13580' of trac.sagemath.org:sage into u/hivert/ticket/13580
67521ddMerge branch 'u/hivert/ticket/13580' into public/semigroups/iterator_finitely_generated_semigroups-20403

comment:9 Changed 4 years ago by tscrim

  • Dependencies set to #13580

Trivial conflict/rebase over #13580.

comment:10 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:11 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

See patchbot

comment:12 Changed 4 years ago by git

  • Commit changed from 67521dd7f14f74d975bfd74cf6ed10c4092f36a4 to 6272efd5359a98368bcb7edcb583572c25bf28bc

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

6272efdRemoving tab character.

comment:13 Changed 4 years ago by tscrim

  • Status changed from needs_work to positive_review

comment:14 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

comment:15 Changed 4 years ago by fbissey

My own doctesting earlier this afternoon, complained about a tab in backtrack.py as well.

comment:16 Changed 4 years ago by tscrim

The tab character should be fixed in 6272efd.

I am actually surprised the breadth first search is so consistent. It is somewhat non-deterministic 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 large-scale changes.

Last edited 4 years ago by tscrim (previous) (diff)

comment:17 Changed 4 years ago by git

  • Commit changed from 6272efd5359a98368bcb7edcb583572c25bf28bc to 702d33315879dadcdaccfcb6c66114e9207b8c2d

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

702d333Fix doctest output order (for 32-bit).

comment:18 Changed 4 years ago by tscrim

  • Status changed from needs_work to positive_review

Quick-n-dirty fix for doctest order.

comment:19 Changed 4 years ago by vbraun

  • Branch changed from public/semigroups/iterator_finitely_generated_semigroups-20403 to 702d33315879dadcdaccfcb6c66114e9207b8c2d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.