Examples of finite semigroups#

sage.categories.examples.finite_semigroups.Example[source]#

alias of LeftRegularBand

class sage.categories.examples.finite_semigroups.LeftRegularBand(alphabet=('a', 'b', 'c', 'd'))[source]#

Bases: UniqueRepresentation, Parent

An example of a finite semigroup

This class provides a minimal implementation of a finite semigroup.

EXAMPLES:

sage: S = FiniteSemigroups().example(); S
An example of a finite semigroup:
 the left regular band generated by ('a', 'b', 'c', 'd')
>>> from sage.all import *
>>> S = FiniteSemigroups().example(); S
An example of a finite semigroup:
 the left regular band generated by ('a', 'b', 'c', 'd')

This is the semigroup generated by:

sage: S.semigroup_generators()
Family ('a', 'b', 'c', 'd')
>>> from sage.all import *
>>> S.semigroup_generators()
Family ('a', 'b', 'c', 'd')

such that \(x^2 = x\) and \(x y x = xy\) for any \(x\) and \(y\) in \(S\):

sage: S('dab')
'dab'
sage: S('dab') * S('acb')
'dabc'
>>> from sage.all import *
>>> S('dab')
'dab'
>>> S('dab') * S('acb')
'dabc'

It follows that the elements of \(S\) are strings without repetitions over the alphabet \(a\), \(b\), \(c\), \(d\):

sage: sorted(S.list())
['a', 'ab', 'abc', 'abcd', 'abd', 'abdc', 'ac', 'acb', 'acbd', 'acd',
 'acdb', 'ad', 'adb', 'adbc', 'adc', 'adcb', 'b', 'ba', 'bac',
 'bacd', 'bad', 'badc', 'bc', 'bca', 'bcad', 'bcd', 'bcda', 'bd',
 'bda', 'bdac', 'bdc', 'bdca', 'c', 'ca', 'cab', 'cabd', 'cad',
 'cadb', 'cb', 'cba', 'cbad', 'cbd', 'cbda', 'cd', 'cda', 'cdab',
 'cdb', 'cdba', 'd', 'da', 'dab', 'dabc', 'dac', 'dacb', 'db',
 'dba', 'dbac', 'dbc', 'dbca', 'dc', 'dca', 'dcab', 'dcb', 'dcba']
>>> from sage.all import *
>>> sorted(S.list())
['a', 'ab', 'abc', 'abcd', 'abd', 'abdc', 'ac', 'acb', 'acbd', 'acd',
 'acdb', 'ad', 'adb', 'adbc', 'adc', 'adcb', 'b', 'ba', 'bac',
 'bacd', 'bad', 'badc', 'bc', 'bca', 'bcad', 'bcd', 'bcda', 'bd',
 'bda', 'bdac', 'bdc', 'bdca', 'c', 'ca', 'cab', 'cabd', 'cad',
 'cadb', 'cb', 'cba', 'cbad', 'cbd', 'cbda', 'cd', 'cda', 'cdab',
 'cdb', 'cdba', 'd', 'da', 'dab', 'dabc', 'dac', 'dacb', 'db',
 'dba', 'dbac', 'dbc', 'dbca', 'dc', 'dca', 'dcab', 'dcb', 'dcba']

It also follows that there are finitely many of them:

sage: S.cardinality()
64
>>> from sage.all import *
>>> S.cardinality()
64

Indeed:

sage: 4 * ( 1 + 3 * (1 + 2 * (1 + 1)))
64
>>> from sage.all import *
>>> Integer(4) * ( Integer(1) + Integer(3) * (Integer(1) + Integer(2) * (Integer(1) + Integer(1))))
64

As expected, all the elements of \(S\) are idempotents:

sage: all( x.is_idempotent() for x in S )
True
>>> from sage.all import *
>>> all( x.is_idempotent() for x in S )
True

Now, let us look at the structure of the semigroup:

sage: S = FiniteSemigroups().example(alphabet = ('a','b','c'))
sage: S.cayley_graph(side="left", simple=True).plot()                           # needs sage.graphs sage.plot
Graphics object consisting of 60 graphics primitives
sage: S.j_transversal_of_idempotents()  # random (arbitrary choice)             # needs sage.graphs
['acb', 'ac', 'ab', 'bc', 'a', 'c', 'b']
>>> from sage.all import *
>>> S = FiniteSemigroups().example(alphabet = ('a','b','c'))
>>> S.cayley_graph(side="left", simple=True).plot()                           # needs sage.graphs sage.plot
Graphics object consisting of 60 graphics primitives
>>> S.j_transversal_of_idempotents()  # random (arbitrary choice)             # needs sage.graphs
['acb', 'ac', 'ab', 'bc', 'a', 'c', 'b']

We conclude by running systematic tests on this semigroup:

sage: TestSuite(S).run(verbose = True)
running ._test_an_element() . . . pass
running ._test_associativity() . . . pass
running ._test_cardinality() . . . pass
running ._test_category() . . . pass
running ._test_construction() . . . pass
running ._test_elements() . . .
  Running the test suite of self.an_element()
  running ._test_category() . . . pass
  running ._test_eq() . . . pass
  running ._test_new() . . . pass
  running ._test_not_implemented_methods() . . . pass
  running ._test_pickling() . . . pass
  pass
running ._test_elements_eq_reflexive() . . . pass
running ._test_elements_eq_symmetric() . . . pass
running ._test_elements_eq_transitive() . . . pass
running ._test_elements_neq() . . . pass
running ._test_enumerated_set_contains() . . . pass
running ._test_enumerated_set_iter_cardinality() . . . pass
running ._test_enumerated_set_iter_list() . . . pass
running ._test_eq() . . . pass
running ._test_new() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
running ._test_some_elements() . . . pass
>>> from sage.all import *
>>> TestSuite(S).run(verbose = True)
running ._test_an_element() . . . pass
running ._test_associativity() . . . pass
running ._test_cardinality() . . . pass
running ._test_category() . . . pass
running ._test_construction() . . . pass
running ._test_elements() . . .
  Running the test suite of self.an_element()
  running ._test_category() . . . pass
  running ._test_eq() . . . pass
  running ._test_new() . . . pass
  running ._test_not_implemented_methods() . . . pass
  running ._test_pickling() . . . pass
  pass
running ._test_elements_eq_reflexive() . . . pass
running ._test_elements_eq_symmetric() . . . pass
running ._test_elements_eq_transitive() . . . pass
running ._test_elements_neq() . . . pass
running ._test_enumerated_set_contains() . . . pass
running ._test_enumerated_set_iter_cardinality() . . . pass
running ._test_enumerated_set_iter_list() . . . pass
running ._test_eq() . . . pass
running ._test_new() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
running ._test_some_elements() . . . pass
class Element[source]#

Bases: ElementWrapper

wrapped_class#

alias of str

an_element()[source]#

Returns an element of the semigroup.

EXAMPLES:

sage: S = FiniteSemigroups().example()
sage: S.an_element()
'cdab'

sage: S = FiniteSemigroups().example(("b"))
sage: S.an_element()
'b'
>>> from sage.all import *
>>> S = FiniteSemigroups().example()
>>> S.an_element()
'cdab'

>>> S = FiniteSemigroups().example(("b"))
>>> S.an_element()
'b'
product(x, y)[source]#

Returns the product of two elements of the semigroup.

EXAMPLES:

sage: S = FiniteSemigroups().example()
sage: S('a') * S('b')
'ab'
sage: S('a') * S('b') * S('a')
'ab'
sage: S('a') * S('a')
'a'
>>> from sage.all import *
>>> S = FiniteSemigroups().example()
>>> S('a') * S('b')
'ab'
>>> S('a') * S('b') * S('a')
'ab'
>>> S('a') * S('a')
'a'
semigroup_generators()[source]#

Returns the generators of the semigroup.

EXAMPLES:

sage: S = FiniteSemigroups().example(alphabet=('x','y'))
sage: S.semigroup_generators()
Family ('x', 'y')
>>> from sage.all import *
>>> S = FiniteSemigroups().example(alphabet=('x','y'))
>>> S.semigroup_generators()
Family ('x', 'y')