Finitely generated semigroups

class sage.categories.finitely_generated_semigroups.FinitelyGeneratedSemigroups(base_category)

Bases: CategoryWithAxiom_singleton

The category of finitely generated (multiplicative) semigroups.

A finitely generated semigroup is a semigroup endowed with a distinguished finite set of generators (see FinitelyGeneratedSemigroups.ParentMethods.semigroup_generators()). This makes it into an enumerated set.

EXAMPLES:

Sage

sage: C = Semigroups().FinitelyGenerated(); C
Category of finitely generated semigroups
sage: C.super_categories()
[Category of semigroups,
 Category of finitely generated magmas,
 Category of enumerated sets]
sage: sorted(C.axioms())
['Associative', 'Enumerated', 'FinitelyGeneratedAsMagma']
sage: C.example()
An example of a semigroup: the free semigroup generated
by ('a', 'b', 'c', 'd')

Python

>>> from sage.all import *
>>> C = Semigroups().FinitelyGenerated(); C
Category of finitely generated semigroups
>>> C.super_categories()
[Category of semigroups,
 Category of finitely generated magmas,
 Category of enumerated sets]
>>> sorted(C.axioms())
['Associative', 'Enumerated', 'FinitelyGeneratedAsMagma']
>>> C.example()
An example of a semigroup: the free semigroup generated
by ('a', 'b', 'c', 'd')

class Finite(base_category)

Bases: CategoryWithAxiom_singleton

class ParentMethods

Bases: object

some_elements()

Return an iterable containing some elements of the semigroup.

OUTPUT: the ten first elements of the semigroup, if they exist.

EXAMPLES:

Sage

sage: S = FiniteSemigroups().example(alphabet=('x','y'))
sage: sorted(S.some_elements())
['x', 'xy', 'y', 'yx']
sage: S = FiniteSemigroups().example(alphabet=('x','y','z'))
sage: X = S.some_elements()
sage: len(X)
10
sage: all(x in S for x in X)
True

Python

>>> from sage.all import *
>>> S = FiniteSemigroups().example(alphabet=('x','y'))
>>> sorted(S.some_elements())
['x', 'xy', 'y', 'yx']
>>> S = FiniteSemigroups().example(alphabet=('x','y','z'))
>>> X = S.some_elements()
>>> len(X)
10
>>> all(x in S for x in X)
True

class ParentMethods

Bases: object

ideal(gens, side='twosided')

Return the side-sided ideal generated by gens.

This brute force implementation recursively multiplies the elements of gens by the distinguished generators of this semigroup.

See also

semigroup_generators()

INPUT:

• gens – a list (or iterable) of elements of self

• side – [default: “twosided”] “left”, “right” or “twosided”

EXAMPLES:

Sage

sage: S = FiniteSemigroups().example()
sage: sorted(S.ideal([S('cab')], side="left"))
['abc', 'abcd', 'abdc', 'acb', 'acbd', 'acdb', 'adbc',
 'adcb', 'bac', 'bacd', 'badc', 'bca', 'bcad', 'bcda',
 'bdac', 'bdca', 'cab', 'cabd', 'cadb', 'cba', 'cbad',
 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca',
 'dcab', 'dcba']
sage: list(S.ideal([S('cab')], side="right"))
['cab', 'cabd']
sage: sorted(S.ideal([S('cab')], side="twosided"))
['abc', 'abcd', 'abdc', 'acb', 'acbd', 'acdb', 'adbc',
 'adcb', 'bac', 'bacd', 'badc', 'bca', 'bcad', 'bcda',
 'bdac', 'bdca', 'cab', 'cabd', 'cadb', 'cba', 'cbad',
 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca',
 'dcab', 'dcba']
sage: sorted(S.ideal([S('cab')]))
['abc', 'abcd', 'abdc', 'acb', 'acbd', 'acdb', 'adbc',
 'adcb', 'bac', 'bacd', 'badc', 'bca', 'bcad', 'bcda',
 'bdac', 'bdca', 'cab', 'cabd', 'cadb', 'cba', 'cbad',
 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca',
 'dcab', 'dcba']

Python

>>> from sage.all import *
>>> S = FiniteSemigroups().example()
>>> sorted(S.ideal([S('cab')], side="left"))
['abc', 'abcd', 'abdc', 'acb', 'acbd', 'acdb', 'adbc',
 'adcb', 'bac', 'bacd', 'badc', 'bca', 'bcad', 'bcda',
 'bdac', 'bdca', 'cab', 'cabd', 'cadb', 'cba', 'cbad',
 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca',
 'dcab', 'dcba']
>>> list(S.ideal([S('cab')], side="right"))
['cab', 'cabd']
>>> sorted(S.ideal([S('cab')], side="twosided"))
['abc', 'abcd', 'abdc', 'acb', 'acbd', 'acdb', 'adbc',
 'adcb', 'bac', 'bacd', 'badc', 'bca', 'bcad', 'bcda',
 'bdac', 'bdca', 'cab', 'cabd', 'cadb', 'cba', 'cbad',
 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca',
 'dcab', 'dcba']
>>> sorted(S.ideal([S('cab')]))
['abc', 'abcd', 'abdc', 'acb', 'acbd', 'acdb', 'adbc',
 'adcb', 'bac', 'bacd', 'badc', 'bca', 'bcad', 'bcda',
 'bdac', 'bdca', 'cab', 'cabd', 'cadb', 'cba', 'cbad',
 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca',
 'dcab', 'dcba']

semigroup_generators()

Return distinguished semigroup generators for self.

OUTPUT: a finite family

This method should be implemented by all semigroups in FinitelyGeneratedSemigroups.

EXAMPLES:

Sage

sage: S = FiniteSemigroups().example()
sage: S.semigroup_generators()
Family ('a', 'b', 'c', 'd')

Python

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

succ_generators(side='twosided')

Return the successor function of the side-sided Cayley graph of self.

This is a function that maps an element of self to all the products of x by a generator of this semigroup, where the product is taken on the left, right, or both sides.

INPUT:

• side: “left”, “right”, or “twosided”

Todo

Design choice:

• find a better name for this method

• should we return a set? a family?

EXAMPLES:

Sage

sage: S = FiniteSemigroups().example()
sage: S.succ_generators("left" )(S('ca'))
('ac', 'bca', 'ca', 'dca')
sage: S.succ_generators("right")(S('ca'))
('ca', 'cab', 'ca', 'cad')
sage: S.succ_generators("twosided" )(S('ca'))
('ac', 'bca', 'ca', 'dca', 'ca', 'cab', 'ca', 'cad')

Python

>>> from sage.all import *
>>> S = FiniteSemigroups().example()
>>> S.succ_generators("left" )(S('ca'))
('ac', 'bca', 'ca', 'dca')
>>> S.succ_generators("right")(S('ca'))
('ca', 'cab', 'ca', 'cad')
>>> S.succ_generators("twosided" )(S('ca'))
('ac', 'bca', 'ca', 'dca', 'ca', 'cab', 'ca', 'cad')

example()

EXAMPLES:

Sage

sage: Semigroups().FinitelyGenerated().example()
An example of a semigroup: the free semigroup generated
by ('a', 'b', 'c', 'd')

Python

>>> from sage.all import *
>>> Semigroups().FinitelyGenerated().example()
An example of a semigroup: the free semigroup generated
by ('a', 'b', 'c', 'd')

extra_super_categories()

State that a finitely generated semigroup is endowed with a default enumeration.

EXAMPLES:

Sage

sage: Semigroups().FinitelyGenerated().extra_super_categories()
[Category of enumerated sets]

Python

>>> from sage.all import *
>>> Semigroups().FinitelyGenerated().extra_super_categories()
[Category of enumerated sets]