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)

Bases: sage.monoids.automatic_semigroup.AutomaticSemigroup

gens()

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}

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

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

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}

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

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

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
semigroup_generators()

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])
sage: M.semigroup_generators()
Family (1, F[1], F[2], F[3])
sage.monoids.automatic_semigroup.AutomaticSemigroup

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]

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

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

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: G = M.cayley_graph(side = "twosided"); G
Looped multi-digraph on 4 vertices
sage: sorted(G.edges(), 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()))
[[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: 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)

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

    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()
    sage: C.is_directed_acyclic()
    False

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

    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

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

    sage: len(M.idempotents())
    16
    sage: all([len(j) == 1 for j in M.j_classes()])
    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:`Automatic_semigroup`.

.. WARNING::

    :class:`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