Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#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) Commit:
Dependencies: #17160 Stopgaps:

Description (last modified by nthiery)

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 5 years ago by virmaux

  • Branch set to u/virmaux/automaticmonoid

comment:2 Changed 5 years ago by virmaux

  • Branch u/virmaux/automaticmonoid deleted
  • Type changed from PLEASE CHANGE to enhancement

comment:3 Changed 5 years ago by virmaux

  • Branch set to u/virmaux/automaticmonoid

comment:4 Changed 5 years ago by git

  • Commit set to bd807f4ccea8565feb8e2984476ee7cb4f18b404

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

bd807f418002: AutomaticMonoid class

comment:5 Changed 5 years ago by virmaux

  • Description modified (diff)

comment:6 Changed 5 years ago by git

  • Commit changed from bd807f4ccea8565feb8e2984476ee7cb4f18b404 to da7db1d95e91c50fd4d91958561e676ac828dc4d

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

da7db1ddocumentation and tests

comment:7 Changed 5 years ago by git

  • Commit changed from da7db1d95e91c50fd4d91958561e676ac828dc4d to 36dccd7e16e688e897514d471b0f21aa87d6e774

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

36dccd718002: I do not understand a function

comment:8 Changed 5 years ago by git

  • Commit changed from 36dccd7e16e688e897514d471b0f21aa87d6e774 to 02b605094b1ce914427ffc6b02400ea3dc4ea7eb

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

02b605018002: reduced word can now be forced, documentation and explaination of some algorithms

comment:9 Changed 5 years ago by virmaux

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 5 years ago by git

  • Commit changed from 02b605094b1ce914427ffc6b02400ea3dc4ea7eb to 24c6da04d78f183099b8508ea8f0c5391dbb1946

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

24c6da0Merge branch 'develop' into automaticmonoid

comment:11 Changed 5 years ago by git

  • Commit changed from 24c6da04d78f183099b8508ea8f0c5391dbb1946 to 834ea5676d8f4f9d44d36cfa8b3b13249241bba4

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

834ea5618002: doctest, use of representation

comment:12 Changed 5 years ago by aschilling

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

adb6b57edited doc tests

comment:13 Changed 5 years ago by git

  • Commit changed from adb6b5759d787491829bbe8064bb538ab299f4fd to 193af581087bea35518e9a34b0170145d138ce25

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

459bb91trivial doctest
193af58Merge branch 'automaticmonoid' into t/18002/public/automatic-monoid/18002

comment:14 Changed 5 years ago by git

  • Commit changed from 193af581087bea35518e9a34b0170145d138ce25 to 6c0e4e1fe1142d51ba5a4400073cf8e3ba6fd8b1

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

6c0e4e118002: lift for elements

comment:15 Changed 5 years ago by git

  • Commit changed from 6c0e4e1fe1142d51ba5a4400073cf8e3ba6fd8b1 to 3ab5dcf67e099d9c2526a45976a795857b9b662b

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

4f57640fixed sorted doc test failure
3ab5dcfMerge branch 'public/automatic-monoid/18002' of git://trac.sagemath.org/sage into u/virmaux/automaticmonoid

comment:16 Changed 5 years ago by git

  • Commit changed from 3ab5dcf67e099d9c2526a45976a795857b9b662b to 97374c2480745c1c4111ebe54561bbec4f336676

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

97374c2new examples which breaks other tests

comment:17 Changed 5 years ago by git

  • Commit changed from 97374c2480745c1c4111ebe54561bbec4f336676 to 1ca91b1d24cac8cef2ba6450e50a029babfcec2a

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

7dd863ddoctest
1ca91b1merge conflict

comment:18 Changed 5 years ago by git

  • Commit changed from 1ca91b1d24cac8cef2ba6450e50a029babfcec2a to 9e8948ae645929f26f0c55b8993b20ebd6badf83

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

9e8948abroken doctest

comment:19 Changed 5 years ago by git

  • Commit changed from 9e8948ae645929f26f0c55b8993b20ebd6badf83 to e25c060fe32b0a70a5dee305ca3dab17e28c108e

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

e25c06018002: generators are now known at the creation of the object + few doctest

comment:20 Changed 5 years ago by git

  • Commit changed from e25c060fe32b0a70a5dee305ca3dab17e28c108e to 387fe526253408153f51bf1a9508c5553a82a734

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

387fe5218002: fixed unique representation of the parent (yikes+ some proofreading + copy / deepcopy

comment:21 Changed 5 years ago by git

  • Commit changed from 387fe526253408153f51bf1a9508c5553a82a734 to 4440ed0b98f53937f92c81b075a989b04b70002f

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

91f462318002: a few doctest
12e7a46Merge branch 'public/automatic-monoid/18002' of git://trac.sagemath.org/sage into t/18002/public/automatic-monoid/18002
4440ed018002: iterative methods, doctest

comment:22 Changed 5 years ago by git

  • Commit changed from 4440ed0b98f53937f92c81b075a989b04b70002f to 6a09a9a0389f868866d513c098278e2d9cce539c

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

6a09a9a18002: type, now test pass...

comment:23 Changed 5 years ago by git

  • Commit changed from 6a09a9a0389f868866d513c098278e2d9cce539c to 64ffedce5f23f47a36249ebeae7c1e9d427f5baf

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

64ffedcMerge branch 'develop' into t/18002/public/automatic-monoid/18002

comment:24 Changed 5 years ago by git

  • Commit changed from 64ffedce5f23f47a36249ebeae7c1e9d427f5baf to bf3fc99f9935ca8c935fff8f5c26798dd610f8d2

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

bf3fc99fixed typos and added tests

comment:25 Changed 5 years ago by vdelecroix

You should fill the Authors field of the ticket (with the full names of each author).

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:26 Changed 5 years ago by git

  • Commit changed from bf3fc99f9935ca8c935fff8f5c26798dd610f8d2 to 25df27181b699aaa90d833841a16c91c48030fc8

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

25df271added missing doctests

comment:27 Changed 5 years ago by aschilling

  • Authors set to Nicolas M. Thiery, Aladin Virmaux
  • Reviewers set to Anne Schilling

comment:28 Changed 5 years ago by git

  • Commit changed from 25df27181b699aaa90d833841a16c91c48030fc8 to 02676b3fe271cf54bdd4d846d23a412bcc8fefea

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

9e62d4c18002: first step of reworking the API to make it more foolproof + minor improvements
7787b05Merge branch 'public/automatic-monoid/18002' of trac.sagemath.org:sage into t/18002/public/automatic-monoid/18002
693f85418002: first step toward making the iterator concurent execution safe
02676b318002: Make __iter__ concurent execution proof; improved repr; reworked API; better category settings (includes Subobjects)

comment:29 Changed 5 years ago by git

  • Commit changed from 02676b3fe271cf54bdd4d846d23a412bcc8fefea to 4e81ccf095ca13f1aae2ee2a33a6fd233b6deab4

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

4e81ccf18002: automatic monoid -> automatic semigroup

comment:30 Changed 5 years ago by git

  • Commit changed from 4e81ccf095ca13f1aae2ee2a33a6fd233b6deab4 to 230a6bbb65dbe2386834060ee6214c702bee8f1b

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

230a6bb18002: added Semigroups.ParentMethods.subsemigroup alias + removed from global name space + improved category determination + fix in construct(up_to=...)

comment:31 Changed 5 years ago by nthiery

  • Authors changed from Nicolas M. Thiery, Aladin Virmaux to Nicolas M. Thiéry, Aladin Virmaux
  • Cc days64 added
  • Description modified (diff)

comment:32 Changed 5 years ago by nthiery

  • Description modified (diff)

comment:33 Changed 5 years ago by git

  • Commit changed from 230a6bbb65dbe2386834060ee6214c702bee8f1b to d9247d445705dc393b9ff4095963c47e0f5b0625

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

fd1e65118002: import fixed, doctest fixed, few pep8
d9247d4Merge branch 'public/automatic-monoid/18002' of git://trac.sagemath.org/sage into t/18002/public/automatic-monoid/18002

comment:34 Changed 5 years ago by virmaux

  • 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 5 years ago by git

  • Commit changed from d9247d445705dc393b9ff4095963c47e0f5b0625 to 7c8e098e3006d91215eb1f49273d98c00d01cfd2

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

7c8e09818002: semigroups instead of monoids in documentation

comment:36 Changed 5 years ago by git

  • Commit changed from 7c8e098e3006d91215eb1f49273d98c00d01cfd2 to 520c74654e17838f88a2bb52e1c95ebac038ebe4

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

520c74618002 review of code

comment:37 follow-up: Changed 5 years ago by aschilling

  • Status changed from needs_info to needs_review

comment:38 in reply to: ↑ 37 Changed 5 years ago by aschilling

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 5 years ago by git

  • Commit changed from 520c74654e17838f88a2bb52e1c95ebac038ebe4 to cb7168a061a64a2d6b0d0e65cecfa8ff022dba55

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

cb7168a18002 added more tests

comment:40 Changed 5 years ago by git

  • Commit changed from cb7168a061a64a2d6b0d0e65cecfa8ff022dba55 to ff0b44ae9b5bd3c5125cfb0a728cf8591daf3da7

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

ff0b44aMerge branch 'develop' into t/18002/public/automatic-monoid/18002

comment:41 Changed 5 years ago by git

  • Commit changed from ff0b44ae9b5bd3c5125cfb0a728cf8591daf3da7 to ef045518dabb642dc7ae13d60aed0bae7d5a3b6c

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

4a7c5a1Merge branch 'develop' into automatic-monoid-18002
ef04551Merge branch 'public/automatic-monoid/18002' of trac.sagemath.org:sage into automatic-monoid-18002

comment:42 Changed 5 years ago by nthiery

  • Dependencies set to #17160

comment:43 Changed 5 years ago by git

  • Commit changed from ef045518dabb642dc7ae13d60aed0bae7d5a3b6c to 446d012149a669b72958ed0ca4a8459164d00986

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

dabcafdMerge branch 'develop' into t/17160/categories/finitely-generated-magmas-17160
cf9b429Fixed ReST typo
aff268917160: fixed category for finite set endomaps + minor __init__ refactoring
4b3d74cMerge branch 'develop' into categories/finitely-generated-magmas-17160
ad5d6c08678: permutation groups are finitely generated, finite fields are enumerated, fixes
839200e8678: More doctest updates. Should almost pass all tests.
919a215Merge branch 'develop = sage 6.6 beta6' into categories/finitely-generated-magmas-17160
ef01ef0Merge branch 't/18012/sphinx_depends_on_jinja2' into categories/finitely-generated-magmas-17160
975c008Merge branch 'u/nthiery/categories/finitely-generated-magmas-17160' of trac.sagemath.org:sage into categories/finitely-generated-magmas-17160
446d012Merge branch 'categories/finitely-generated-magmas-17160' into automatic-monoid-18002

comment:44 Changed 5 years ago by git

  • Commit changed from 446d012149a669b72958ed0ca4a8459164d00986 to 26af5a7b17b1d35b7b4a55293f08e09fba6a691c

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

6d438db18002: finished merge in of 17160 (doctest updates+gens) + standardized file header
032f87d18002: added Monoids.ParentMethods.submonoid shorthand
ea4abd618002: mention that the set of generators shall be finite in the doc of Semigroups.ParentMethods.semigroup
89c2cd318002: improvement to Semigroups.ParentMethods.cayley_graph: use the monoid generators instead of the semigroup generators when appropriate
26af5a718002: split away a second class AutomaticMonoid for a cleaner handling of the unit and the generators

comment:45 Changed 5 years ago by nthiery

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 5 years ago by git

  • Commit changed from 26af5a7b17b1d35b7b4a55293f08e09fba6a691c to 4167e04f6daf94519e9bf1e4be1477077b87631d

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

4167e0418002 small doc changes

comment:47 follow-up: Changed 5 years ago by aschilling

  • Description modified (diff)
  • Status changed from needs_review to positive_review

comment:48 in reply to: ↑ 47 Changed 5 years ago by aschilling

I made some small doc changes. The rest looks good to me. Thanks!

comment:49 Changed 5 years ago by git

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

e66348d18002: minor pep 8

comment:50 Changed 5 years ago by virmaux

  • Status changed from needs_review to positive_review

comment:51 Changed 5 years ago by git

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

1ca4df118002: added note about the name of the class

comment:52 Changed 5 years ago by nthiery

  • 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 5 years ago by vbraun

  • 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 5 years ago by git

  • Commit changed from 1ca4df1473ac6190d37033c430677a6cc1f291f7 to a8aec14aceef2da52fd842324ff7fc4d1629daf0

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

508a6a9Merge branch 'develop' into automatic-monoid-18002
dbadd6a15852: uncouple Sequence from categories
1f9c338Merge branch 'develop' into t/15852/15852
6b12bdaMerge branch 'u/rws/15852' of trac.sagemath.org:sage into public/categories/finitely_generated_magma-17160
19ceb81Merge branch 'u/nthiery/categories/finitely-generated-magmas-17160' of trac.sagemath.org:sage into public/categories/finitely_generated_magma-17160
a8aec14Merge branch 'categories/finitely-generated-magmas-17160' into automatic-monoid-18002

comment:55 Changed 5 years ago by git

  • Commit changed from a8aec14aceef2da52fd842324ff7fc4d1629daf0 to a8306e4da2265d06e6fc20ca3f16989632132fee

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

a8306e418002: updated doctest in tutorial

comment:56 Changed 5 years ago by nthiery

  • Status changed from needs_work to positive_review

Oops, sorry. Just a trivial thing. Fixed!

comment:57 Changed 5 years ago by nthiery

  • Description modified (diff)
  • Summary changed from AutomaticMonoid to Submonoids and subsemigroup defined by generators

comment:58 follow-up: Changed 5 years ago by vdelecroix

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 5 years ago by vbraun

  • 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: Changed 5 years ago by nthiery

  • 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 using gcd!

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 5 years ago by vdelecroix

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 using gcd!

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

Note: See TracTickets for help on using tickets.