Submonoids and subsemigroup defined by generators

[virmaux]

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.

[git]

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

​bd807f4

18002: AutomaticMonoid class

[git]

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

​da7db1d

documentation and tests

[git]

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

​36dccd7

18002: I do not understand a function

[git]

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

[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.

[git]

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

​24c6da0

Merge branch 'develop' into automaticmonoid

[git]

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

​834ea56

18002: doctest, use of representation

[aschilling]

New commits:

​adb6b57

edited doc tests

[git]

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

​459bb91	trivial doctest
​193af58	Merge branch 'automaticmonoid' into t/18002/public/automatic-monoid/18002

[git]

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

​6c0e4e1

18002: lift for elements

[git]

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

​4f57640	fixed sorted doc test failure
​3ab5dcf	Merge branch 'public/automatic-monoid/18002' of git://trac.sagemath.org/sage into u/virmaux/automaticmonoid

[git]

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

​97374c2

new examples which breaks other tests

[git]

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

​7dd863d	doctest
​1ca91b1	merge conflict

[git]

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

​9e8948a

broken doctest

[git]

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

[git]

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

​387fe52

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

[git]

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

​91f4623	18002: a few doctest
​12e7a46	Merge branch 'public/automatic-monoid/18002' of git://trac.sagemath.org/sage into t/18002/public/automatic-monoid/18002
​4440ed0	18002: iterative methods, doctest

[git]

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

​6a09a9a

18002: type, now test pass...

[git]

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

​64ffedc

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

[git]

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

​bf3fc99

fixed typos and added tests

[vdelecroix]

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

[git]

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

​25df271

added missing doctests

[git]

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)

[git]

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

​4e81ccf

18002: automatic monoid -> automatic semigroup

[git]

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=...)

[git]

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

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

[virmaux]

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

[git]

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

​7c8e098

18002: semigroups instead of monoids in documentation

[git]

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

​520c746

18002 review of code

[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.

[git]

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

​cb7168a

18002 added more tests

[git]

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

​ff0b44a

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

[git]

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

​4a7c5a1	Merge branch 'develop' into automatic-monoid-18002
​ef04551	Merge branch 'public/automatic-monoid/18002' of trac.sagemath.org:sage into automatic-monoid-18002

[git]

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

[git]

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

[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.

[git]

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

​4167e04

18002 small doc changes

[aschilling]

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

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​e66348d

18002: minor pep 8

[git]

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

[nthiery]

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.

[vbraun]

**********************************************************************
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

[git]

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

[git]

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

​a8306e4

18002: updated doctest in tutorial

[nthiery]

Oops, sorry. Just a trivial thing. Fixed!

[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!

[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. 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.

[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