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()
, orlist()
, 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