Automatic Semigroups#

Semigroups defined by generators living in an ambient semigroup and represented by an automaton.

AUTHORS:

  • Nicolas M. Thiéry

  • Aladin Virmaux

class sage.monoids.automatic_semigroup.AutomaticMonoid(generators, ambient, one, mul, category)[source]#

Bases: AutomaticSemigroup

gens()[source]#

Return the family of monoid generators of self.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(28)
sage: M = R.submonoid(Family({1: R(3), 2: R(5)}))
sage: M.monoid_generators()
Finite family {1: 3, 2: 5}

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(28))
>>> M = R.submonoid(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}))
>>> M.monoid_generators()
Finite family {1: 3, 2: 5}

Note that the monoid generators do not include the unit, unlike the semigroup generators:

sage: M.semigroup_generators()
Family (1, 3, 5)

>>> from sage.all import *
>>> M.semigroup_generators()
Family (1, 3, 5)
monoid_generators()[source]#

Return the family of monoid generators of self.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(28)
sage: M = R.submonoid(Family({1: R(3), 2: R(5)}))
sage: M.monoid_generators()
Finite family {1: 3, 2: 5}

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(28))
>>> M = R.submonoid(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}))
>>> M.monoid_generators()
Finite family {1: 3, 2: 5}

Note that the monoid generators do not include the unit, unlike the semigroup generators:

sage: M.semigroup_generators()
Family (1, 3, 5)

>>> from sage.all import *
>>> M.semigroup_generators()
Family (1, 3, 5)
one()[source]#

Return the unit of self.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(21)
sage: M = R.submonoid(())
sage: M.one()
1
sage: M.one().parent() is M
True

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(21))
>>> M = R.submonoid(())
>>> M.one()
1
>>> M.one().parent() is M
True
semigroup_generators()[source]#

Return the generators of self as a semigroup.

The generators of a monoid \(M\) as a semigroup are the generators of \(M\) as a monoid and the unit.

EXAMPLES:

sage: M = Monoids().free([1,2,3])                                       # needs sage.combinat
sage: M.semigroup_generators()                                          # needs sage.combinat
Family (1, F[1], F[2], F[3])

>>> from sage.all import *
>>> M = Monoids().free([Integer(1),Integer(2),Integer(3)])                                       # needs sage.combinat
>>> M.semigroup_generators()                                          # needs sage.combinat
Family (1, F[1], F[2], F[3])
class sage.monoids.automatic_semigroup.AutomaticSemigroup(generators, ambient, one, mul, category)[source]#

Bases: UniqueRepresentation, Parent

Semigroups defined by generators living in an ambient semigroup.

This implementation lazily constructs all the elements of the semigroup, and the right Cayley graph relations between them, and uses the latter as an automaton.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(12)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: M in Monoids()
True
sage: M.one()
1
sage: M.one() in M
True
sage: g = M._generators; g
Finite family {1: 3, 2: 5}
sage: g[1]*g[2]
3
sage: M.some_elements()
[1, 3, 5, 9]

sage: M.list()
[1, 3, 5, 9]

sage: M.idempotents()
[1, 9]

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(12))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> M in Monoids()
True
>>> M.one()
1
>>> M.one() in M
True
>>> g = M._generators; g
Finite family {1: 3, 2: 5}
>>> g[Integer(1)]*g[Integer(2)]
3
>>> M.some_elements()
[1, 3, 5, 9]

>>> M.list()
[1, 3, 5, 9]

>>> M.idempotents()
[1, 9]

As can be seen above, elements are represented by default the corresponding element in the ambient monoid. One can also represent the elements by their reduced word:

sage: M.repr_element_method("reduced_word")
sage: M.list()
[[], [1], [2], [1, 1]]

>>> from sage.all import *
>>> M.repr_element_method("reduced_word")
>>> M.list()
[[], [1], [2], [1, 1]]

In case the reduced word has not yet been calculated, the element will be represented by the corresponding element in the ambient monoid:

sage: R = IntegerModRing(13)
sage: N = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: N.repr_element_method("reduced_word")
sage: n = N.an_element()
sage: n
[1]
sage: n*n
9

>>> from sage.all import *
>>> R = IntegerModRing(Integer(13))
>>> N = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> N.repr_element_method("reduced_word")
>>> n = N.an_element()
>>> n
[1]
>>> n*n
9

Calling construct(), cardinality(), or list(), or iterating through the monoid will trigger its full construction and, as a side effect, compute all the reduced words. The order of the elements, and the induced choice of reduced word is currently length-lexicographic (i.e. the chosen reduced word is of minimal length, and then minimal lexicographically w.r.t. the order of the indices of the generators):

sage: M.cardinality()
4
sage: M.list()
[[], [1], [2], [1, 1]]
sage: g = M._generators

sage: g[1]*g[2]
[1]

sage: g[1].transition(1)
[1, 1]
sage: g[1] * g[1]
[1, 1]
sage: g[1] * g[1] * g[1]
[1]
sage: g[1].transition(2)
[1]
sage: g[1] * g[2]
[1]

sage: [ x.lift() for x in M.list() ]
[1, 3, 5, 9]

sage: # needs sage.graphs
sage: G = M.cayley_graph(side="twosided"); G
Looped multi-digraph on 4 vertices
sage: G.edges(sort=True, key=str)
[([1, 1], [1, 1], (2, 'left')),
 ([1, 1], [1, 1], (2, 'right')),
 ([1, 1], [1], (1, 'left')),
 ([1, 1], [1], (1, 'right')),
 ([1], [1, 1], (1, 'left')),
 ([1], [1, 1], (1, 'right')),
 ([1], [1], (2, 'left')),
 ([1], [1], (2, 'right')),
 ([2], [1], (1, 'left')),
 ([2], [1], (1, 'right')),
 ([2], [], (2, 'left')),
 ([2], [], (2, 'right')),
 ([], [1], (1, 'left')),
 ([], [1], (1, 'right')),
 ([], [2], (2, 'left')),
 ([], [2], (2, 'right'))]
sage: list(map(sorted, M.j_classes()))
[[[1], [1, 1]], [[], [2]]]
sage: M.j_classes_of_idempotents()
[[[1, 1]], [[]]]
sage: M.j_transversal_of_idempotents()
[[1, 1], []]

sage: list(map(attrcall('pseudo_order'), M.list()))                             # needs sage.graphs
[[1, 0], [3, 1], [2, 0], [2, 1]]

>>> from sage.all import *
>>> M.cardinality()
4
>>> M.list()
[[], [1], [2], [1, 1]]
>>> g = M._generators

>>> g[Integer(1)]*g[Integer(2)]
[1]

>>> g[Integer(1)].transition(Integer(1))
[1, 1]
>>> g[Integer(1)] * g[Integer(1)]
[1, 1]
>>> g[Integer(1)] * g[Integer(1)] * g[Integer(1)]
[1]
>>> g[Integer(1)].transition(Integer(2))
[1]
>>> g[Integer(1)] * g[Integer(2)]
[1]

>>> [ x.lift() for x in M.list() ]
[1, 3, 5, 9]

>>> # needs sage.graphs
>>> G = M.cayley_graph(side="twosided"); G
Looped multi-digraph on 4 vertices
>>> G.edges(sort=True, key=str)
[([1, 1], [1, 1], (2, 'left')),
 ([1, 1], [1, 1], (2, 'right')),
 ([1, 1], [1], (1, 'left')),
 ([1, 1], [1], (1, 'right')),
 ([1], [1, 1], (1, 'left')),
 ([1], [1, 1], (1, 'right')),
 ([1], [1], (2, 'left')),
 ([1], [1], (2, 'right')),
 ([2], [1], (1, 'left')),
 ([2], [1], (1, 'right')),
 ([2], [], (2, 'left')),
 ([2], [], (2, 'right')),
 ([], [1], (1, 'left')),
 ([], [1], (1, 'right')),
 ([], [2], (2, 'left')),
 ([], [2], (2, 'right'))]
>>> list(map(sorted, M.j_classes()))
[[[1], [1, 1]], [[], [2]]]
>>> M.j_classes_of_idempotents()
[[[1, 1]], [[]]]
>>> M.j_transversal_of_idempotents()
[[1, 1], []]

>>> list(map(attrcall('pseudo_order'), M.list()))                             # needs sage.graphs
[[1, 0], [3, 1], [2, 0], [2, 1]]

We can also use it to get submonoids from groups. We check that in the symmetric group, a transposition and a long cycle generate the whole group:

sage: # needs sage.groups
sage: G5 = SymmetricGroup(5)
sage: N = AutomaticSemigroup(Family({1: G5([2,1,3,4,5]), 2: G5([2,3,4,5,1])}),
....:                        one=G5.one())
sage: N.repr_element_method("reduced_word")
sage: N.cardinality() == G5.cardinality()
True
sage: N.retract(G5((1,4,3,5,2)))
[1, 2, 1, 2, 2, 1, 2, 1, 2, 2]
sage: N.from_reduced_word([1, 2, 1, 2, 2, 1, 2, 1, 2, 2]).lift()
(1,4,3,5,2)

>>> from sage.all import *
>>> # needs sage.groups
>>> G5 = SymmetricGroup(Integer(5))
>>> N = AutomaticSemigroup(Family({Integer(1): G5([Integer(2),Integer(1),Integer(3),Integer(4),Integer(5)]), Integer(2): G5([Integer(2),Integer(3),Integer(4),Integer(5),Integer(1)])}),
...                        one=G5.one())
>>> N.repr_element_method("reduced_word")
>>> N.cardinality() == G5.cardinality()
True
>>> N.retract(G5((Integer(1),Integer(4),Integer(3),Integer(5),Integer(2))))
[1, 2, 1, 2, 2, 1, 2, 1, 2, 2]
>>> N.from_reduced_word([Integer(1), Integer(2), Integer(1), Integer(2), Integer(2), Integer(1), Integer(2), Integer(1), Integer(2), Integer(2)]).lift()
(1,4,3,5,2)

We can also create a semigroup of matrices, where we define the multiplication as matrix multiplication:

sage: # needs sage.modules
sage: M1 = matrix([[0,0,1],[1,0,0],[0,1,0]])
sage: M2 = matrix([[0,0,0],[1,1,0],[0,0,1]])
sage: M1.set_immutable()
sage: M2.set_immutable()
sage: def prod_m(x,y):
....:     z=x*y
....:     z.set_immutable()
....:     return z
sage: Mon = AutomaticSemigroup([M1,M2], mul=prod_m,
....:                          category=Monoids().Finite().Subobjects())
sage: Mon.cardinality()
24
sage: C = Mon.cayley_graph()                                                    # needs sage.graphs
sage: C.is_directed_acyclic()                                                   # needs sage.graphs
False

>>> from sage.all import *
>>> # needs sage.modules
>>> M1 = matrix([[Integer(0),Integer(0),Integer(1)],[Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0)]])
>>> M2 = matrix([[Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)]])
>>> M1.set_immutable()
>>> M2.set_immutable()
>>> def prod_m(x,y):
...     z=x*y
...     z.set_immutable()
...     return z
>>> Mon = AutomaticSemigroup([M1,M2], mul=prod_m,
...                          category=Monoids().Finite().Subobjects())
>>> Mon.cardinality()
24
>>> C = Mon.cayley_graph()                                                    # needs sage.graphs
>>> C.is_directed_acyclic()                                                   # needs sage.graphs
False

Let us construct and play with the 0-Hecke Monoid:

sage: # needs sage.graphs sage.modules
sage: W = WeylGroup(['A',4]); W.rename("W")
sage: ambient_monoid = FiniteSetMaps(W, action="right")
sage: pi = W.simple_projections(length_increasing=True).map(ambient_monoid)
sage: M = AutomaticSemigroup(pi, one=ambient_monoid.one()); M
A submonoid of (Maps from W to itself) with 4 generators
sage: M.repr_element_method("reduced_word")
sage: sorted(M._elements_set, key=str)
[[1], [2], [3], [4], []]
sage: M.construct(n=10)
sage: sorted(M._elements_set, key=str)
[[1, 2], [1, 3], [1, 4], [1], [2, 1], [2, 3], [2], [3], [4], []]
sage: elt = M.from_reduced_word([3,1,2,4,2])
sage: M.construct(up_to=elt)
sage: len(M._elements_set)
36
sage: M.cardinality()
120

>>> from sage.all import *
>>> # needs sage.graphs sage.modules
>>> W = WeylGroup(['A',Integer(4)]); W.rename("W")
>>> ambient_monoid = FiniteSetMaps(W, action="right")
>>> pi = W.simple_projections(length_increasing=True).map(ambient_monoid)
>>> M = AutomaticSemigroup(pi, one=ambient_monoid.one()); M
A submonoid of (Maps from W to itself) with 4 generators
>>> M.repr_element_method("reduced_word")
>>> sorted(M._elements_set, key=str)
[[1], [2], [3], [4], []]
>>> M.construct(n=Integer(10))
>>> sorted(M._elements_set, key=str)
[[1, 2], [1, 3], [1, 4], [1], [2, 1], [2, 3], [2], [3], [4], []]
>>> elt = M.from_reduced_word([Integer(3),Integer(1),Integer(2),Integer(4),Integer(2)])
>>> M.construct(up_to=elt)
>>> len(M._elements_set)
36
>>> M.cardinality()
120

We check that the 0-Hecke monoid is \(J\)-trivial and contains \(2^4\) idempotents:

sage: len(M.idempotents())                                                      # needs sage.graphs sage.modules
16
sage: all(len(j) == 1 for j in M.j_classes())                                   # needs sage.graphs sage.modules
True

>>> from sage.all import *
>>> len(M.idempotents())                                                      # needs sage.graphs sage.modules
16
>>> all(len(j) == Integer(1) for j in M.j_classes())                                   # needs sage.graphs sage.modules
True

Note

Unlike what the name of the class may suggest, this currently implements only a subclass of automatic semigroups; essentially the finite ones. See Wikipedia article Automatic_semigroup.

Warning

AutomaticSemigroup is designed primarily for finite semigroups. This property is not checked automatically (this would be too costly, if not undecidable). Use with care for an infinite semigroup, as certain features may require constructing all of it:

sage: M = AutomaticSemigroup([2], category = Monoids().Subobjects()); M
A submonoid of (Integer Ring) with 1 generators
sage: M.retract(2)
2
sage: M.retract(3)   # not tested: runs forever trying to find 3

>>> from sage.all import *
>>> M = AutomaticSemigroup([Integer(2)], category = Monoids().Subobjects()); M
A submonoid of (Integer Ring) with 1 generators
>>> M.retract(Integer(2))
2
>>> M.retract(Integer(3))   # not tested: runs forever trying to find 3
class Element(ambient_element, parent)[source]#

Bases: ElementWrapper

lift()[source]#

Lift the element self into its ambient semigroup.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(18)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}))
sage: M.repr_element_method("reduced_word")
sage: m = M.an_element(); m
[1]
sage: type(m)
<class 'sage.monoids.automatic_semigroup.AutomaticSemigroup_with_category.element_class'>
sage: m.lift()
3
sage: type(m.lift())
<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(18))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}))
>>> M.repr_element_method("reduced_word")
>>> m = M.an_element(); m
[1]
>>> type(m)
<class 'sage.monoids.automatic_semigroup.AutomaticSemigroup_with_category.element_class'>
>>> m.lift()
3
>>> type(m.lift())
<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
reduced_word()[source]#

Return the length-lexicographic shortest word of self.

OUTPUT: a list of indexes of the generators

Obtaining the reduced word requires having constructed the Cayley graph of the semigroup up to self. If this is not the case, an error is raised.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(15)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: M.construct()
sage: for m in M: print((m, m.reduced_word()))
(1, [])
(3, [1])
(5, [2])
(9, [1, 1])
(0, [1, 2])
(10, [2, 2])
(12, [1, 1, 1])
(6, [1, 1, 1, 1])

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(15))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> M.construct()
>>> for m in M: print((m, m.reduced_word()))
(1, [])
(3, [1])
(5, [2])
(9, [1, 1])
(0, [1, 2])
(10, [2, 2])
(12, [1, 1, 1])
(6, [1, 1, 1, 1])
transition(i)[source]#

The multiplication on the right by a generator.

INPUT:

  • i – an element from the indexing set of the generators

This method computes self * self._generators[i].

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(17)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: M.repr_element_method("reduced_word")
sage: M.construct()
sage: a = M.an_element()
sage: a.transition(1)
[1, 1]
sage: a.transition(2)
[1, 2]

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(17))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> M.repr_element_method("reduced_word")
>>> M.construct()
>>> a = M.an_element()
>>> a.transition(Integer(1))
[1, 1]
>>> a.transition(Integer(2))
[1, 2]
ambient()[source]#

Return the ambient semigroup of self.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(12)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: M.ambient()
Ring of integers modulo 12

sage: # needs sage.modules
sage: M1 = matrix([[0,0,1],[1,0,0],[0,1,0]])
sage: M2 = matrix([[0,0,0],[1,1,0],[0,0,1]])
sage: M1.set_immutable()
sage: M2.set_immutable()
sage: def prod_m(x,y):
....:     z=x*y
....:     z.set_immutable()
....:     return z
sage: Mon = AutomaticSemigroup([M1,M2], mul=prod_m)
sage: Mon.ambient()
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(12))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> M.ambient()
Ring of integers modulo 12

>>> # needs sage.modules
>>> M1 = matrix([[Integer(0),Integer(0),Integer(1)],[Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0)]])
>>> M2 = matrix([[Integer(0),Integer(0),Integer(0)],[Integer(1),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)]])
>>> M1.set_immutable()
>>> M2.set_immutable()
>>> def prod_m(x,y):
...     z=x*y
...     z.set_immutable()
...     return z
>>> Mon = AutomaticSemigroup([M1,M2], mul=prod_m)
>>> Mon.ambient()
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring
an_element()[source]#

Return the first given generator of self.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(16)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: M.an_element()
3

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(16))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> M.an_element()
3
cardinality()[source]#

Return the cardinality of self.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(12)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: M.cardinality()
4

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(12))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> M.cardinality()
4
construct(up_to=None, n=None)[source]#

Construct the elements of self.

INPUT:

  • up_to – an element of self or of the ambient semigroup.

  • n – an integer or None (default: None)

This construct all the elements of this semigroup, their reduced words, and the right Cayley graph. If \(n\) is specified, only the \(n\) first elements of the semigroup are constructed. If element is specified, only the elements up to ambient_element are constructed.

EXAMPLES:

sage: # needs sage.groups sage.modules
sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: W = WeylGroup(['A',3]); W.rename("W")
sage: ambient_monoid = FiniteSetMaps(W, action="right")
sage: pi = W.simple_projections(length_increasing=True).map(ambient_monoid)
sage: M = AutomaticSemigroup(pi, one=ambient_monoid.one()); M
A submonoid of (Maps from W to itself) with 3 generators
sage: M.repr_element_method("reduced_word")
sage: sorted(M._elements_set, key=str)
[[1], [2], [3], []]
sage: elt = M.from_reduced_word([2,3,1,2])
sage: M.construct(up_to=elt)
sage: len(M._elements_set)
19
sage: M.cardinality()
24

>>> from sage.all import *
>>> # needs sage.groups sage.modules
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> W = WeylGroup(['A',Integer(3)]); W.rename("W")
>>> ambient_monoid = FiniteSetMaps(W, action="right")
>>> pi = W.simple_projections(length_increasing=True).map(ambient_monoid)
>>> M = AutomaticSemigroup(pi, one=ambient_monoid.one()); M
A submonoid of (Maps from W to itself) with 3 generators
>>> M.repr_element_method("reduced_word")
>>> sorted(M._elements_set, key=str)
[[1], [2], [3], []]
>>> elt = M.from_reduced_word([Integer(2),Integer(3),Integer(1),Integer(2)])
>>> M.construct(up_to=elt)
>>> len(M._elements_set)
19
>>> M.cardinality()
24
from_reduced_word(l)[source]#

Return the element of self obtained from the reduced word l.

INPUT:

  • l – a list of indices of the generators

Note

We do not save the given reduced word l as an attribute of the element, as some elements above in the branches may have not been explored by the iterator yet.

EXAMPLES:

sage: # needs sage.groups
sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: G4 = SymmetricGroup(4)
sage: M = AutomaticSemigroup(Family({1:G4((1,2)), 2:G4((1,2,3,4))}),
....:                        one=G4.one())
sage: M.from_reduced_word([2, 1, 2, 2, 1]).lift()
(1,3)
sage: M.from_reduced_word([2, 1, 2, 2, 1]) == M.retract(G4((3,1)))
True

>>> from sage.all import *
>>> # needs sage.groups
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> G4 = SymmetricGroup(Integer(4))
>>> M = AutomaticSemigroup(Family({Integer(1):G4((Integer(1),Integer(2))), Integer(2):G4((Integer(1),Integer(2),Integer(3),Integer(4)))}),
...                        one=G4.one())
>>> M.from_reduced_word([Integer(2), Integer(1), Integer(2), Integer(2), Integer(1)]).lift()
(1,3)
>>> M.from_reduced_word([Integer(2), Integer(1), Integer(2), Integer(2), Integer(1)]) == M.retract(G4((Integer(3),Integer(1))))
True
gens()[source]#

Return the family of generators of self.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(28)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}))
sage: M.semigroup_generators()
Finite family {1: 3, 2: 5}

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(28))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}))
>>> M.semigroup_generators()
Finite family {1: 3, 2: 5}
lift(x)[source]#

Lift an element of self into its ambient space.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(15)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: a = M.an_element()
sage: a.lift() in R
True
sage: a.lift()
3
sage: [m.lift() for m in M]
[1, 3, 5, 9, 0, 10, 12, 6]

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(15))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> a = M.an_element()
>>> a.lift() in R
True
>>> a.lift()
3
>>> [m.lift() for m in M]
[1, 3, 5, 9, 0, 10, 12, 6]
list()[source]#

Return the list of elements of self.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(12)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: M.repr_element_method("reduced_word")
sage: M.list()
[[], [1], [2], [1, 1]]

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(12))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> M.repr_element_method("reduced_word")
>>> M.list()
[[], [1], [2], [1, 1]]
product(x, y)[source]#

Return the product of two elements in self. It is done by retracting the multiplication in the ambient semigroup.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(12)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: a = M[1]
sage: b = M[2]
sage: a*b
[1]

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(12))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> a = M[Integer(1)]
>>> b = M[Integer(2)]
>>> a*b
[1]
repr_element_method(style='ambient')[source]#

Sets the representation of the elements of the monoid.

INPUT:

  • style – “ambient” or “reduced_word”

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(17)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}), one=R.one())
sage: M.list()
[1, 3, 5, 9, 15, 8, 10, 11, 7, 6, 13, 16, 4, 14, 12, 2]
sage: M.repr_element_method("reduced_word")
sage: M.list()
[[], [1], [2], [1, 1], [1, 2], [2, 2], [1, 1, 1], [1, 1, 2], [1, 2, 2],
 [2, 2, 2], [1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 2], [1, 1, 1, 1, 2],
 [1, 1, 1, 2, 2], [1, 1, 1, 1, 2, 2]]

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(17))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}), one=R.one())
>>> M.list()
[1, 3, 5, 9, 15, 8, 10, 11, 7, 6, 13, 16, 4, 14, 12, 2]
>>> M.repr_element_method("reduced_word")
>>> M.list()
[[], [1], [2], [1, 1], [1, 2], [2, 2], [1, 1, 1], [1, 1, 2], [1, 2, 2],
 [2, 2, 2], [1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 2], [1, 1, 1, 1, 2],
 [1, 1, 1, 2, 2], [1, 1, 1, 1, 2, 2]]
retract(ambient_element, check=True)[source]#

Retract an element of the ambient semigroup into self.

EXAMPLES:

sage: # needs sage.groups
sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: S5 = SymmetricGroup(5); S5.rename("S5")
sage: M = AutomaticSemigroup(Family({1:S5((1,2)), 2:S5((1,2,3,4))}),
....:                        one=S5.one())
sage: m = M.retract(S5((3,1))); m
(1,3)
sage: m.parent() is M
True
sage: M.retract(S5((4,5)), check=False)
(4,5)
sage: M.retract(S5((4,5)))
Traceback (most recent call last):
...
ValueError: (4,5) not in A subgroup of (S5) with 2 generators

>>> from sage.all import *
>>> # needs sage.groups
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> S5 = SymmetricGroup(Integer(5)); S5.rename("S5")
>>> M = AutomaticSemigroup(Family({Integer(1):S5((Integer(1),Integer(2))), Integer(2):S5((Integer(1),Integer(2),Integer(3),Integer(4)))}),
...                        one=S5.one())
>>> m = M.retract(S5((Integer(3),Integer(1)))); m
(1,3)
>>> m.parent() is M
True
>>> M.retract(S5((Integer(4),Integer(5))), check=False)
(4,5)
>>> M.retract(S5((Integer(4),Integer(5))))
Traceback (most recent call last):
...
ValueError: (4,5) not in A subgroup of (S5) with 2 generators
semigroup_generators()[source]#

Return the family of generators of self.

EXAMPLES:

sage: from sage.monoids.automatic_semigroup import AutomaticSemigroup
sage: R = IntegerModRing(28)
sage: M = AutomaticSemigroup(Family({1: R(3), 2: R(5)}))
sage: M.semigroup_generators()
Finite family {1: 3, 2: 5}

>>> from sage.all import *
>>> from sage.monoids.automatic_semigroup import AutomaticSemigroup
>>> R = IntegerModRing(Integer(28))
>>> M = AutomaticSemigroup(Family({Integer(1): R(Integer(3)), Integer(2): R(Integer(5))}))
>>> M.semigroup_generators()
Finite family {1: 3, 2: 5}