#18002 closed enhancement (fixed)
Submonoids and subsemigroup defined by generators
Reported by:  virmaux  Owned by:  

Priority:  major  Milestone:  sage6.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)  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_monoidnt.patch
from the SageCombinat 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 sagecombinat 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/automaticmonoid/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/automaticmonoid/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/automaticmonoid/18002' of trac.sagemath.org:sage into t/18002/public/automaticmonoid/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 followup: ↓ 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/automaticmonoid/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/finitelygeneratedmagmas17160

cf9b429  Fixed ReST typo

aff2689  17160: fixed category for finite set endomaps + minor __init__ refactoring

4b3d74c  Merge branch 'develop' into categories/finitelygeneratedmagmas17160

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/finitelygeneratedmagmas17160

ef01ef0  Merge branch 't/18012/sphinx_depends_on_jinja2' into categories/finitelygeneratedmagmas17160

975c008  Merge branch 'u/nthiery/categories/finitelygeneratedmagmas17160' of trac.sagemath.org:sage into categories/finitelygeneratedmagmas17160

446d012  Merge branch 'categories/finitelygeneratedmagmas17160' into automaticmonoid18002

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 followup: ↓ 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 automaticmonoid18002

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_magma17160

19ceb81  Merge branch 'u/nthiery/categories/finitelygeneratedmagmas17160' of trac.sagemath.org:sage into public/categories/finitely_generated_magma17160

a8aec14  Merge branch 'categories/finitelygeneratedmagmas17160' into automaticmonoid18002

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 followup: ↓ 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/automaticmonoid/18002 to a8306e4da2265d06e6fc20ca3f16989632132fee
 Resolution set to fixed
 Status changed from positive_review to closed
comment:60 in reply to: ↑ 58 ; followup: ↓ 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