#18002 closed enhancement (fixed)
Submonoids and subsemigroup defined by generators
Reported by: | virmaux | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.6 |
Component: | combinatorics | Keywords: | monoids, days64 |
Cc: | nthiery, aschilling, days64 | Merged in: | |
Authors: | Nicolas M. Thiéry, Aladin Virmaux | Reviewers: | Anne Schilling |
Report Upstream: | N/A | Work issues: | |
Branch: | a8306e4 (Commits, GitHub, GitLab) | Commit: | |
Dependencies: | #17160 | Stopgaps: |
Description (last modified by )
Implement subsemigroups generated by elements of an ambient semigroups, lazily constructing all the elements and their Cayley graph relations.
Here is a quick example from the documentation:
sage: R = IntegerModRing(12) sage: R.submonoid([R(3), R(5)], one = R.one()) sage: M.cardinality() 4
This builds on and supersedes the old patch
automatic_monoid-nt.patch
from the Sage-Combinat mercurial queue.
Change History (61)
comment:1 Changed 6 years ago by
- Branch set to u/virmaux/automaticmonoid
comment:2 Changed 6 years ago by
- Branch u/virmaux/automaticmonoid deleted
- Type changed from PLEASE CHANGE to enhancement
comment:3 Changed 6 years ago by
- Branch set to u/virmaux/automaticmonoid
comment:4 Changed 6 years ago by
- Commit set to bd807f4ccea8565feb8e2984476ee7cb4f18b404
comment:5 Changed 6 years ago by
- Description modified (diff)
comment:6 Changed 6 years ago by
- Commit changed from bd807f4ccea8565feb8e2984476ee7cb4f18b404 to da7db1d95e91c50fd4d91958561e676ac828dc4d
Branch pushed to git repo; I updated commit sha1. New commits:
da7db1d | documentation and tests
|
comment:7 Changed 6 years ago by
- Commit changed from da7db1d95e91c50fd4d91958561e676ac828dc4d to 36dccd7e16e688e897514d471b0f21aa87d6e774
Branch pushed to git repo; I updated commit sha1. New commits:
36dccd7 | 18002: I do not understand a function
|
comment:8 Changed 6 years ago by
- Commit changed from 36dccd7e16e688e897514d471b0f21aa87d6e774 to 02b605094b1ce914427ffc6b02400ea3dc4ea7eb
Branch pushed to git repo; I updated commit sha1. New commits:
02b6050 | 18002: reduced word can now be forced, documentation and explaination of some algorithms
|
comment:9 Changed 6 years ago by
Hello,
the code is now freshly imported from the sage-combinat queue. I remade a lot of doctest, add some examples and documented almost every methods. All tests pass.
comment:10 Changed 6 years ago by
- Commit changed from 02b605094b1ce914427ffc6b02400ea3dc4ea7eb to 24c6da04d78f183099b8508ea8f0c5391dbb1946
Branch pushed to git repo; I updated commit sha1. New commits:
24c6da0 | Merge branch 'develop' into automaticmonoid
|
comment:11 Changed 6 years ago by
- Commit changed from 24c6da04d78f183099b8508ea8f0c5391dbb1946 to 834ea5676d8f4f9d44d36cfa8b3b13249241bba4
Branch pushed to git repo; I updated commit sha1. New commits:
834ea56 | 18002: doctest, use of representation
|
comment:12 Changed 6 years ago by
- Branch changed from u/virmaux/automaticmonoid to public/automatic-monoid/18002
- Commit changed from 834ea5676d8f4f9d44d36cfa8b3b13249241bba4 to adb6b5759d787491829bbe8064bb538ab299f4fd
- Status changed from new to needs_review
New commits:
adb6b57 | edited doc tests
|
comment:13 Changed 6 years ago by
- Commit changed from adb6b5759d787491829bbe8064bb538ab299f4fd to 193af581087bea35518e9a34b0170145d138ce25
comment:14 Changed 6 years ago by
- Commit changed from 193af581087bea35518e9a34b0170145d138ce25 to 6c0e4e1fe1142d51ba5a4400073cf8e3ba6fd8b1
Branch pushed to git repo; I updated commit sha1. New commits:
6c0e4e1 | 18002: lift for elements
|
comment:15 Changed 6 years ago by
- Commit changed from 6c0e4e1fe1142d51ba5a4400073cf8e3ba6fd8b1 to 3ab5dcf67e099d9c2526a45976a795857b9b662b
comment:16 Changed 6 years ago by
- Commit changed from 3ab5dcf67e099d9c2526a45976a795857b9b662b to 97374c2480745c1c4111ebe54561bbec4f336676
Branch pushed to git repo; I updated commit sha1. New commits:
97374c2 | new examples which breaks other tests
|
comment:17 Changed 6 years ago by
- Commit changed from 97374c2480745c1c4111ebe54561bbec4f336676 to 1ca91b1d24cac8cef2ba6450e50a029babfcec2a
comment:18 Changed 6 years ago by
- Commit changed from 1ca91b1d24cac8cef2ba6450e50a029babfcec2a to 9e8948ae645929f26f0c55b8993b20ebd6badf83
Branch pushed to git repo; I updated commit sha1. New commits:
9e8948a | broken doctest
|
comment:19 Changed 6 years ago by
- Commit changed from 9e8948ae645929f26f0c55b8993b20ebd6badf83 to e25c060fe32b0a70a5dee305ca3dab17e28c108e
Branch pushed to git repo; I updated commit sha1. New commits:
e25c060 | 18002: generators are now known at the creation of the object + few doctest
|
comment:20 Changed 6 years ago by
- Commit changed from e25c060fe32b0a70a5dee305ca3dab17e28c108e to 387fe526253408153f51bf1a9508c5553a82a734
Branch pushed to git repo; I updated commit sha1. New commits:
387fe52 | 18002: fixed unique representation of the parent (yikes+ some proofreading + copy / deepcopy
|
comment:21 Changed 6 years ago by
- Commit changed from 387fe526253408153f51bf1a9508c5553a82a734 to 4440ed0b98f53937f92c81b075a989b04b70002f
comment:22 Changed 6 years ago by
- Commit changed from 4440ed0b98f53937f92c81b075a989b04b70002f to 6a09a9a0389f868866d513c098278e2d9cce539c
Branch pushed to git repo; I updated commit sha1. New commits:
6a09a9a | 18002: type, now test pass...
|
comment:23 Changed 6 years ago by
- Commit changed from 6a09a9a0389f868866d513c098278e2d9cce539c to 64ffedce5f23f47a36249ebeae7c1e9d427f5baf
Branch pushed to git repo; I updated commit sha1. New commits:
64ffedc | Merge branch 'develop' into t/18002/public/automatic-monoid/18002
|
comment:24 Changed 6 years ago by
- Commit changed from 64ffedce5f23f47a36249ebeae7c1e9d427f5baf to bf3fc99f9935ca8c935fff8f5c26798dd610f8d2
Branch pushed to git repo; I updated commit sha1. New commits:
bf3fc99 | fixed typos and added tests
|
comment:25 Changed 6 years ago by
You should fill the Authors
field of the ticket (with the full names of each author).
comment:26 Changed 6 years ago by
- Commit changed from bf3fc99f9935ca8c935fff8f5c26798dd610f8d2 to 25df27181b699aaa90d833841a16c91c48030fc8
Branch pushed to git repo; I updated commit sha1. New commits:
25df271 | added missing doctests
|
comment:27 Changed 6 years ago by
- Reviewers set to Anne Schilling
comment:28 Changed 6 years ago by
- Commit changed from 25df27181b699aaa90d833841a16c91c48030fc8 to 02676b3fe271cf54bdd4d846d23a412bcc8fefea
Branch pushed to git repo; I updated commit sha1. New commits:
9e62d4c | 18002: first step of reworking the API to make it more foolproof + minor improvements
|
7787b05 | Merge branch 'public/automatic-monoid/18002' of trac.sagemath.org:sage into t/18002/public/automatic-monoid/18002
|
693f854 | 18002: first step toward making the iterator concurent execution safe
|
02676b3 | 18002: Make __iter__ concurent execution proof; improved repr; reworked API; better category settings (includes Subobjects)
|
comment:29 Changed 6 years ago by
- Commit changed from 02676b3fe271cf54bdd4d846d23a412bcc8fefea to 4e81ccf095ca13f1aae2ee2a33a6fd233b6deab4
Branch pushed to git repo; I updated commit sha1. New commits:
4e81ccf | 18002: automatic monoid -> automatic semigroup
|
comment:30 Changed 6 years ago by
- Commit changed from 4e81ccf095ca13f1aae2ee2a33a6fd233b6deab4 to 230a6bbb65dbe2386834060ee6214c702bee8f1b
Branch pushed to git repo; I updated commit sha1. New commits:
230a6bb | 18002: added Semigroups.ParentMethods.subsemigroup alias + removed from global name space + improved category determination + fix in construct(up_to=...)
|
comment:31 Changed 6 years ago by
- Cc days64 added
- Description modified (diff)
comment:32 Changed 6 years ago by
- Description modified (diff)
comment:33 Changed 6 years ago by
- Commit changed from 230a6bbb65dbe2386834060ee6214c702bee8f1b to d9247d445705dc393b9ff4095963c47e0f5b0625
comment:34 Changed 6 years ago by
- Status changed from needs_review to needs_info
Hello,
The commit I just made is stupid: I did not checked I correctly pulled before so it merged pretty well with the last one you made. The second one only corrects some typo in the documentation (mainly I replaced 'monoids' by 'semigroups' to be accurate with the last commits).
The method one() is provided whether the constructed object is a monoid (which is great) or is a semigroup (which is less great). Would not it be better to define this method in the constructor only if the AutomaticSemigroup
is in Monoids
?
There is no real example where the ambient semigroup is actually a semigroup (ie not a Monoid),
may we add and play with the following in the doc ?
sage: S = Semigroups().Finite().example() sage: A = AutomaticSemigroup(Family({1: S('a'), 2: S('ca'), 3: S('bc')})) sage: A in Semigroups() and A not in Monoids() True
Cheers, Aladin
comment:35 Changed 6 years ago by
- Commit changed from d9247d445705dc393b9ff4095963c47e0f5b0625 to 7c8e098e3006d91215eb1f49273d98c00d01cfd2
Branch pushed to git repo; I updated commit sha1. New commits:
7c8e098 | 18002: semigroups instead of monoids in documentation
|
comment:36 Changed 6 years ago by
- Commit changed from 7c8e098e3006d91215eb1f49273d98c00d01cfd2 to 520c74654e17838f88a2bb52e1c95ebac038ebe4
Branch pushed to git repo; I updated commit sha1. New commits:
520c746 | 18002 review of code
|
comment:37 follow-up: ↓ 38 Changed 6 years ago by
- Status changed from needs_info to needs_review
comment:38 in reply to: ↑ 37 Changed 6 years ago by
Looks good to me now! There is currently one doctest failure in /categories/semigroup.py which should be fixed once #17160 is merged. Then this can be set to positive review.
comment:39 Changed 6 years ago by
- Commit changed from 520c74654e17838f88a2bb52e1c95ebac038ebe4 to cb7168a061a64a2d6b0d0e65cecfa8ff022dba55
Branch pushed to git repo; I updated commit sha1. New commits:
cb7168a | 18002 added more tests
|
comment:40 Changed 6 years ago by
- Commit changed from cb7168a061a64a2d6b0d0e65cecfa8ff022dba55 to ff0b44ae9b5bd3c5125cfb0a728cf8591daf3da7
Branch pushed to git repo; I updated commit sha1. New commits:
ff0b44a | Merge branch 'develop' into t/18002/public/automatic-monoid/18002
|
comment:41 Changed 6 years ago by
- Commit changed from ff0b44ae9b5bd3c5125cfb0a728cf8591daf3da7 to ef045518dabb642dc7ae13d60aed0bae7d5a3b6c
comment:42 Changed 6 years ago by
- Dependencies set to #17160
comment:43 Changed 6 years ago by
- Commit changed from ef045518dabb642dc7ae13d60aed0bae7d5a3b6c to 446d012149a669b72958ed0ca4a8459164d00986
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
dabcafd | Merge branch 'develop' into t/17160/categories/finitely-generated-magmas-17160
|
cf9b429 | Fixed ReST typo
|
aff2689 | 17160: fixed category for finite set endomaps + minor __init__ refactoring
|
4b3d74c | Merge branch 'develop' into categories/finitely-generated-magmas-17160
|
ad5d6c0 | 8678: permutation groups are finitely generated, finite fields are enumerated, fixes
|
839200e | 8678: More doctest updates. Should almost pass all tests.
|
919a215 | Merge branch 'develop = sage 6.6 beta6' into categories/finitely-generated-magmas-17160
|
ef01ef0 | Merge branch 't/18012/sphinx_depends_on_jinja2' into categories/finitely-generated-magmas-17160
|
975c008 | Merge branch 'u/nthiery/categories/finitely-generated-magmas-17160' of trac.sagemath.org:sage into categories/finitely-generated-magmas-17160
|
446d012 | Merge branch 'categories/finitely-generated-magmas-17160' into automatic-monoid-18002
|
comment:44 Changed 6 years ago by
- Commit changed from 446d012149a669b72958ed0ca4a8459164d00986 to 26af5a7b17b1d35b7b4a55293f08e09fba6a691c
Branch pushed to git repo; I updated commit sha1. New commits:
6d438db | 18002: finished merge in of 17160 (doctest updates+gens) + standardized file header
|
032f87d | 18002: added Monoids.ParentMethods.submonoid shorthand
|
ea4abd6 | 18002: mention that the set of generators shall be finite in the doc of Semigroups.ParentMethods.semigroup
|
89c2cd3 | 18002: improvement to Semigroups.ParentMethods.cayley_graph: use the monoid generators instead of the semigroup generators when appropriate
|
26af5a7 | 18002: split away a second class AutomaticMonoid for a cleaner handling of the unit and the generators
|
comment:45 Changed 6 years ago by
Hi Aladin, Anne,
Following a suggestion of Aladin, and Anne's experience with using the ticket in practice, I made a few further changes (better handling of one + submonoid method). I also merged 17160 and rc2. Running the full long tests now, but the tests in the relevant category files + automatic_semigroup.py pass.
comment:46 Changed 6 years ago by
- Commit changed from 26af5a7b17b1d35b7b4a55293f08e09fba6a691c to 4167e04f6daf94519e9bf1e4be1477077b87631d
Branch pushed to git repo; I updated commit sha1. New commits:
4167e04 | 18002 small doc changes
|
comment:47 follow-up: ↓ 48 Changed 6 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
comment:48 in reply to: ↑ 47 Changed 6 years ago by
I made some small doc changes. The rest looks good to me. Thanks!
comment:49 Changed 6 years ago by
- Commit changed from 4167e04f6daf94519e9bf1e4be1477077b87631d to e66348d467e0dcde325c876c3cc713ac68606b0d
- Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
e66348d | 18002: minor pep 8
|
comment:50 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:51 Changed 6 years ago by
- Commit changed from e66348d467e0dcde325c876c3cc713ac68606b0d to 1ca4df1473ac6190d37033c430677a6cc1f291f7
- Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
1ca4df1 | 18002: added note about the name of the class
|
comment:52 Changed 6 years ago by
- Status changed from needs_review to positive_review
Thanks Anne and Aladin for the checks and fixes. I added a small note about the name of the class. It's trivial enough that I left this as positive review.
comment:53 Changed 6 years ago by
- Status changed from positive_review to needs_work
********************************************************************** File "src/doc/en/thematic_tutorials/coercion_and_categories.rst", line 463, in doc.en.thematic_tutorials.coercion_and_categories Failed example: len([s for s in dir(MS2) if inspect.ismethod(getattr(MS2,s,None))]) Expected: 83 Got: 85
comment:54 Changed 6 years ago by
- Commit changed from 1ca4df1473ac6190d37033c430677a6cc1f291f7 to a8aec14aceef2da52fd842324ff7fc4d1629daf0
Branch pushed to git repo; I updated commit sha1. New commits:
508a6a9 | Merge branch 'develop' into automatic-monoid-18002
|
dbadd6a | 15852: uncouple Sequence from categories
|
1f9c338 | Merge branch 'develop' into t/15852/15852
|
6b12bda | Merge branch 'u/rws/15852' of trac.sagemath.org:sage into public/categories/finitely_generated_magma-17160
|
19ceb81 | Merge branch 'u/nthiery/categories/finitely-generated-magmas-17160' of trac.sagemath.org:sage into public/categories/finitely_generated_magma-17160
|
a8aec14 | Merge branch 'categories/finitely-generated-magmas-17160' into automatic-monoid-18002
|
comment:55 Changed 6 years ago by
- Commit changed from a8aec14aceef2da52fd842324ff7fc4d1629daf0 to a8306e4da2265d06e6fc20ca3f16989632132fee
Branch pushed to git repo; I updated commit sha1. New commits:
a8306e4 | 18002: updated doctest in tutorial
|
comment:56 Changed 6 years ago by
- Status changed from needs_work to positive_review
Oops, sorry. Just a trivial thing. Fixed!
comment:57 Changed 6 years ago by
- Description modified (diff)
- Summary changed from AutomaticMonoid to Submonoids and subsemigroup defined by generators
comment:58 follow-up: ↓ 60 Changed 6 years ago by
The example in the description is precisely an example where we want to override the method .submonoid()
since everything can be computed using gcd
!
comment:59 Changed 6 years ago by
- Branch changed from public/automatic-monoid/18002 to a8306e4da2265d06e6fc20ca3f16989632132fee
- Resolution set to fixed
- Status changed from positive_review to closed
comment:60 in reply to: ↑ 58 ; follow-up: ↓ 61 Changed 6 years ago by
- Commit a8306e4da2265d06e6fc20ca3f16989632132fee deleted
Replying to vdelecroix:
The example in the description is precisely an example where we want to override the method
.submonoid()
since everything can be computed usinggcd
!
We are looking for a multiplicative monoid here, not additive. So I don't see from the top of my head how to do it with gcd
. I might be missing something though. And I certainly agree that there must be some better way than brute force in such a specific situation. I was just looking for a simple example where one can easily check things by hand.
comment:61 in reply to: ↑ 60 Changed 6 years ago by
Replying to nthiery:
Replying to vdelecroix:
The example in the description is precisely an example where we want to override the method
.submonoid()
since everything can be computed usinggcd
!We are looking for a multiplicative monoid here, not additive. So I don't see from the top of my head how to do it with
gcd
.
Indeed, gcd
is not enough.
And I certainly agree that there must be some better way than brute force in such a specific situation. I was just looking for a simple example where one can easily check things by hand.
In the case of Z/nZ
we know the multiplicative structure! That is indeed a great advantage. I would decompose Z/nZ = Prod_i (Z/(p_i)^k_i Z
. Then determine the order of the generators in each projection and the (multiplicative) subgroup they generate. And finally glue back.
But I am pretty sure that this was not the situation you had in mind with Aladin when you wrote this ticket ;-)
Vincent
Branch pushed to git repo; I updated commit sha1. New commits:
18002: AutomaticMonoid class